測試Hamiltonian路徑查找器實現

Question

我正在實現一種算法，該算法可以在有向圖中找到最佳哈密頓路徑。我已經實現了一個算法，似乎工作得很好，但我不完全確定在某些情況下是否存在細微的錯誤或其他問題。因此，我需要一些解決方案已知的不同網絡，以檢查我的實施是否也應該解決問題。

由於維基百科意味着哈密頓路徑只是無向圖的適當項，因此假設「哈密頓路徑」是指在給定網絡上定向或以其他方式訪問每個節點一次且恰好一次的路徑。爲了簡單起見，我們可以假定每個連接（或「邊」）具有正整數值（或「長度」）。我們還可以假設沒有節點連接到自身，並且在任何兩個節點之間的每個方向上不能有多於一個邊。

我碰巧對總長度最長的路徑感興趣，所以「最優」意味着最長，儘管如果我想要最短的總長度（如傳統TSP）那麼它可能沒有什麼區別。我也碰巧使用了貪婪算法。

我在哪裏或如何獲得TSP已解決的定向網絡？如果實際解決方案和貪婪（或其他啓發式）解決方案可用，那將會更好。網絡應該足夠大以提供信息豐富的測試，但對於我來說手動檢查解決方案（如果解決方案最初是未知的）足夠小。它們應該拓撲多樣，足以涵蓋「簡單」和「有問題」的網絡。

對於其他人尋找相同的;我有最好的是以下網絡：

A B C D E 
A 0 1 2 0 1 
B 1 0 0 0 1 
C 0 3 0 1 2 
D 4 0 0 0 0 
E 1 0 0 2 0 

這是一個鄰接列表，行是邊緣起源和列是目的地。數字是每條邊的長度，0表示「無邊」。例如，圖4示出了邊緣的從 d 長度 A是4，並且沒有來自甲到d（長度0）連接。

該網絡中的最大長度路徑是E-> D-> A-> C-> B。它的總長度是2 + 3 + 3 + 3 = 11。我相信貪婪算法能夠在這種情況下找到最好的解決方案，並且它可能很明顯是最好的解決方案。

Answer 1

正如你已經閱讀了哈密頓路徑上的Wiki條目，你應該已經注意到找到哈密爾頓路徑是NP難（準確地說，你正在解決的是TSP - 但是這並沒有太大改變）。這一事實表明，貪婪算法不會爲您解決問題提供最佳解決方案。

如果你的貪心算法就像

獲取邊由降值/長度有序，

邊緣添加到路徑的建設，除非它

（一）創建一個週期

（b）造成度= 3的路徑中的功能於結構的節點

否則跳過它

這裏是最小的反例，我能想到的地方貪婪使得它失敗：

A B C D E F 
A 0 5 4 0 0 0 
B 5 0 5 0 4 0 
C 4 5 0 1 0 0 
D 0 0 1 0 5 4 
E 0 4 0 5 0 5 
F 0 0 0 4 5 0 

貪心算法ABCDEF找到路徑與21的總長度，而最佳路徑ACBEDF總長度爲22（其中更多長度相同）。

如果你的算法工作方式不同，它可能適用於這個例子，但是如果它是貪婪的，它仍然會有一個反例。發佈你的代碼，如果是這樣的話，你有興趣。