A *搜索算法的最壞情況是什麼？

在什麼條件下將A *搜索算法探索搜索空間的所有狀態？這是最糟糕的情況嗎？A *搜索算法的最壞情況是什麼？

據我來說，這將被迫搜索整個搜索空間，如果F（N），用於向目標的路徑上的每個節點，是不是在同一水平上的其他節點更高。這是最壞的情況，因爲所產生的所有節點都必須擴大以達到目標。

這是正確的嗎？

A的時間複雜度*取決於啓發式。在最壞的情況下，膨脹的節點的數目是在溶液中（最短路徑）的長度的指數，但它是多項式時的搜索空間是一棵樹，有一個單一的目標狀態，並且啓發式函數h滿足某些標準：

2012-11-17 10:29:54 ajon

您能否解釋一下這個問題，其中的算法探索了搜索空間中的所有狀態（考慮一棵樹只存在一個目標狀態） –

這實際上是一個非常酷的保證！然而，在平面（或低維）空間的典型情況下，即使沒有啓發式搜索，搜索也將是多項式。 –

回答