1
我想了解A *，統一成本和貪婪搜索算法是如何工作的。我知道在所有3種算法中探索節點的方式發生了變化（貪婪會基於啓發式值探索，基於啓發式加距離的A *，基於距離的均勻性）。A *總是提供最短路徑嗎？
我想知道是否對於給定的來源和目的地，所有3種算法是否提供了最短路徑（僅探索了不同數量的城市？），還是可以提供不同的路徑。
由於實現部分的原因，我大多感到困惑 - 如果將節點存儲在隊列中，則當您要探索目標節點時，您將擁有最短路徑，但如果您有路徑隊列（並且此隊列現在是基於啓發式+距離排序），那麼你可能並不總是獲得最短路徑。
即使啓發式是不可接受的，A *算法只會在探索目標節點時停止（由於不可接受的啓發式，它可能會探索許多不必要的路徑），在這種情況下，它必須首先探索所有到達該節點的路徑，以便它總能找到最短路徑，不是嗎？ – harrythomas
@harrythomas不，作爲一個極端的例子，考慮一個方形網格，一端在一個頂端角落，另一個在底部角落。我可以做一個啓發式算法，使算法首先遵循邊界，這將導致次優解決方案。 – orlp
是的，但在這種情況下，當你探索另一條邊時，你會發現最短的距離，你會更新它的權利？或者在A *星你不更新最短距離？考慮統一成本搜索找到最短路徑的方式（通過使用找到的新值更新當前最短值） – harrythomas