4

次のようなブール配列を想定します。

1111
1111
1110
1111
1001

次に、この形状を実現するために、任意のサイズの最小の長方形を配置する方法を見つける必要があります。したがって、たとえば、次のようになります。

+-++
| |+
| |
+-++
+  +

ここで、+は長方形の角であり、|、-は長方形の境界です。

私が考えたのは、可能な限り最大の長方形から始めて、配置できる場所が配列内にあるかどうかを確認することです。この場所で、長方形で覆われるすべての配列要素が真になります。そのような場所が存在する場合、長方形がリストに追加されます。その後、配列の左側のスペースに長方形を配置する別のスポットがあるかどうかを確認し、長方形のサイズを小さくして、サイズが0になるまで残りのスペースでプロセスを繰り返します。

私たちは常に大きな長方形から始めるので、これは良い結果をもたらすはずです。もちろん、使用する長方形の数を減らすことができます。つまり、使用する長方形の量は少なくなります。

しかし、これは私が考えた概念であり、まだ実践されていません。それはかなり非効率的であるように思われるので、これを達成するための既知の迅速なアルゴリズムがあるかどうか疑問に思いましたか？

4

4 に答える 4

4

私は本当にこの問題について考えるのに行き詰まっていたので、私は公表された研究を調べました。最適なソリューションが必要な場合、これを効率的に解決するのはかなり難しい問題であることがわかります（技術的になりたい場合はNP困難）。私の言葉を信じたくない場合は、InformationandControlの論文「長方形でポリゴンをカバーするためのアルゴリズム」をチェックしてください。この論文には興味深いアイデアがたくさんあり、著者は最適なカバーを見つけるためのアルゴリズムを提供しています。明らかに、それは多項式時間で実行されませんが、問題のあるインスタンスのサイズに対しては十分に高速である可能性があります。興味のある問題に効果があるかどうかを確認するために、最初にさらに単純な枯渇テクニックを試してみることもできます。

これが私の最初の提案であり、反例はまだ私には発生していませんが、私はもはや最適であることを保証しません。

Rと呼ばれる長方形の空のコレクションから始めます。値が1の配列内の各位置（i、j）について、（i、j）を含む1の最も広い長方形Wを見つけ、Wを長方形に追加してから拡張します。すべて1を含む最大高さのM。コレクションRが存在しない場合は、コレクションRにMを追加します。終了したら、Rを通過し、Rの他の長方形で完全に覆われている長方形をすべて削除します。

于 2009-11-25T18:28:38.143 に答える
3

2次元配列をカルノー図のように扱うことを検討しましたか？ブール真理値表のセルを統合するためのアルゴリズム（Quine-McCluskyアルゴリズムなど）があります。これは、あなたがやろうとしていることのように見えます。

于 2009-11-20T17:03:03.093 に答える
1

説明する欲張りアルゴリズムが常に最適であるとは限らないことに注意してください。検討

01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX

最大の長方形から始めると、背の高い長方形が得られ、次に小さなエッジがたくさんあり、15個の長方形になります。一方、小さな横長の長方形だけを作成する場合は、14で実行できます。

于 2009-11-20T16:56:23.560 に答える
1

1で構成される最大の長方形の部分行列を見つけることができるO（N ^ 2）アルゴリズムがあります。この部分行列を見つけて、その周りに長方形を置きます。次に、その中のものをゼロに置き換えて、後続の長方形に含まれないようにします。アルゴリズムを再度適用して、次の長方形を見つけます。など、誰も残らなくなるまで続きます。

もちろん、この欲張りアルゴリズムは最適なソリューションを保証するものではなく、最悪の場合、その複雑さはO（N ^ 4）です。

入力データの最大サイズはいくつですか？

于 2009-11-20T17:03:55.083 に答える