卡住实施维基百科的A *（“A星”）算法

Question

我实施A *从这个伪维基百科的文章搜索算法：

function A*(start,goal) 
    closedset := the empty set // The set of nodes already evaluated. 
    openset := set containing the initial node // The set of tentative nodes to be evaluated. 
    came_from := the empty map // The map of navigated nodes. 

    g_score[start] := 0 // Cost from start along best known path. 
    h_score[start] := heuristic_cost_estimate(start, goal) 
    f_score[start] := h_score[start] // Estimated total cost from start to goal through y. 

    while openset is not empty 
     x := the node in openset having the lowest f_score[] value 
     if x = goal 
      return reconstruct_path(came_from, came_from[goal]) 

     remove x from openset 
     add x to closedset 
     foreach y in neighbor_nodes(x) 
      if y in closedset 
       continue 
      tentative_g_score := g_score[x] + dist_between(x,y) 

      if y not in openset 
       add y to openset 
       tentative_is_better := true 
      else if tentative_g_score < g_score[y] 
       tentative_is_better := true 
      else 
       tentative_is_better := false 

      if tentative_is_better = true 
       came_from[y] := x 
       g_score[y] := tentative_g_score 
       h_score[y] := heuristic_cost_estimate(y, goal) 
       f_score[y] := g_score[y] + h_score[y] 

    return failure 


function reconstruct_path(came_from, current_node) 
    if came_from[current_node] is set 
     p = reconstruct_path(came_from, came_from[current_node]) 
     return (p + current_node) 
    else 
     return current_node 

我卡在那里有人问我行以最低的f值检索openSet中的节点。 openSet何时被填充？什么？它应该在第一次运行时就开始了吗？

我也不在已了解重构路径伪：

ArrayList<Point> reconstructPath(Point cameFrom, Point current_node){ 

     //if came_from[current_node] is set //what does it mean "ïs set"? 
     //??? 
     return null; 

    } 

应该如何是伪指令来实现？

boolean AStar (Point start, Point goal){ 

     HashSet <Point>closedSet = new HashSet<Point>(); 
     HashSet <Point>openSet = new HashSet<Point>(); 
     HashMap <Point,Point> came_from = new HashMap<Point, Point>(); 

     HashMap <Point, Integer> g_score = new HashMap<Point, Integer>(); 
     HashMap <Point, Integer> h_score =new HashMap<Point,Integer>(); 
     HashMap <Point,Integer> f_score =new HashMap<Point,Integer>(); 

     g_score.put(start, 0); 
     h_score.put(start, heuristic_cost_estimate(start,goal)); 
     f_score.put(start, heuristic_cost_estimate(start,goal)); 


     openSet.add(start); 
     while(!openSet.isEmpty()){ 

      // x := the node in openset having the lowest f_score[] value 
      //???? 
     } 

     return false; 

    } 

Integer heuristic_cost_estimate(Point start, Point goal){ 

     double minusI = (start.I-goal.I); 
     int minusIi =(int)Math.pow(minusI,2.0D); 

     double minusJ = (start.J-goal.J); 
     int minusIj =(int)Math.pow(minusJ,2.0D); 

     int ri = minusIj + minusIi; 

     Integer result = new Integer(ri); 

     return result; 


    } 



ArrayList<Point> reconstructPath(Point cameFrom, Point current_node){ 

     //if came_from[current_node] is set //what does it mean "ïs set"? 
     //??? 
     return null; 

    } 

Answer 1

打开集最初包含您从开始搜索的节点 - 起始节点。

openset := set containing the initial node // The set of tentative nodes to be evaluated. 

对于重构路径的一部分 - 每次处理一个节点，并找到其邻居X可以从当前节点更低的成本来达到的时候，你应该设置came_from项X到节点你”目前正在处理。一旦找到目标节点，就会按照目标节点中的came_from条目重新构建路径，直到到达源节点。您可以通过修改Point类来实现此目的，使其具有名为came_from的附加字段。

从哈希表中提取具有最低值的节点的唯一方法是遍历哈希表。另一种方法是另外有一个树形图，它可以让你快速找到具有最小值的元素（或者有一个专门的堆，例如二进制或Fibonacci堆，它可以让你减少堆内元素的值）。

This是我最初学习A *的地方。