A *的時間複雜度

維基說對A *的複雜以下幾點：A *的時間複雜度

A *的時間複雜度依賴於啓發式。在最壞的情況下，擴展節點的數量在溶液（最短路徑）的長度指數，但它是多項式當搜索空間是一棵樹......

我的問題是：「A *的時間複雜度是指數級的嗎？還是不是時間複雜度，而是內存複雜度？」如果是內存複雜度，A *具有哪種時間複雜度？

來源

2012-06-17 Szkandy

它說時間的複雜性。 – leppie

可能的重複項：http://stackoverflow.com/q/1715401/1328439 –

由於每個展開的節點存儲避免前往同一個節點多次，擴展節點的數量呈指數級增長意味着指數時間和空間複雜性。

請注意，指數空間複雜度必要意味着指數時間複雜度。反過來是不正確的。

來源

2012-06-17 09:38:43

非常感謝。這正是我所需要知道的。 – Szkandy

@ user1403414恐怕這不是一個完整的答案，因爲維基百科文章說A *在解決方案的長度上是指數級的。這與複雜性理論的標準設置不同，其中複雜度是根據輸入的長度來衡量的。 –

這是'O（（| V | + | E |）log | V |）'。在圖形大小方面描述A *複雜性是最有意義的。這個答案令人驚訝地很差（維基百科驅動也許？不是肯定科爾曼...） – PawelP

是A *時間複雜度指數還是內存複雜度？

，從維基百科中提取表明，它的參考時間複雜度

來源

2012-06-17 09:30:21

在最壞的情況下，A *的時間複雜度是指數級的。

但是，考慮h(n)估計的距離和h*(n)剩餘的確切距離。如果條件| h(n) - h*(n) | < O(log *h(n))成立，也就是說，如果我們的估計函數的錯誤增長爲亞指數，則A *時間複雜度將爲多項式。不幸的是，大多數時候估計誤差增長是線性的，所以在實踐中，更快的替代方案是優選的，所支付的價格是最優性不再被實現。

來源

2012-08-30 08:01:36 coredump

A *的時間複雜度

回答

相關問題