2D平面内のポイントの複数のリストを並べ替えて、各リストの対応するポイント間の距離が最小になるようにするアルゴリズムが必要です。
つまり、同じ長さの2つのリストの場合、最初のリストの最初のポイントは2番目のリストの最初のポイントまでの距離が最小になり、最初の2番目のポイントは2番目のリストの2番目のポイントまでの距離が最小になります。
私が最初に考えたのは、x座標とy座標の平均で単純に並べ替えることでしたが、それは完全に正確ではないように感じます。
質問する
1015 次
1 に答える
1
隣接するポイント間の合計距離を最小化しようとしている場合、これは並べ替えタスクではありません。
代わりに、 2 次元空間でハミルトニアン パスの問題を解こうとしているようです。これは、点間の任意の距離に対して NP 完全です。あなたの場合、ユークリッド距離への制限でさえNP-completeですが、近似アルゴリズムがあります。https://www.ads.tuwien.ac.at/teaching/ws10/AlgGraphen/ag3-2x2.pdfを参照してください。一般に、ゲーデル賞を受賞した Sanjeev Arora の業績により、ユークリッド TSP は多項式時間で近似できます。
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.6765
ユークリッド巡回セールスマン問題を検索すると、この問題の解を近似する方法を議論している他の科学論文へのリンクも表示されます。
于 2013-03-14T01:38:21.103 に答える