3

ここでのすべての回答、ウィキペディアとウィキハウ、インド人の講義、およびその他の情報源を読みましたが、彼らの言っていることを理解し、そのように実装したと確信しています。しかし、これらすべての説明が明らかに誤りであるという声明について、私は混乱しています。

彼らは皆、行列のゼロを最小数の行でカバーするように言い、それが N に等しい場合 (つまり、すべての行とすべての列にゼロがある)、ゼロの解があり、完了です。しかし、私はこれを見つけました：

    a  b  c  d  e

A   0  7  0  0  0
B   0  8  0  0  6 
C   5  0  7  3  4 
D   5  0  5  9  3 
E   0  4  0  0  9

すべての行と列にゼロがあり、5 行未満でゼロをカバーする方法はありませんが、明らかにゼロの解はありません。行 C の列 b にはゼロしかありませんが、行 D にはゼロが残りません。

ここで何か誤解していますか？ゼロ割り当てが可能かどうかについて、より良いテストが必要ですか? これらすべての情報源は、何か本質的なものを除外していますか?

4

1 に答える 1

8

この例の行列のゼロは、列 b、行 A、行 B、行 E の 4 行だけでカバーできます。

例に適用された6 月 25 日の時点でウィキペディアの記事に示されているアルゴリズムの段階的なウォークスルーを次に示します。

    a  b  c  d  e

A   0  7  0  0  0
B   0  8  0  0  6 
C   5  0  7  3  4 
D   5  0  5  9  3 
E   0  4  0  0  9

ステップ 1: 各行の最小値はゼロであるため、減算は効果がありません。すべてのタスクがゼロ コストで実行されるようにタスクを割り当てようとしますが、これは不可能であることが判明しました。次のステップに進みます。

ステップ 2: 各列の最小値もゼロであるため、このステップも効果がありません。次のステップに進みます。

ステップ 3: すべてのゼロをカバーする最小数の行を見つけます。[b,A,B,E] を見つけます。

    a  b  c  d  e

A   ---|---------
B   ---|---------
C   5  |  7  3  4 
D   5  |  5  9  3 
E   ---|---------

ステップ 4: 最小限の露出要素を見つけます。これは (C,d) と (D,e) で 3 です。マークされていないすべての要素から 3 を引き、2 つの線で覆われているすべての要素に 3 を追加します。

    a  b   c  d  e

A   0  10  0  0  0
B   0  11  0  0  6 
C   2  0   4  0  1 
D   2  0   2  6  0 
E   0  7   0  0  9

すべてのゼロをカバーするための最小行数はすぐに 5 になります。すべての行にゼロがあり、すべての列にゼロがあるため、これは簡単に確認できます。アルゴリズムは、ステップ 1 で探していたような割り当てが新しい行列で可能になるはずであると主張します。

すべてのタスクがゼロコストで実行されるようにタスクを割り当てようとします (新しいマトリックスに従って)。これが可能になりました。解 [(A,e),(B,c),(C,d),(D,b),(E,a)] を見つけます。

ここで戻って、見つけた解が実際に最適であることを確認できます。コストが 3 の (C,d) を除いて、すべての割り当てられたジョブのコストがゼロであることがわかります。3 は実際には行列の最小の非ゼロ要素であり、コストがゼロのソリューションがないことは明らかです。これが最適解であること。

于 2013-07-02T07:19:59.743 に答える