ランダムなセルにチョコレートを含む 2-d グリッドがあります。1 回の移動で、1 つの行または 1 つの列に含まれるすべてのチョコレートを取得できます。すべてのチョコレートを取得するために必要な最小の移動数は何ですか?
例: チョコレートを含むセル:
0 0
1 1
2 2
分。移動回数 = 3
0 0
1 0
0 1
移動の最小数=2
この問題には貪欲なアルゴリズムの解決策があると思いますが、この問題にどのようにアプローチすればよいでしょうか?
2 に答える
0
これは、 NP 困難であることが証明されている古典的なセット カバー問題の分散だと思います。
したがって、貪欲なアルゴリズムは近似値しか得られず、最適解は得られません。
于 2013-10-08T07:01:52.670 に答える
0
この特定の問題については、NP 困難ではありません。多項式時間で解けます。解決策は次のとおりです。
2D グリッドを 2 部グラフに変換します。左側には行を表すノードが含まれ、右側には列を表すノードが含まれます。チョコレートを含む各セルの座標が (x,y) であると仮定し、row_x と column_y をリンクするエッジを追加します。二部グラフが確立されたら、ハンガリー語アルゴリズムを使用して最大一致を取得します。二部グラフでは、最大一致の答えは最小頂点被覆に等しいので、答えはまさにあなたが望むものです。
ハンガリーのアルゴリズムは O(V*E) アルゴリズムです。詳細については、ハンガリーのアルゴリズムを参照してください
二部グラフの詳細については、 二部グラフ を参照してください。最大一致が最小頂点被覆に等しい理由は、ここで確認できます。
PS: これは貪欲な問題でも、動的計画法の問題でもありません。グラフの問題です。
于 2013-10-09T08:05:33.670 に答える