注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

千鸟

本blog所有日志均系原创 转载请注明出处

 
 
 

日志

 
 

图搜索(A*算法) java版  

2007-03-31 22:10:24|  分类: Arithmetic |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

图搜索(A*算法) java版 - souljava - 千鸟

/*
 * AStar.java
 *
 * Created on April 1, 2007, 9:48 PM
 *
 
 */

package com.soulnew;


/**
 *@author soulnew@soulnew.com
 */
import java.util.*;
public class AStar {
   
    /** Creates a new instance of AStar */
    public AStar() {
    }
    public static class PriorityList extends LinkedList {
       
        public void add(Comparable object) {
            for (int i=0; i<size(); i++) {
                if (object.compareTo(get(i)) <= 0) {
                    add(i, object);
                    return;
                }
            }
            addLast(object);
        }
    }


    /**
        Construct the path, not including the start node.
    */
    protected List constructPath(AStarNode node) {
        LinkedList path = new LinkedList();
        while (node.pathParent != null) {
            path.addFirst(node);
            node = node.pathParent;
        }
        return path;
    }

    public List findPath(AStarNode startNode, AStarNode goalNode) {
       
        LinkedList openList = new LinkedList();  //要访问的节点放到这个表
        LinkedList closedList = new LinkedList();  //已经访问过的节点放到这个表
       
        startNode.costFromStart = 0;    //设置起点到自己的距离是0
        startNode.estimatedCostToGoal =
         startNode.getEstimatedCost(goalNode);  //得到至终点的估计成本,赋值给起点
        startNode.pathParent = null;     //和广度优先一样pathParent用来记录,上一个节点,通过遍历就可以找到起点
        openList.add(startNode);  //把起点放入 即将用来搜索的表中
       
        while (!openList.isEmpty()) {
            AStarNode node = (AStarNode)openList.removeFirst();  //从要访问的表中取处一个来
//            if (node == goalNode) {
                // construct the path from start to goal
                //找到终点了,停止搜索,开始遍历路径
               
//            }
           
            List neighbors = node.getNeighbors();
            for (int i=0; i<neighbors.size(); i++) {    //遍历所有的邻居节点
                AStarNode neighborNode =
                        (AStarNode)neighbors.get(i);
                boolean isOpen = openList.contains(neighborNode);
                //isOpen 用来判断邻居节点在不在即将访问的表中
                boolean isClosed =
                        closedList.contains(neighborNode);
                //isClosed  用来判断邻居节点在不在已经访问过的表中
                int costFromStart = node.costFromStart +node.getCost(neighborNode);  //获得该节点成本
               
                // check if the neighbor node has not been
                // traversed or if a shorter path to this
                // neighbor node is  found.
                if ((!isOpen && !isClosed) ||costFromStart < neighborNode.costFromStart)
                    //检查邻居节点是否还未遍历,或找到了这个邻居节点的更短路径
                {
                    neighborNode.pathParent = node;
                    neighborNode.costFromStart = costFromStart;
//                    neighborNode.estimatedCostToGoal = neighborNode.getEstimatedCost(goalNode);
                    //估计到重点的距离的方法,看使用A*的具体场合
                    if (node!= goalNode) {
                        if (isClosed) {
                            closedList.remove(neighborNode);
                            //找到该节点的更短路径,则该路径从已访问过的表中移走
                        }
                        if (!isOpen) {
                            openList.add(neighborNode);
                        }
                    }
                }
            }
            closedList.add(node);
        }
        return constructPath(goalNode);
       
        // no path found
     //   return null;
    }
    public static void main(String[] args) {
        AStarNode nodeA = new  AStarNode("A",0,10);
        AStarNode nodeB = new  AStarNode("B",5,15);
        AStarNode nodeC = new  AStarNode("C",10,20);
        AStarNode nodeD = new AStarNode("D",15,15);
        AStarNode nodeE = new AStarNode("E",20,10);
        AStarNode nodeF = new AStarNode("F",15,5);
        AStarNode nodeG = new AStarNode("G",10,0);
        AStarNode nodeH = new AStarNode("H",5,5);
       
       
        nodeA.neighbors.add(nodeF);
        nodeA.neighbors.add(nodeC);
        nodeA.neighbors.add(nodeE);
       
         nodeC.neighbors.add(nodeA);
         nodeC.neighbors.add(nodeE);
        
         nodeE.neighbors.add(nodeA);
         nodeE.neighbors.add(nodeC);
         nodeE.neighbors.add(nodeF);
        
         nodeF.neighbors.add(nodeA);       
         nodeF.neighbors.add(nodeE);

       
        AStar bfs = new AStar ();
        System.out.println("From A to F: " +
                bfs.findPath(nodeA, nodeF).toString());
        System.out.println("From C to F: " +
               bfs.findPath(nodeC, nodeF).toString());
       System.out.println("From F to C: " +
                bfs.findPath(nodeF, nodeC));
//        System.out.println("From A to G: " +
//                bfs.findPath(nodeH, nodeG).toString());
//        System.out.println("From A to unknown: " +
//                bfs.findPath(nodeA, new AStarNode("unknown",0,0)).toString());

    }
}

 //////////

/*

  AStarNode.java

*/

////////

/*
 * AStarNode.java
 *
 **
 
 */

package com.soulnew;


/**
 *
 * @author soulnew@soulnew.com
 */
import java.util.*;
import java.math.*;
public class AStarNode {
   
    /** Creates a new instance of AStarNode */
    public AStarNode(String name,int x,int y) {
        neighbors=new LinkedList();
        this.x=x;
        this.y=y;
        this.name=name;
    }
    String name;
    int costFromStart;   
    int estimatedCostToGoal;
    int x,y;
    AStarNode pathParent;
    List neighbors;
   
    public String toString() {
        return name;
    }
   
    public int getEstimatedCost(AStarNode node){  //
        int dx=this.x-node.x;
        int dy=this.y-node.y;
       return (int)Math.sqrt(dx*dx+dy*dy);
    }
   
    public List getNeighbors(){
        return neighbors;
    }
   
    public int getCost(AStarNode node){
        int dx=this.x-node.x;
        int dy=this.y-node.y;
        return (int)Math.sqrt(dx*dx+dy*dy);
    }

   
}

out:

From A to F: [F]
From C to F: [E, F]
From F to C: [E, C]

 

  评论这张
 
阅读(1001)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017