これには基準がありますか？アルゴリズム名？
説明: サイズの異なる 10 個のポリゴンがあります。特定のサイズの領域があります。
その領域で最も多くのポリゴンを塗りつぶす方法と、それらがどのように適合されているかを知りたいです。
注: 制限セットによっては、ポリゴンが回転する場合があります。
質問する
2223 次
3 に答える
6
考えられる名前の 1 つは、Packing Problemです。ナップザック問題に関連しています。これらの問題は NP 困難になる傾向があり、多くはヒューリスティックを必要とします。ポリゴンと領域の許容される形式を制限できる場合は、特殊なケースに対してより効率的なアルゴリズムが存在する可能性があります。
于 2009-12-01T08:19:44.710 に答える
2
ウィキペディアの「Dancing Links」で、タイル張りを含む正確なカバー問題に対するドナルド クヌースの解決策を確認できます。質問はタイル張りの問題と見なすことができます。
于 2009-12-01T08:30:13.783 に答える
1
すべてのポリゴンが長方形であり、それらが収まる領域も長方形である場合、これはビンパッキングと呼ばれ、Google はこれに関する情報であなたを圧倒します。そうでない場合は、ビンパッキングの変種を探していると思います。また、「試してテストする」ことが最適なアルゴリズムである NP 問題に取り組んでいると思います。
于 2009-12-01T08:24:28.087 に答える