最優和有效的方法來解決多旅行推銷員的一個非常簡單的變種

我有兩個nx2矩陣的雙打，A & B包含x和y座標在每一行。我必須將A中的一個點與B中的一個點進行配對，以便根據歐式距離啓發式含義以最佳方式完成，假設A包含人員初始位置並且B包含寶藏位置。每個代理商都希望到達最近的寶藏，因爲所有的寶藏都是平等的。最優和有效的方法來解決多旅行推銷員的一個非常簡單的變種

這與多TSP稍有不同。我正在尋找最佳的算法來實現這不是一個矯枉過正的問題。天真的做法是從第一個代理開始，並開始配對代理寶藏，直到所有代理完成。一旦代理商與寶藏配對，寶藏就不再需要進一步分配。這是我現在在Matlab中實現的內容，但我願意提供更好的解決方案。

來源

2016-11-17 user_1_1_1

您描述的問題是**加權雙方匹配**問題（https://en.wikipedia.org/wiki/Matching_(graph_theory)#In_weighted_bipartite_graphs）。匈牙利語算法（https://en.wikipedia.org/wiki/Hungarian_algorithm）可能是您需要的 - 相當有效，而且不那麼複雜 –

絕對正確的答案。它解決了我的問題！ –

我認爲詳盡的O（n * n）是不可能的？使用記憶法，您可以通過一旦超出當前「最佳」的總距離中止來改進徹底的解決方案。

來源

2016-11-17 02:20:40

最優和有效的方法來解決多旅行推銷員的一個非常簡單的變種

回答

相關問題