問題タブ [hungarian-algorithm]

ハンガリーのアルゴリズムを適切に実装しようとしていますが、配列内のすべてのゼロをカバーする最小行数を見つける方法に固執しています。

また、後でいくつかの計算を行うために、これらの行を知る必要があります

ここに説明があります：

http://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf

ステップ3でそれは言う

マトリックス内のすべてのゼロをカバーするために、できるだけ少ない行を使用してください。これを行う簡単なルールはありません-基本的に試行錯誤です。

試行錯誤は計算の観点から何を意味しますか？たとえば、5行5列の2D配列がある場合、

最初の行はすべてのゼロ、最初と2番目、最初の行と最初の列などをカバーできます。組み合わせが多すぎます。

これより効率的なものはありませんか？

前もって感謝します

Java でハンガリー語のアルゴリズムを実装しようとしています。NxN コスト マトリックスがあります。私はこのガイドを順を追って進めています。したがって、costMatrix[N][N] と、カバーされた行とカバーされた列を追跡する 2 つの配列があります - rowCover[N]、rowColumn[N] (1 はカバーされていることを意味し、0 はカバーされていないことを意味します)

最小行数で 0 をカバーするにはどうすればよいですか? 誰かが私を正しい方向に向けることができますか?

ヘルプ/提案をいただければ幸いです。

Javaでハンガリーのアルゴリズムを実装しようとしています。NxNコストマトリックスがあります。私はこのガイドを段階的にたどっていて、ステップ9に到達しました-

「各行または列で1つだけが選択されるように、ゼロのセットを選択して一致するものを選択してください。」

私はすでに0の行列を持っています。私はこれを理解しようとしていましたが、私のために働いていたのはブルートフォース方式だけでした。

また、最初に遭遇した0を選択し、その列と行を削除して繰り返します。ただし、この方法は機能しません。

トリックや方法はありますか？それほど複雑ではないものはありますか？任意の提案をいただければ幸いです。

ありがとう

C++ でハンガリー語アルゴリズムの実装を作成しました。この実装は、多くの場合に非常にうまく機能します。ただし、アルゴリズムの 1 つのステップの実装が間違っていると私が信じている (そしてそれは真実である) ため、私のアルゴリズムがまったく機能しない場合があります。

私の実装では、配列を入力として取りX、アルゴリズムのステップを実行して、最終的な割り当てを生成します。

アルゴリズムの手順は wiki で見つけることができます: Hungarian Algorithm

ステップ 3 では、次のコストの配列があります (ワーカーは行で表され、ジョブは列で表されます)。

そしてそれは言います

ただし、これの正しい実装が何であるかはわかりません。どうすればできるだけ多くのタスクを割り当てることができますか? 選択はランダムになりますか？次に、選択がランダムである場合、最初の仕事をする最初の労働者、4 番目の仕事をする 2 番目の労働者、2 番目の仕事をする 4 番目の労働者を選ぶことができます。したがって、2 番目のワーカーは除外されます。ただし、ウィキペディアでは、著者は別のアプローチを取りました。3 番目のワーカーは最初のジョブを実行し、2 番目のワーカーは 2 番目のジョブを実行し、4 番目のワーカーは 2 番目のジョブを実行する必要があります。したがって、最初のワーカーは除外されます。

このようなランダムなアクションを行う際の問題は、次の場合です。

アルゴリズムを実行し、入力に対して算術演算を実行している間、できるだけ多くのタスクをワーカーに割り当てる前に、次のコスト マトリックスがあるとします。

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 番目のワーカーに割り当てるために戻ります。

私の実装はこのロジックに従いますが、すべてのケースを解決できるわけではありません。

たとえば、次のケースを考えてみましょう。

最初のワーカーは 4 つのジョブ、2 番目のワーカーは 4 つ、3 つ目のワーカーは 2 つ、4 つ目のワーカーは 2 つのジョブを引き受けることができます。つまり、割り当てを実行して続行するには、1 つのジョブしか引き受けることができないワーカーが少なくとも 1 人必要になるため、この実装では割り当てを行いません。テーブルを再スキャンします。では、この場合はどうすればよいでしょうか。恣意的な割り当ては悪いことです。残念ながら、その講義では何も提案されていません。次のことしか思いつきませんでした。

各ワーカーには、そのワーカーに割り当てることができるタスクの量を示す値を持つカウンターがあります。その行にはいくつのゼロがありますか? それがカウンターの値です。次に、最小のカウンターを持つワーカーに任意のタスクを割り当て始めます。したがって、この場合、各ワーカーのカウンターの配列には次の値が含まれます。

たとえば、私は 3 番目の労働者を選び、任意に最初の仕事を彼に割り当てます。新しいカウンターは次のようになります。

次に、4 番目のワーカーを選択し、彼が利用できる唯一の割り当て (2 番目のジョブ) を実行します。新しいカウンターは次のようになります。

次に、最初のワーカーまたは 2 番目のワーカーのいずれかを選択できます。私は最初の労働者に任意の割り当てを行い、彼に 3 番目の仕事を与えます。カウンターは

最後に、最初の仕事に 4 番目の割り当てを与えます。

したがって、最終的な割り当ては次のとおりです。

良いアプローチのように思えますが、この方法が機能しないという特殊なケースがあるのではないかと心配しています。このアプローチがすべてのケースで機能するかどうかを確認するにはどうすればよいですか? また、機能しない場合は、どのアプローチが問題を完全に解決しますか?

前もって感謝します

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

例えば：

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

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

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

ハンガリーのアルゴリズムは、代入問題を多項式時間で解きます。ワーカーとタスク、および各ワーカーをタスクに割り当てるコストを含む n×n 行列が与えられると、コストを最小化する割り当てを見つけることができます。

コストが最大になる選択肢を見つけたいですか? ハンガリー語または同様の方法を使用してそれを行うことはできますか? それとも、これは指数関数的にのみ行うことができますか?

次のように、ハンガリー方式の最小行数でゼロをカバーする手順を実行しようとしています。

1. 割り当てられていないすべての行にチェックを入れます。
2. チェックされた行にゼロがある場合は、対応する列にチェックを入れます。
3. チェックされた列内で、割り当てがある場合は、対応する行にチェックを入れます。
4. チェックされていない各行とチェックされている列の上に線を引きます。
5. 割り当てられていない行ごとに繰り返します。
6. 次に、シータ (カバーされていない最小値) を見つけます。

問題は、私がそれを行うとき、まだゼロが発見されていることです! Theta がゼロになり、無限ループに入ります!

たとえば、次の行列 25 x 25 を使用すると、次のようになります。

1 5 5 2 3 1 2 3 2 4 5 2 3 1 5 5 2 3 1 5 1 4 3 2 5

5 5 3 2 3 2 5 1 4 3 2 5 3 2 4 5 2 5 2 1 1 4 1 2 5

5 1 4 3 2 5 1 1 4 1 2 5 2 2 3 4 1 4 5 3 2 4 5 2 5

1 1 4 1 2 5 3 2 4 5 2 5 5 5 1 5 1 5 5 2 2 3 4 1 4

3 2 4 5 2 5 2 2 3 4 1 4 5 4 2 1 3 2 5 5 5 1 5 1 5

2 2 3 4 1 4 5 5 1 5 1 5 5 5 2 5 5 1 4 5 4 2 1 3 2

5 5 1 5 1 5 5 5 3 2 3 2 1 5 5 1 5 1 5 5 5 2 5 5 1

5 4 2 1 3 2 5 1 4 3 2 5 5 5 4 2 1 3 2 5 1 4 3 2 5

5 5 2 5 5 1 1 1 4 1 2 5 1 5 5 2 5 5 1 1 1 4 1 2 5

2 4 5 3 4 2 3 2 4 5 2 5 2 2 4 5 3 4 2 3 2 4 5 2 5

2 2 5 5 1 3 2 2 3 4 1 4 2 2 2 5 5 1 3 2 2 3 4 1 4

4 1 5 4 5 3 5 5 1 5 1 5 5 4 1 5 4 5 3 5 5 1 5 1 5

5 1 4 3 2 5 3 2 4 5 2 5 5 5 1 4 3 2 5 3 2 4 5 2 5

1 1 4 1 2 5 2 2 3 4 1 4 1 1 1 4 1 2 5 2 2 3 4 1 4

3 2 4 5 2 5 5 5 1 5 1 5 4 3 2 4 5 2 5 5 5 1 5 1 5

2 2 3 4 1 4 5 4 2 1 3 2 1 2 2 3 4 1 4 5 4 2 1 3 2

5 5 1 5 1 5 5 5 2 5 5 1 2 5 5 1 5 1 5 5 5 2 5 5 1

5 1 4 3 2 5 3 5 1 4 3 2 5 3 5 2 2 3 5 2 2 3 2 5 3

3 4 1 4 1 1 1 1 1 4 1 2 5 5 1 4 3 2 5 1 4 1 2 5 2

1 5 5 2 3 1 5 3 2 4 5 2 5 1 1 4 1 2 5 2 4 5 2 5 5

5 5 3 2 3 2 2 2 2 3 4 1 4 3 2 4 5 2 5 2 3 4 1 4 3

5 1 4 3 2 5 2 5 5 1 5 1 5 2 2 3 4 1 4 5 1 5 1 5 5

1 1 4 1 2 5 2 5 4 2 1 3 2 5 5 1 5 1 5 4 2 1 3 2 1

3 2 4 5 2 5 1 5 5 2 5 5 1 5 4 2 1 3 2 5 2 5 5 1 3

2 2 3 4 1 4 1 2 4 5 3 4 2 5 5 2 5 5 1 4 5 3 4 2 2

ハンガリーの方法からステップ 1 と 2 として行と列の最小値を差し引いた後、次のようになります。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 4 0 4 0 4 4 4 1 4 4 0 1 4 4 0 4 0 4 4 4 1 4 4 0

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

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

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

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

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

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

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

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

次に、割り当てを行うと、25ではなく23の割り当てがあるため、上記の手順に基づいてゼロをカバーする前述の手順を実行すると、次のようになります。

太字のセルは、上記の手順に従ってカバーされたセルです。

カバーされていないゼロがまだあり、次に選択されるときに無限ループが発生することに注意してください。

私を助けてください。

前もって感謝します

現時点ではn、ユーザー数のデータベースがあります。そして、これらすべてのユーザーは、互換性スコアのように、他のすべてのユーザーに関連付けられたスコアを持っています。これらのスコアは対称的です。したがって、user1 が user2 とのスコアが 10 の場合、user2 は user1 とのスコアが 10 になります。

すべてのユーザーの合計スコアを最大化しながら、すべてのユーザーを互いに一致させる方法を探しています。

これは明らかにハンガリーのアルゴリズムとして知られていますか? 最小スコアではなく最大スコアを探していますが。

Railsでこれを行うクリーンな方法はありますか? 私はどこでも見ましたが、何も見つかりませんでした。