7

だから私は、ハンガリーの方法が必要とする伝統的なコストを持たない仕事の割り当ての問題を抱えています.

例えば：

I have 3 workers - A, B and C
I have 5 jobs -  1, 2, 3, 4 and 5

各ワーカーには、次のように実行できるジョブのリストがあります。

worker A can work on job 1, 2, 5
worker B can work on job 1, 2
worker C can work on job 1

最終的な結果は (費用がかからないため)、達成できる課題の最大数です。この例では、最大 3 つの課題を達成できます。

worker A on job 5
worker B on job 2
worker C on job 1

ハンガリーの方法はこれを解決する良い方法ですか？「ダミー」コストだけを使用する必要がありますか? 仕事の好みの指標をコストとして使用することを考えていました。これは良い考えですか？

4

4 に答える 4

6

ハンガリーのアルゴリズムをここで機能させることもできますが、Hopcroft–Karp のような重み付けされていない最大 2 部マッチングのアルゴリズムの方が高速です。

于 2013-05-09T14:35:02.333 に答える
5

できるジョブにコスト -1 を割り当て、その他はゼロにします。

次に、ハンガリー語のアルゴリズムを実行すると、答えが返されます (実際には -answer が返されます)。

オーバーフローを引き起こす可能性があります (ハンガリー語を非常に注意深く実装しない限り)。

実際、これは 2 部グラフでの最大マッチングであり、この問題を解決する方法はたくさんあります。wiki ページを参照してください。

http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs

PS:Hopcroft–Karp アルゴリズムはハンガリー語よりも高速であり、単純でもあります。試してみる価値があります。一部の複雑な方法はこれら 2 つよりも高速ですが、これらのアルゴリズムを最初から学習することはお勧めしません。

PSS: stackoverflow のあなたの ID は、この問題を解決する方法です。それはネットワークの流れです。これは、最短引数パス (sap) と呼ばれます。参照: http://coral.ie.lehigh.edu/~ted/files/ie411/lectures/Lecture11.pdf

于 2013-05-09T14:22:22.987 に答える
2

ダミーコストでうまくいくはずです。できる仕事にはコスト 1 を割り当て、できない仕事には無限のコスト (システムで許可されている場合) を割り当てます。ハンガリーのアルゴリズムは、すべてのタスクの総コストを最小限に抑えるように設計されているため、自然に物事を把握できます。彼らの仕事の好みが何であるかを説明する必要はありません。それがアルゴリズムの仕事です。

于 2013-05-09T14:17:15.107 に答える
1

ハンガリーのアルゴリズムで答えが得られますが、無限コストを使用しないでください。比較できないためです(自分でコストを比較(infinity + infinity)しinfinityない限り)。

A: 1, 2, 3

B: 1

C: 1

行列形式:

  1   2   3

A 1   2   3

B 1   inf inf

C 1   inf inf

あなたのコンピュータは と をどのように比較できます1, inf, infか2, 1, inf?

代わりに、割り当てられないことが保証されるほど大きなコストを使用します (オーバーフローには注意してください)。

于 2013-05-09T14:21:16.417 に答える