産業界では、布地、木材、金属など、材料の最も効率的な使用法を計算する必要があるという問題がよくあります。したがって、出発点は、ポリゴンおよび/または曲線で作成された、指定された寸法の形状の X 量です。ラインであり、ターゲットは指定された次元の別のポリゴンです。
現在の CAM スイートの多くがこれを実装していると思いますが、それらやその内部を使用した経験がないので、スペースの最も効率的な使用法を見つけるためにどのような種類の計算アルゴリズムが使用されているのでしょうか? このトピックについて説明している本やその他の参考文献を教えてもらえますか?
アンドリューが答えで正しい方向を示し、問題に名前を付けた後、私は自分の研究結果を別の答えとしてここに捨てることにしました。
これは確かにパッキングの問題であり、より正確には入れ子の問題です。この問題は数学的に NP 困難であるため、現在使用されているアルゴリズムはヒューリスティックなアプローチです。単純な問題セットを除いて、線形時間で問題を解決するソリューションはないようです。複雑な問題を解決するには、現在のハードウェアでは数分から数時間かかります。材料を十分に活用して解決策を達成したい場合です。形状のネスティングを提供する商用ソフトウェア ソリューションは数十ありますが、オープン ソース ソリューションを見つけることができなかったので、実際に実装されたアルゴリズムを確認できる実際の例はありません。
コペンハーゲン大学 ( Nielsen )の Benny Kjær Nielsen によって書かれた論文には、過去の解法を使用したネスティングとストリップ ネスティングの問題の優れた説明があります。
一般的なアプローチは、最適なネスティング ソリューションを見つけるために、複数の既知のアルゴリズムを組み合わせて使用することです。これらのアルゴリズムには、(Guided / Iterated) Local Search、No-Fit Polygonに基づくFast Neighborhood Search、およびJostling Heuristicsが含まれます。この件に関して、アルゴリズムがどのように機能するかの写真が掲載された素晴らしい論文を見つけました。また、これまでのさまざまなソフトウェア実装のベンチマークもありました。この論文は、S. Umetani et al ( Umetani ) による International Symposium on Scheduling 2006 で発表されました。
比較的新しく、おそらくこれまでで最良のアプローチはハイブリッド遺伝的アルゴリズム(HGA) に基づいています。これはシミュレーテッド アニーリングと遺伝的アルゴリズムからなるハイブリッドで、武漢大学 ( Quanming )の Wu Qingming らによって説明されています。彼らは、Visual Studio、SQL データベース、および MatLab の遺伝的アルゴリズム最適化ツールボックス (GAOT) を使用してこれを実装しました。
あなたは、2次元空間と3次元空間の両方について、さまざまな問題が定義され、研究が行われている、よく知られたコンピューターサイエンスのパッキングドメインについて言及しています。
定義された問題については、ネット上にかなりの資料がありますが、それを見つけるには、検索する問題の名前を知っている必要があります。
一部のパッケージはヒューリスティックなアプローチを採用する可能性があり (そうなると思います)、絶対的な正しい答えを得るためにすべての可能性を計算する必要があるかもしれません。