algorithm - デカルト曲面項目のアルゴリズムを含む

Question

デカルト面全体に広がる特定の数のアイテムを含む最小数の長方形を最適に見つけるのに役立つアルゴリズムはありますか (各アイテムは x & y 座標を持つポイントです)。長方形は直交し、Ox 軸上に下部セグメントがあり、各長方形の面積は所定の値 M より小さくなければなりません。

Answer 1

完全な解決策ではありませんが、問題を単純化します。すべての点 P が一般的な位置にあり、x 座標で並べ替えられていると仮定します。

x >= fx次に、 P を素集合に分割する F 個の垂直フェンス ( の形式) を見つけることによって、解が形成されます。

次に、各セットを軸に沿った長方形でカバーできます。セット内の最初と最後のポイントが長方形の幅を決定し、セット内の最高の y 座標を持つポイントが高さを決定し、これによってサーフェス サイズが決定されます。長方形の。

明らかに、すべての長方形の合計サーフェス サイズを許容最大値以下に保ちながら、フェンスの数 (およびここでは長方形の数) が最小になるようにフェンスを選択することが秘訣です。

編集
おそらく、F フェンスを配置する問題は、動的計画法を使用して解決できます。 これは私がこれまでに思いついたものです：

その場合、フェンスの場所は最大 |P|-1 です。これらはおそらく動的計画法テーブルの列になります。動的計画法テーブルの各行は、追加のフェンスを使用して表す必要があります (最小数のフェンスで結果を見つけようとしていることを思い出してください)。したがって、各セル (X, Y) は、最初の X の使用可能な位置に正確に Y フェンスを分配する最適なソリューション (四角形の合計サイズに関して) を表します。ただし、テーブルの隣接するセルが特定のセルの値を決定するのにどのように役立つか (またはその可能性があるか) を確認するのに少し問題があります。

編集 2 : 忘れてください。動的プログラミングのアプローチが可能だとは思いません。これは、最適なソリューションを段階的に構築することは不可能だと考えているためです (別のポイントまたはフェンスを追加することで、最適なソリューションの構成が完全に変わる可能性があります)。これにより、貪欲なアプローチも除外されます。

私が考えることができる唯一の考えは、アルゴリズムの観点からは少し壮観ではありませんが、フェンスを配布するためのシミュレーテッドアニーリングなどのランダム化されたアプローチです。最適なソリューションを保証するものではありませんが、それにかなり近づくことができるはずです。

編集 3 : この投稿の下での反応に応じて、必ずしも最善の解決策を必要とするわけではありませんが、代わりに「かなり良い」解決策を求めて、現在学んでいることを適用してみてはどうでしょうか。

いずれにせよ、おそらくすべてのポイントを左から右に並べ替える必要があります。

貪欲な解決策は、最初の四角形を定義して、左端の点を含むようにすることです。次に、右側のポイントが含まれるように長方形を拡張します。長方形が最大サイズを超えるまで、次のポイントを追加し続けます。その場合は、新しい長方形から始めて、ポイントを追加し直すなどしてください。

解決策を得る分割統治法は、すべての点をカバーする長方形から始めることです。明らかに、この四角形は最大サイズ M を超えているため、いくつかのヒューリスティックに従って (たとえば、ちょうど真ん中、または後続の 2 つのポイントが最も離れているポイントで) 2 つの小さな四角形 Ml と Mr に垂直方向に分割します。Ml と Mr を同じ方法で再帰的に処理し、長方形を再度分割するか、見つかった長方形が <= M の場合は結果の一部として報告します。

どちらのアプローチでも、一部の人為的な構成では結果が任意に悪いものになる可能性がありますが、一般的には解決策は「問題ありません」であることに注意してください。