C++ でハンガリー語アルゴリズムの実装を作成しました。この実装は、多くの場合に非常にうまく機能します。ただし、アルゴリズムの 1 つのステップの実装が間違っていると私が信じている (そしてそれは真実である) ため、私のアルゴリズムがまったく機能しない場合があります。
私の実装では、配列を入力として取りX、アルゴリズムのステップを実行して、最終的な割り当てを生成します。
アルゴリズムの手順は wiki で見つけることができます: Hungarian Algorithm
ステップ 3 では、次のコストの配列があります (ワーカーは行で表され、ジョブは列で表されます)。
そしてそれは言います
Initially assign as many tasks as possible then do the following
ただし、これの正しい実装が何であるかはわかりません。どうすればできるだけ多くのタスクを割り当てることができますか? 選択はランダムになりますか？次に、選択がランダムである場合、最初の仕事をする最初の労働者、4 番目の仕事をする 2 番目の労働者、2 番目の仕事をする 4 番目の労働者を選ぶことができます。したがって、2 番目のワーカーは除外されます。ただし、ウィキペディアでは、著者は別のアプローチを取りました。3 番目のワーカーは最初のジョブを実行し、2 番目のワーカーは 2 番目のジョブを実行し、4 番目のワーカーは 2 番目のジョブを実行する必要があります。したがって、最初のワーカーは除外されます。
このようなランダムなアクションを行う際の問題は、次の場合です。
アルゴリズムを実行し、入力に対して算術演算を実行している間、できるだけ多くのタスクをワーカーに割り当てる前に、次のコスト マトリックスがあるとします。
2 2 0 3
6 1 6 0
0 0 6 1
0 3 5 3
3 番目のジョブを最初のワーカーに割り当て、4 番目のジョブを 2 番目のワーカーに割り当て、最初のジョブを 3 番目のワーカーに割り当てることをランダムに選択した場合、4 番目のワーカーは除外されます。しかし、アルゴリズムが正しく機能するためには、 を割り当てる必要がありas many jobs to workers as possibleます。これはここにありますか？いいえ、最初のジョブを 3 番目のワーカーに割り当てる代わりに、最初のジョブを 4 番目のワーカーに割り当てると、2 番目のジョブを 3 番目のワーカーに割り当てることができるため、アルゴリズムはできるだけ多くのジョブをワーカーに割り当てるだけでなく、しかし、それは最適な結果を見つけるでしょう。
結論: ランダムな割り当てを行うのは良い方法ではありません。
これについて少し調べてみたところ、次の講義を見つけました。
http://www.youtube.com/watch?v=BUGIhEecipE
この講義で教授は、できるだけ多くのタスクを割り当てるという問題に対して、別のアプローチを提案しています。彼によると、行または列にゼロが1つだけある場合、割り当てを行います。したがって、最初の行から始めて、最初の行にゼロが1つしかないかどうかを確認し、そうであれば割り当てを行います。それ以外の場合は、その行を無視して 2 番目の行に移動し、代入によってすべてのゼロがカバーされるまで、テーブルを再スキャンして同じことを繰り返します。
このアプローチに従うことで、前のケースが解決されることがわかります。3 番目のジョブを 1 番目のワーカーに割り当て、4 番目のジョブを 2 番目のワーカーに割り当てます。3 番目のワーカーは 2 つのジョブを引き受けることができるので、しばらく無視します。最初のジョブを 4 番目のワーカーに割り当てます。 2 番目のジョブを 3 番目のワーカーに割り当てるために戻ります。
私の実装はこのロジックに従いますが、すべてのケースを解決できるわけではありません。
たとえば、次のケースを考えてみましょう。
0 0 0 0
0 0 0 0
0 0 4 9
0 0 2 3
最初のワーカーは 4 つのジョブ、2 番目のワーカーは 4 つ、3 つ目のワーカーは 2 つ、4 つ目のワーカーは 2 つのジョブを引き受けることができます。つまり、割り当てを実行して続行するには、1 つのジョブしか引き受けることができないワーカーが少なくとも 1 人必要になるため、この実装では割り当てを行いません。テーブルを再スキャンします。では、この場合はどうすればよいでしょうか。恣意的な割り当ては悪いことです。残念ながら、その講義では何も提案されていません。次のことしか思いつきませんでした。
各ワーカーには、そのワーカーに割り当てることができるタスクの量を示す値を持つカウンターがあります。その行にはいくつのゼロがありますか? それがカウンターの値です。次に、最小のカウンターを持つワーカーに任意のタスクを割り当て始めます。したがって、この場合、各ワーカーのカウンターの配列には次の値が含まれます。
4
4
2
2
たとえば、私は 3 番目の労働者を選び、任意に最初の仕事を彼に割り当てます。新しいカウンターは次のようになります。
3
3
0
1
次に、4 番目のワーカーを選択し、彼が利用できる唯一の割り当て (2 番目のジョブ) を実行します。新しいカウンターは次のようになります。
2
2
0
0
次に、最初のワーカーまたは 2 番目のワーカーのいずれかを選択できます。私は最初の労働者に任意の割り当てを行い、彼に 3 番目の仕事を与えます。カウンターは
1
0
0
0
最後に、最初の仕事に 4 番目の割り当てを与えます。
したがって、最終的な割り当ては次のとおりです。
0 0 0 *
0 0 * 0
* 0 4 9
0 * 2 3
良いアプローチのように思えますが、この方法が機能しないという特殊なケースがあるのではないかと心配しています。このアプローチがすべてのケースで機能するかどうかを確認するにはどうすればよいですか? また、機能しない場合は、どのアプローチが問題を完全に解決しますか?
前もって感謝します