ハンガリアン アルゴリズムを C で実装しました。ほとんどの場合、うまく機能します。ときどき、私のコードが一部の行列の解を見つけられないことがあります。ソリューションの確認 マトリックスがどのようにカバーされているかが重要であると考え始めています。次に例を示します。
これは、最初の 2 つのステップが実行されたときの行列です (行ごとに min を減算し、列ごとに min を減算します)。
7 65 0 90 0 90
8 33 49 16 41 0
0 0 63 45 46 69
62 72 50 6 39 0
62 6 54 0 2 42
7 1 49 19 0 58
私のコードを使用してカバーした場合（2意味の要素が2回交差しています）：
1 1 1 2 2 2
0 0 0 1 1 1
1 1 1 2 2 2
0 0 0 1 1 1
0 0 0 1 1 1
0 0 0 1 1 1
ここで同じ元のマトリックスを使用して解決策を探しましたが、マトリックスのカバーが異なっていました。最後の 2 列を選択する代わりに、最後の 2 行を選択しました。さらに 2 つのマトリックス削減により、それらは一致することになります。一方、私はしません。
どの回線の組み合わせが優れているかを判断する方法はありますか?