割り当てアルゴリズム：どのようにこの状況を克服できますか？

Question

http://en.wikipedia.org/wiki/Assignment_problem

私が説明しようとしてるような状況は、次の講義からである：32:00 でhttp://www.youtube.com/watch?v=BUGIhEecipE教授は、この問題を説明し、しかし、彼はそれに任意の解決策を提示していない

は、私たちがしていると仮定以下の表を有する。行は列割当と値作業者が割り当て

3 1 1 4 
4 2 2 5 
5 3 4 8 
4 2 5 9 

を完了するのに必要な時間の量は、最初に、私は、各列の最小値を見つけ、そして他のすべての値からそれを減算し、労働者を表します同じ行。私は今、明らかな解決策は、労働者1である列に対して同じことを行うと、私は

0 0 0 0 
0 0 0 0 
0 0 1 2 
0 0 3 4 

次のような結果を得ることはタスク1タスク4、タスク3 2労働者、タスク2 3労働者、労働者1を取ります

しかし、プログラミング言語を使用すると、実際にはこれを見つけることができません。任意の選択をすると、たとえば

ワーカー1、タスク1 ワーカー2、タスク2 を選択することができます。残りのコストがゼロ以上であるため、何も選択できません。

私がティッキングプロセスを実行する場合は、基本的にすべての行とすべての列にチェックを入れなければならないため、テーブルの値は実際には変更されません。

私の質問は、この問題をどのように解決するかです。これを達成するのに役立つ方法はありますか？

また、割り当て問題を解決するための簡単な方法をお勧めしますか？この全体的なチッキングプロセスと最小/最大音を減算することは、低時間の複雑さではないようです。

私はアルゴリズムを実装しようとしていますが、このような状況に対処する必要があるかもしれないので、あなたはhttp://en.wikipedia.org/wiki/Hungarian_algorithmで「二部グラフの面でアルゴリズム」セクションを見れば、あなたは幅優先探索を使用して、方法を見ることができます最終的には、事前

Answer 1

で

おかげで間違っていることが判明しますマッチングを見つけるか、または行と列から引き算する定数を見つけます。あなたが引用する例では、それは一致を見つけるはずです。

私はそれが割り当てアルゴリズムにWikipediaの記事に引用され表示されていないが、メモリから、私はハンガリーのアルゴリズムは、この問題のためにかなり競争力のアルゴリズムだと思いました。