Go语言视频零基础入门到精通

javalearner

/*
  * 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() {
     }
   
     /**
         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]
  

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/7/000339093.zip