問題タブ [hungarian-algorithm]

私は一連のホストと一連のタスクを持っています。
各ホストには cpu、mem、およびタスクの容量があり、各タスクには cpu、mem の要件があります。
各ホストはレイテンシ クラスに属し、特定のレイテンシ値で他のホストと通信できます。
各タスクは、特定の値以下のレイテンシで別のタスクと通信する必要がある場合があります。
私の問題入力の例を次の画像に示します。 ここで、タスク t1 はタスク t2、t3、および t4 とそれぞれ 3、3、および 5 以下のレイテンシで通信する必要があり、ホスト h1 はレイテンシ クラス 3 に属し、h2、h3、および h4 とレイテンシ 2、5、および 5 で通信します。それぞれ3。
Hungarian/munkres アルゴリズムを使用してこの問題を解決しようと考えていましたが、コスト関数を適切に設定するにはどうすればよいですか? これを解決するためのより良い割り当てアルゴリズムはありますか?
ありがとう。

ハンガリーのアルゴリズムを解決する関数を実装しようとしていますが、アルゴリズムについて誤解しているものがあると思います。

テスト目的で、動作するはずのGoogleのこのC++コードを使用しています。

しかし、この 14x11 行列をテストすると、解決できないと表示されます。

[ 0 0 0 0 0 0 0 0 0 ]

[ 53 207 256 207 231 348 348 348 231 244 244 ]

[ 240 33 67 33 56 133 133 133 56 33 33 ]

[ 460 107 200 107 122 324 324 324 122 33 33 ]

[ 167 340 396 340 422 567 567 567 422 442 442 ]

[ 167 367 307 367 433 336 336 336 433 158 158 ]

[ 160 20 37 20 31 70 70 70 31 22 22 ]

[ 200 307 393 307 222 364 364 364 222 286 286 ]

[ 33 153 152 153 228 252 252 252 228 78 78 ]

[ 93 140 185 140 58 118 118 118 58 44 44 ]

[ 0 7 22 7 19 58 58 58 19 0 0 ]

[ 67 153 241 153 128 297 297 297 128 39 39 ]

[ 73 253 389 253 253 539 539 539 253 36 36 ]

[ 173 267 270 267 322 352 352 352 322 231 231 ]

配列を作成するための C++ コード: (誰かが私が提供した C++ の例を使用してテストしたい場合)

int r[14*11] ={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 53, 207, 256, 207, 231, 348, 348, 348, 231, 244 , 244, 240, 33, 67, 33, 56, 133, 133, 133, 56, 33, 33, 460, 107, 200, 107, 122, 324, 324, 324, 122, 33, 33, 167, 340 、396、340、422、567、567、567、422、442、442、167、367、307、367、433、336、336、336、433、158、158、160、20、37、20、31 、70、70、70、31、22、22、200、307、393、307、222、364、364、364、222、286、286、33、153、152、153、228、252、252、252 , 228, 78, 78, 93, 140, 185, 140, 58, 118, 118, 118, 58, 44, 44, 0, 7, 22, 7, 19, 58, 58, 58, 19, 0, 0 , 67, 153, 241, 153, 128, 297, 297, 297, 128, 39, 39, 73, 253, 389, 253, 253, 539, 539, 539, 253, 36, 36, 173, 267, 270 、267、322、352、352、352、322、231、231};

実装を実行してゼロの数を減らすと（最小行数でカバーできるようになります-上部にあるwikihowのリンクのステップ9-）、一意の0の組み合わせを見つける必要がある次のマトリックスが得られます行と列。

問題は、列 10 と 11 (太字のもの) にはそれぞれ 1 つの 0 しかなく、同じ行にあるため、解決できないことです。

行 1 : [ 240 140 225 140 206 339 339 339 206 215 215 0 0 0 ]

行 2 : [ 254 0 37 0 43 58 58 58 43 38 38 67 67 67 ]

行 3 : [ 0 107 158 107 151 206 206 206 151 182 182 0 0 0 ]

行 4 : [ 0 253 245 253 304 235 235 235 304 402 402 220 220 220 ]

行 5 : [ 300 27 56 27 11 0 0 0 11 0 0 227 227 227 ]

行 6 : [ 300 0 145 0 0 230 230 230 0 284 284 227 227 227 ]

行 7 : [ 80 120 188 120 176 269 269 269 176 193 193 0 0 0 ]

行 8 : [ 207 0 0 0 151 143 143 143 151 96 96 167 167 167 ]

行 9 : [ 229 9 95 9 0 110 110 110 0 159 159 22 22 22 ]

行 10 : [ 147 0 40 0 148 221 221 221 148 171 171 0 0 0 ]

行 11 : [ 240 133 203 133 187 282 282 282 187 215 215 0 0 0 ]

行 12 : [ 189 3 0 3 94 58 58 58 94 192 192 16 16 16 ]

行 13 : [ 367 87 36 87 153 0 0 0 153 379 379 200 200 200 ]

行 14 : [ 194 0 82 0 11 115 115 115 11 112 112 127 127 127 ]

この方法に何らかの制限はありますか? それとも、アルゴリズムの実装が悪いのは私だけですか? この場合、「動作するはずの」例も動作しないのはなぜですか?

任意の提案をいただければ幸いです。または、ゼロをカバーする最小行数を見つけるのに役立つトリックや提案を知っている場合は、お知らせください。

前もって感謝します、

解決すべき問題があり、最適な解決策が見当たりません:/ 問題は次のとおりです。

n人の労働者とk人の仕事があります。各仕事は指定された数の労働者によって行われ、各労働者にはそれぞれの仕事の幸福度があります。労働者ができるだけ幸せになるように、仕事のスケジュールを立てなければなりません。したがって、int [n、k] (k >= n) の配列 a1 があります。i 番目の行の k 番目の列には、k 番目のジョブに対する i 番目のワーカーの優先度 (0 から 10 までの数字) が含まれます。また、int[k] の配列 a2 もあります。ここで、i 番目の要素には、その仕事をする人の数が含まれています。各労働者は同じ数の仕事をすることになっています。n >= max(a2) であることを知っているので、幸福の可能な最大の合計を見つけなければなりません。私の解決策は、再帰を使用することです。ジョブの最初の組み合わせの最初のワーカーを選択し、合計に設定を追加し、合計が既に見つかった最大値よりも大きいかどうかを確認し、大きい場合は次のワーカーに進みます。戻ったら、最初のワーカーなどの次の組み合わせを確認します。これは、少量のワーカーには問題なく機能しますが、より大きな問題を解決するには計算の複雑さが高くなります。より良い解決策のアイデアはありますか?

PS。別のサイトのガイがハンガリー語アルゴリズムの使用を勧めてくれましたが、n == k であると想定されており、n <= k で動作させる方法がわかりません。

PS2 例:

Hungarian/Kuhn-Munkres アルゴリズムの PL/SQL 実装はどこにありますか? 私が見つけることができるオンラインはないようです。

N 個の仕事と、それらの仕事をする K 人の労働者が与えられたとしましょう。ただし、2 人の従業員が必要な仕事もあれば、1 人で済む仕事もあります。また、従業員はすべての仕事を行うことはできません。たとえば、労働者 1 は仕事 1、2、および 5 を実行できますが、仕事 3 および 4 は実行できません。また、仕事 1 を実行するために労働者 1 を雇う場合、すでに支払いを済ませているため、仕事 2 および 5 を実行してもらいます。

たとえば、5 つのジョブと 6 つのワーカーがあるとします。ジョブ 1、2、および 4 では 2 人の男性が必要ですが、ジョブ 3 および 5 では 1 人で十分です。そして、これがすべての労働者ができる仕事と彼が必要とする賃金のリストです.

少しの計算と論理的思考の後で、労働者 1、3、4、5 を雇う必要があると結論付けることができます。つまり、支払う必要のある最低賃金は、1000 + 1500 + 2500 + 1500 = 5500 ドルです。

しかし、その量を出力する効率的なアルゴリズムをどのように見つけることができるのでしょうか? これはどういうわけかハンガリーのアルゴリズムを思い出させますが、これらの追加の制約により、私はそれを適用することができません.

マトリックスのいずれかの行にゼロが含まれている場合、上記のエラーがスローされます。どうすれば修正できますか？

これは、Python のコードの一部です。

Ubuntu で次のコマンドを使用して、ライブラリ munkres をインストールしました。

sudo apt-get install python-munkres