Dijkstra的算法VS均勻成本搜索（時間自適應）

我的問題如下：根據不同的消息來源，Dijkstra的算法只不過是一個統一成本搜索的變種。我們知道Dijkstra的算法找到了源和所有目的地（單一來源）之間的最短路徑。然而，我們總是可以修改Dijkstra以找到START和GOAL狀態之間的最短路徑（當目標從優先級隊列中彈出時，我們簡單地停止）;但是這樣做，最糟糕的情況是仍然會找到從START到所有其他節點的最短路徑（假設目標是圖中最遠的節點）。Dijkstra的算法VS均勻成本搜索（時間自適應）

如果我們使用最小優先級堆實現Dijkstra算法，運行時間將爲 O（V log V + E），其中E是邊數，V是頂點數。

由於統一成本搜索與Dijkstra相同（略有不同的實現），那麼UCS的運行時間應該與Dijkstra類似，對吧？然而，根據我的AI類，統一成本搜索在最壞的情況下呈指數形式，它需要O（b ^{1 + [C * /ε]}），其中C *是最優解的成本。（b是分支因子）

兩種算法在運行時間不同的情況下如何能夠相同？運行時間是否一樣，但我們看待它的方式不同？

我會感激你的幫助:) :)謝謝

來源

2012-10-19 John

是運行時間相同，但我們看它的方式是不同的？

是的。可以在無限大的圖上使用統一的成本搜索，而Dijkstra的原始算法永遠不會終止。在這種情況下，根據V和E來定義複雜性是沒有用的，因爲兩者都可能是無限的，並且由此產生的大O數字沒有意義。

來源

2012-10-19 15:04:09

讓我們堅持有限的圖（可能需要很大，但仍然完成）。那麼我怎麼能證明兩種算法具有相同的運行時間？ – John

@John：通過重寫任一算法的僞代碼直到找到其他代碼。這可能非常棘手，因爲Dijkstra通常用於存儲完全存儲在內的有限圖，但UCS用於可能無限的表示爲邊生成函數。 –

我同意你所說的，但在我的情況下，這裏我想證明的是：給定城市地圖（圖），我想證明兩種算法具有相同的時間複雜度以找到最優解 – John

Dijkstra的算法VS均勻成本搜索（時間自適應）

回答

相關問題