5

アイテム ad は、すべてのアイテムのペア間の距離の合計が最小になるように、アイテム 0 ～ 3 とペアにする必要があります。たとえば、次のマトリックスは、最初のグループの各アイテムと対応するグループのアイテム間の距離を表すことができます。

[[2, 2, 4, 9],
 [4, 7, 1, 1],
 [3, 3, 8, 3],
 [6, 1, 7, 8]]

これは、距離 'a' -> '0' が 2、from 'a' -> '1' が 2、from 'a' -> '2' が 4、'a' -> '3 であることを意味するはずです。 ' は 9 です。'b' -> '0' からは 4 などです。

合計距離が最小になるように、各文字を数字と一致させることができるアルゴリズムはありますか? 例えば：

[('a', 1), ('b', 3), ('c', 0), ('d', 2)]

合計距離が 2 + 1 + 3 + 7 = 13 の合法的な解決策になります。現実の世界には 4 つをはるかに超えるアイテムを含むグループがあるため、すべての可能な組み合わせを力ずくでテストすることはできません。

4

2 に答える 2

9

これは二部グラフの古典的な最適化タスクであり、ハンガリーのアルゴリズム/メソッドで解決できます。

于 2011-08-17T12:30:46.193 に答える
1

これは、加重二部マッチング問題のインスタンスとして扱うことで解決できます。アイデアは、要素 ad と 0-3 をグラフのノードとして扱うことです。ここで、文字の付いた各ノードは、重みが行列によって指定されたエッジで番号付きの各ノードに接続されます。このグラフを作成したら、各ノードが多くても 1 つのエッジにのみ接続されるように、文字と数字が一致する一連のエッジを見つけます。このようなエッジのセットはマッチングと呼ばれ、距離を最小化したいので、最小コストのマッチングを探しています。

yi_H が指摘しているように、この問題はよく研究されており、多くの優れた多項式時間アルゴリズムがあります。Hungarian Algorithm は、おそらくこの問題の最も有名なアルゴリズムですが、その後、漸近的に (または実質的に) 高速なアルゴリズムが発明されました。

この問題は、多くの状況で発生するため、覚えておく価値があります。あるグループの項目を別のグループの項目に割り当てる必要がある場合はいつでも、問題を 2 部一致に減らすことができるかどうかを確認してください。もしそうなら、最初の問題に対する迅速な解決策をほぼ確実に見つけたことになります。

于 2011-08-17T16:40:58.437 に答える