著者

村井 保之 巽 久行 徳増 眞司

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.43, no.12, pp.4009-4022, 2002-12-15

---

VLSIフロアプランや板金板取などを含む一般的な板取ないし配置問題に関する研究の一環として,少なくとも1つの解が存在する特殊な配置問題である平面ポリオミノ箱詰め問題を取り上げた.本論では,この解法として,ピース配置に関わる位相的特徴量の潰し合いに着目した配置手順発見のための大域的な探索手法を開発した.この手法の中身は空間的な評価としての``盤面の評価''とそれに基づく手順の評価としての``攻めての評価''を活用して,最も有望な順序でピースを選択し配置するアルゴリズムからなっているが,本論ではさらに,原問題を拡張して2つの最適化問題を派生させ,これらについても前記アルゴリズムをベースとした解法を構成した.あわせて,これら手法の有効性を数値実験により検証した.In this paper,a planar polyomino packing problem is taken up as a specialized placement problem such that it has at least one solution of placement,but not so many in general.The authors have developed a new global search algorithm for solutions,based on the mechanism of generation and extinction of topological characteristics on placement of pieces.Then,two optimization layout problems are constructed and solved by extending the packing problem and its solution.Finally,it is proved by numerical experiments that these algorithms work well in good efficiency.