A *算法不能正常工作

Question

我需要一些幫助來實現我的A *算法。 當我運行該算法時，它確實找到了目標，但路徑絕對不是最短路徑:-P

這是我的代碼，請幫助我發現錯誤！ 我認爲這可能是重建路徑，這是我的問題，但我不確定。

public class Pathfinder { 

public List<Node> aStar(Node start, Node goal, WeightedGraph graph) { 
    Node x, y; 
    int tentative_g_score; 
    boolean tentative_is_better; 

    FScoreComparator comparator = new FScoreComparator(); 
    List<Node> closedset = new ArrayList<Node>(); 
    Queue<Node> openset = new PriorityQueue<Node>(10, comparator); 
    openset.add(start); 

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

    while (!openset.isEmpty()) { 
     x = openset.peek(); 

     if (x == goal) { 
      return reconstruct_path(goal); 
     } 

     x = openset.remove(); 
     closedset.add(x); 

     for (Edge e : graph.adj(x)) { 

      if (e.v == x) { 
       y = e.w; 
      } else { 
       y = e.v; 
      } 

      if (closedset.contains(y) || y.illegal) { 
       continue; 
      } 

      tentative_g_score = x.g_score + e.weight; 

      if (!openset.contains(y)) { 
       openset.add(y); 
       tentative_is_better = true; 
      } else if (tentative_g_score < y.g_score) { 
       tentative_is_better = true; 
      } else { 
       tentative_is_better = false; 
      } 

      if (tentative_is_better) { 
       y.g_score = tentative_g_score; 
       y.h_score = heuristic_cost_estimate(y, goal); 
       y.f_score = y.g_score + y.h_score; 
       y.parent = x; 
      } 

     } 

    } 

    return null; 

} 

private int heuristic_cost_estimate(Node start, Node goal) { 
    return Math.abs(start.x - goal.x) + Math.abs(start.y - goal.y); 
} 

private List<Node> reconstruct_path(Node current_node) { 
    List<Node> result = new ArrayList<Node>(); 

    while (current_node != null) { 
     result.add(current_node); 
     current_node = current_node.parent; 
    } 

    return result; 
} 

private class FScoreComparator implements Comparator<Node> { 

    public int compare(Node n1, Node n2) { 
     if (n1.f_score < n2.f_score) { 
      return 1; 
     } else if (n1.f_score > n2.f_score) { 
      return -1; 
     } else { 
      return 0; 
     } 
    } 
} 

}

感謝大家爲所有偉大的答案！ 感謝你們，我的A *算法現在可以完美工作！ :-)

這是我的第一篇文章，這個論壇真的很棒！

Answer 1

您正在改變的元素的優先級在PriorityQueue。這不受支持，因爲優先級隊列不知道對象已更改。你可以做的是刪除並重新添加對象，當它改變。

該行的優先級更改爲：y.f_score = y.g_score + y.h_score;。該行在將y添加到優先級隊列後發生。請注意，僅僅在計算成本後將openset.add(y);行移動到僅僅是因爲y可能已經在先前的迭代中添加了。

從代碼中也不清楚您使用的啓發式是admissible。如果不是，它也會導致你獲得次優路徑。

最後，性能注意事項：ArrayList和PriorityQueue上的contains方法需要線性運行時間，這將使您的實施的運行時間不是最優的。您可以通過向節點添加布爾屬性來指示它們是處於關閉/打開集合中還是通過使用集合數據結構來改善這一點。

Answer 2

當您更改其優先級時，優先隊列不更新項目的位置。 因此堆屬性不成立。 更改的優先級會影響其他項目的添加/刪除，但不會修復堆屬性。

因此，您沒有從打開中獲得最佳物品 - >您找不到最短路徑。

您可以： 1）寫自己的堆和維護索引，它 2）添加另一個對象爲PQ和標記舊爲無效（必須的，而不是節點把一些物體有效標誌和引用節點進入隊列）。 2）性能較差，我建議不要這樣做，但一些導航軟件使用這種方法（或者至少幾年前使用它）。

編輯：最好的做法是，插入不可變的（或至少與該裝置優先imutable份）具有插入之後對象插入的PriorityQueue