卡住實施維基百科的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 *的地方。