1
我已經實施並使用過幾次A *，並且認爲我知道關於A *的所有知識。直到我遇到這個例子：A * - 簡單的圖表示例 - 錯誤的結果
該圖由4個節點和6向加權邊緣。啓發式按每個節點H=…表示。啓發式顯然是可以接受的，所以我沒有看到任何問題。
問題是找到從開始到目標的路線，而且總成本最小。正確的解決方案是採取邊緣與成本的路徑36和18
我的A *的實現執行以下步驟（省略有關封閉列表的任何操作）：
- 所述的StartNode是{ G = 0，H = 200， - > F = 200}並被選爲'當前節點'
- 所有鄰居都被添加到打開列表
= {{G=5, H=100, F=105}, {G=36, H=100, F=136}}。 - 選擇新的'當前節點'，這是開放列表中具有最小F的節點，它是圖像中較高節點
F = 105的節點。 - 該節點的鄰居被添加到開放列表中，該開放列表包含元素{{G = 36，H = 100，F = 136}，{G = 58，H = 0，F = 58}}。
- 再次選擇一個新的當前節點，這是目標節點，所以算法終止，成本爲5和53的路由被選中。
所以實現會產生錯誤的結果。這些步驟中應該發生什麼？
那麼，這當然不是一個圖（因爲有成對的節點共享兩個邊而不是一個或零），但這不是A *在這裏不起作用的原因。通過用較低的代價替換每個雙邊，可以很容易地製作一個圖表。 –
@Doc Brown - 如果您採用適當的圖形定義，這當然是一個圖表。具體來說，它是一個沒有循環的定向多圖。從[維基百科]（http://en.wikipedia.org/wiki/Multigraph）（當然，這對任何事情都是正確的：〜））：「在數學中，多圖或僞圖是允許有多條邊......「 –
@Ted Hopp：如果你詳細閱讀了維基百科的文章，你會發現它給出了術語」圖「的不同定義，而」多圖「與最常見的定義不符。然而，這裏重要的問題是「A *適用於多圖？」答案是 - 「不是直接的，而是通過將多圖轉化爲經典圖，它可以被應用。」 –