2

私は行列を持っています。行はオブジェクトで、列は目的です。各行はオブジェクトから目的までの距離を表します。

たとえば、3 つのオブジェクト O1 O2 O3 と 3 つの目的、OA OB OC があるとします。マトリックスは次のようになります。

   | OA OB OC
-------------
O1 | 2  4  6
O2 | 1  2  8
O3 | 3  5  3

ランダムなデータで埋めただけです。おそらく意味がありませんが、問題には役立つかもしれません。

私が期待する出力は次のとおりです: O2-OA、O1-OB、O3-OC

そのため、OA は O1 のベアラ対象ですが、OA はすでに OA によって使用されているため、次のものに進みます。

4

1 に答える 1

0

これは線形割り当て問題の例です。

Hungarian Algorithmを使用すると、O(N^3) 時間で最適な解を見つけることができます。詳細については、適切な Python 実装がここにあります。

ハンガリーのアルゴリズムがどのように機能するかを知りたい場合は、この講義は一見の価値があります。

速度が重要な場合、最適なソリューションをすばやく返すことができる方法(ただし、私が知る限り、そうすることが保証されているわけではありません) は、シミュレーテッド アニーリングに関連するいわゆるSoftassign アルゴリズムであり、反復的な行と列が含まれます。コストマトリックスの正規化。

最後に、もちろん、すべての割り当てが行われるまで最良の一致が順番に選択される貪欲な方法を使用して、次善の方法でこれを迅速に解決することは可能です。

于 2013-07-18T15:04:10.380 に答える