精確圖算法

在數據結構和算法中，「精確圖算法」是什麼意思？你能舉幾個例子嗎？精確圖算法

2010-07-09 lilop

我想它指的是算法是否產生一個結果，對於一個給定的問題來說是最優的，還是隻產生一個近似結果。

例如，如果您正在尋找在爲shortest path從一個節點到另一個圖表，還有一堆的算法（Dijkstra，Floyd-Warshall，......你他們的名字）恰好解決這個問題，即它們產生兩個給定節點之間的最短路徑。

另一方面，考慮Travelling Salesman問題。它指出了包含一些給定節點的最短循環路徑的問題。這個問題是NP-complete，因此（據說）不能在合理的時間內完全解決（至少在一般情況下）。然而，存在運行在合理時間內的近似算法，產生至多爲2*length(best route)（至少對於度量TSP）的解決方案，所以來自該算法的解決方案不是確切的解決方案，而是近似值。

來源

2010-07-09 05:52:06 phimuemue

旅行推銷員問題在歐幾里德版本等特殊情況下，具有快速的「近似兩次優化」算法。對於一般圖，沒有多項式時間算法（除非P = NP），它可以在最佳常數因子內找到近似遊程。 – 2010-07-09 05:58:04

兩次最優構造只需要非常合理的限制，即距離是對稱的並滿足三角不等式。（換句話說，距離滿足度量空間的公理）。如果距離可以是任何東西，那麼要求在一個恆定的最優因子範圍內求解與尋求最優解決方案几乎是不同的。 – 2010-07-09 06:45:12

回答

相關問題