旅行推銷員，包括通過城市旅行

Question

傳統上，旅行推銷員問題與從城市到城市的距離從其起源一起工作。如果你可以忽略通過城市的旅行成本，而不是城市之間的旅行成本，那麼這種方法非常好。所以問題是，當通過一個城市的旅行費用不能被忽略時，如何找到最短的路線？

更好地解釋問題的最簡單的方法是採用貪心算法，例如最近鄰居從A開始，他先去B然後有2個選擇，一個去C去5成本，一去D去6成本。起初，C看起來像更便宜的選擇，但通過城市旅行去B需要3成本，並穿過城市去D只需要1.所以最後，採取D將是更便宜的選項。

在我創建一個包含每個城市之間的旅行費用的地圖之前，但正如您在示例中所看到的，在城市中旅行對真實旅行費用有很大影響。

有關如何解決此類問題的任何幫助？

編輯：首選邊緣可以選擇在起點（不通過城市旅遊）。 當推銷員進入城市時（不通過城市旅行）達到目的地。通過城市旅行的兩個方向的費用相同。

Answer 1

我的想法是用大小爲n = |鄰居（C）|的團體來替換每個城市節點C.將C的每個鄰居連接到集團中的一個節點。

集團內部的邊緣表示通過C的「過境」，並且它們具有相關的相應運輸成本。然後，您必須修改旅行銷售員的「目標」，以訪問每個城市派系的至少一個節點（而不是訪問每個派系） - 或者在訪問過之後將所有城市派系節點標記爲已訪問。

Answer 2

如果我們假設起始節點和結束節點都存在城市成本，那麼您需要將該成本添加到您希望包含在路上的頂點。如果一個頂點的成本爲n，其目標的成本爲m，代理將不得不穿過城市，則成本爲n + m。如果開始和結束節點包含在城市內部的交通成本中，那麼您需要將您的總旅行成本初始化爲出發城市的成本，並且您可以在每次穿過頂點時添加目標城市的成本。如果沒有，那麼你用0初始化成本，如果你不在最後一步，只會增加城市旅行成本。

如果代理只需訪問所有城市一次，那麼城市成本可以忽略算法，因爲它是一個常數，可以計算並添加到最優的頂點道路成本。