旅行推銷員啓發式

Question

我目前的想法是： 從0開始，並將其與最近的點連接起來。對於所有剩餘的節點，將其插入所有可能的位置並保持成本最低的配置。

所以我開始與點0最接近的節點指向0是點1

所以我現在有0-> 1 - > 0

對於點2（以及所有剩餘的節點）我將檢查在新的節點可能是所有可能性：

- > 0 - > 1 - > 2

0 - > - > 1 - > 0

0 - > 1-> 2 - > 0

在這裏，我發現

0 - > 1 - > 2 - > 0具有至少總歐氏距離，從而是配置我會繼續。

我將繼續爲我的其餘節點使用此邏輯。

有沒有一種簡單的方法來實現這個在c + +？我目前的想法可能是鏈接列表將是一個好主意，但我希望能夠使用載體，如果可能的話。有沒有人有任何提示如何解決這個問題？

Answer 1

你有沒有想過使用有向圖，然後實現dijkstra算法。在一個有向圖中，dijkstra算法會爲您提供從起始節點到圖中所有其他節點的最短路徑，而不僅僅是您想要的幾個節點。