旅行推銷員的提示

我正在開發一個應用程序，我必須面對旅行推銷員的問題。我做了我自己的嘗試，但是我得到的時間非常糟糕。我正在尋找一些優化解決方案，但是我沒有弄清楚什麼。旅行推銷員的提示

任何提示開始優化這個過程或algorythms？我目前的算法是基本的回溯算法。

My圖表滿足所有在TSP圖形（無方向性，simetric，CONEX）典型的條件......

感謝

來源

2012-02-27 FrioneL

很難優化你看不到的東西。你目前的算法做什麼？ – Nanne 2012-02-27 09:14:30

對不起。我現在的算法是基本的回溯算法，所以我向所有節點跳躍...但是當實際路徑比我已經保存的最小路徑更重時，我會對其進行預測。 – FrioneL 2012-02-27 09:16:22

你知道距離嗎？他們是否遵守三角形不等式（也就是說，從a到c的距離最多是從a到b的距離加上從b到c的距離）？或者他們完全是武斷的？ – templatetypedef 2012-02-27 10:21:42

如果你的指標滿足三角不等式我可以建議你去尋找christofides算法。它有一個保證在最佳解決方案之內。國際海事組織關於christofides算法的困難部分是完美的匹配。如果你不關心保證，你可以尋找google map tsp solver。它將蟻羣優化用於大型路線。如果你想真正快速求解，精度較低，你可以尋找一個怪物曲線，例如希爾伯特曲線或摩爾曲線。

來源

2012-02-27 10:45:25 Bytemain

謝謝。這是一個android gps應用程序，我必須訪問一些點...也許我必須使用較少的準確性，因爲其他人可能會消耗大量電池... – FrioneL 2012-02-27 11:09:14

旅行推銷員的提示

回答

相關問題