6

私の質問は、2 つのポイント セット A と B が与えられた場合、A の要素サイズは B の要素サイズを超えない場合、A の各ポイントに対応する B のポイントを見つける効率的な方法はありますか?一致は最小限ですか?B の各ポイントは、1 回しか使用できません。どうもありがとうございました!

4

1 に答える 1

6

はい、加重二部マッチングのハンガリー語アルゴリズムです。

A の要素と B の要素の間の各エッジについて、そのエッジの重みをそれらの間の距離とします。次に、重みの合計を最小化するハンガリー アルゴリズムを実行します。

合計実行時間は O(|A|^3) です。

于 2012-12-03T08:45:10.293 に答える