オブジェクトを 2 つのセットに分割するプログラムに取り組んでおり、各オブジェクトが他のすべてのオブジェクトとどの程度類似しているかを測定しており、それらを一致させる最適な方法を見つけたいと考えています。
セットが編集距離によって定義された単語と距離である場合、セット「this」、「is」、「a」、「test」と「and」、「this」、「is」の最適なマッチングは、 "best" の場合、"this" は "this" (スコア 0)、"is" は "is" (スコア 0)、"a" は "and" (スコア 0) と一致します。 2)、および "test" を使用した "best" (スコア 1)。
私は問題を、最大の二部マッチングのような問題を見つけることに減らしました。説明は次のとおりです。
エッジが整数の重みを持つ 2 部グラフが与えられた場合、(a) すべての頂点がセット内のエッジを 1 つだけ持ち、(b) このセット内の重みの合計が最大サイズになるエッジのセットを見つけます。
この問題がNP完全であるとは思わない（または、そうでなくても、アルゴリズムが非常に遅い場合）、答えをある程度近似する方法はありますか？
現在、最小ウェイト エッジを選択し、それとそれが接続するノードを削除して繰り返しますが、これは最適ではないようです。これをある種のフローの問題に減らすことを考えました (通常の 2 部マッチングで行うように) が、この場合は機能しません。