3

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

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

ここに説明があります：

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

ステップ3でそれは言う

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

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

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

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

前もって感謝します

4

3 に答える 3

2

ここでは、二部一致アルゴリズムを実装する必要があります。グラフには 2 つのパーティションがあります。一方の頂点は行を表し、もう一方の頂点はテーブルの列を表します。セル (i,j) に 1 がある場合、行iと列jの間にエッジがあります。次に、最大二部マッチングを作成します。二部マッチング アルゴリズムの最後の反復の後、どの頂点がマッチングのソースとインクリメンタル パスを介して接続されているかを把握する必要があります。増分パスは、正の容量を持つエッジのみを使用するパスです。次のような画像が必要です。

         row_1                  col_1
        /                             \
       / - row_2                col_2 -\
source  - ....     some_edges           \ sink
       \                                / 
        \ - row_n                col_n /
                                 .... /
                                 col_m

最大の 2 部一致を見つけたら、シンクから正の容量エッジを介して到達可能な行と列を見つけます。スクラッチする必要がある行と列の最小数は、次のアルゴリズムを使用して見つけられます。ソースから到達できないすべての行と到達可能なすべての列を取り消します。これが最適なソリューションです。

この回答がお役に立てば幸いです。

于 2012-04-09T14:30:03.183 に答える
1

なぜ試行錯誤するように言われたのかよくわかりません。ただし、ハンガリーのアルゴリズムは指数関数的な時間を要しません。最小行数を把握する方法の例を紹介するウィキペディアをご覧ください（ステップ3をご覧ください）。

http://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation

この記事には、実装へのリンクと、使用しているものよりもハンガリーのアルゴリズムのより完全な（ただしより技術的な）説明を提供するいくつかのオンラインコースノートも含まれています。

于 2012-04-09T16:54:57.297 に答える
0

試行錯誤は O((n+m)!) の複雑さを意味します。

すべての行または列を選択するとすべての 0 がカバーされるため、せいぜい min(n,m) 行を選択するだけで済みます。

大規模な問題のこのステップを解決するために、動的計画法アルゴリズムを実装します。

于 2012-04-09T14:19:41.610 に答える