距離の合計が最小の3Dポイントのセットを別のセットにマッピングする

Question

指定されたのは、2組の3次元ポイント、ソースセットと宛先セットです。各セットのポイントの数は任意です（ゼロでもかまいません）。タスクは、すべての距離の合計が最小になるように、すべての宛先ポイントにソースポイントを1つまたはまったく割り当てないことです。ソースポイントがデスティネーションポイントよりも多い場合、追加のポイントは無視されます。

この問題には総当たり的な解決策がありますが、ポイントの数が多い可能性があるため、実行できません。この問題は、セットサイズが等しい2Dでは簡単だと聞きましたが、悲しいことに、これらの前提条件はここでは与えられません。

近似と厳密解の両方に興味があります。

編集：ハハ、はい、宿題のように聞こえると思います。実際、そうではありません。私は多数の車の位置を受け取るプログラムを書いており、それらをそれぞれの駐車セルにマッピングしようとしています。 ：）

Answer 1

頭のてっぺんから、空間的な並べ替えとシミュレートされたアニーリング。

スペースのグリッド＆amp;セットを空間セルにソートします。

各セル内のO（NM）問題を解決し、次にセル近傍内などで解決して、トライアルマッチングを取得します。

最後に、多くのサイクルのシミュレーテッドアニーリングを実行します。このサイクルでは、マッチをランダムに変更して、近くのスペースを探索します。

これは発見的であり、必ずしも最良ではありませんが、適切な答えを取得します。また、最初のグリッドソートにより、かなり効率的です。

Answer 2

この問題に対処する方法の1つは、古典的な割り当て問題として扱うことです。 http：// en.wikipedia.org/wiki/Assignment_problem

ポイントをグラフの頂点として扱い、エッジの重みはポイント間の距離です。最速のアルゴリズムは、最大マッチングを探している（そして、あなたの場合のように最小ではない）こと、および重みが負ではないことを前提としているため、重みを再定義して、たとえば：

weight(A, B) = bigNumber- distance(A,B)

where bigNumber は最長距離よりも大きいです。

明らかに、2部グラフになります。次に、最大加重2部一致の標準アルゴリズムの1つを使用します（Web上の多くのリソース、たとえば http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf またはウィキペディアの概要： http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings ）この方法で終了します- O（NM max（N、M））アルゴリズムを使用します。NとMはポイントセットのサイズです。

Answer 3

私はあなたの質問には本当に答えがありませんが、次のトピックを調べることをお勧めします。 （これについてはほとんど知りませんが、以前にStack Overflowで遭遇しました。）

• 最近傍検索
• k d-tree

これが少し役立つことを願っています。