algorithm - 2 組のポイントをリンクする最小コストを見つける方法

Question

点 S と V の 2 つのセットを取得しました。どちらもサイズ n です。2 つのセットをリンクして、S のすべてのポイントが V の 1 つのポイントだけにリンクするようにします。2 つのポイントをリンクするコストは、2 つのポイント間のユークリッド距離として定義されます。あるはずです！可能なリンク方法。では、最小コストの方法を見つけるにはどうすればよいでしょうか。（効率的な方法で）

Answer 1

これは割り当ての問題です。ハンガリーの方法で解決できます。pythonにはこれの実装があります。また、任意の線形計画法ソルバーを使用して問題を解くこともできます。LP の定式化では、常に整数解が得られます。