【要約】詰め込み選手権 ―― ポリオミノを長方形に敷き詰める、四つのアルゴリズムの勝負 [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
製造現場では、材料から部品を無駄なく切り出す「板取り（ネスティング）」の最適化がコストに直結する。筆者は、この課題をモデル化したポリオミノの敷き詰め問題を用いて、以下の課題を検証した。
- ・材料の歩留まりを最大化するための、最適な配置パターンの探索。
- ・ピースの形状や配置の組み合わせが膨大になることによる、計算量の爆発。
- ・問題の規模拡大に伴う、解法ごとの性能差の把握。
// Approach
筆者は、ポリオミノを長方形に敷き詰める問題を解くため、4つの異なるアルゴリズムを実装し比較した。実装では、Pythonの多倍長整数を用いたビット演算により、高速な重なり判定を実現している。
- ・貪欲法：ピースを特定の順序で、空きスペースの左上から順に詰める。
- ・焼きなまし法：確率的な遷移を許容し、局所最適解を回避しながら探索する。
- ・遺伝的アルゴリズム：順序交叉を用いて、ピースの並び順を最適化する。
- ・厳密解：空きマスを起点に候補を絞り込む、バックトラック探索を用いる。
// Result
実験の結果、盤面の規模に応じて、最も効率的なアルゴリズムが変化することが示された。筆者は、問題の構造と計算リソースのバランスから、以下の知見を得た。
- ・小・中規模：制約が強く伝播しやすい構造のため、厳密解が100%を達成した。
- ・大規模：厳密解は計算量増大により失速するが、ヒューリスティクスが実用的な解を出す。
- ・結論：実務では、規模に応じて厳密解とヒューリスティクスを使い分けるべきである。
Senior Engineer Insight
> 本記事は、組合せ最適化における「問題の構造」と「規模」の重要性を突いている。制約が強い小規模問題には厳密解が適している。探索空間が広大な大規模問題には、ヒューリスティクスが適している。これらは実戦的な設計指針と言える。ただし、実務のネスティングは連続的な形状や切り代の考慮が必要である。本モデルはあくまで抽象化された模型である。現場への適用時は、モデルの単純化による誤差を考慮すべきだ。