位相的特徴量に基づく平面ポリオミノ箱詰め問題の解法

• 村井, 保之

• 巽, 久行

• 徳増, 眞司

書誌事項

タイトル別名

• イソウテキ トクチョウリョウ ニ モトヅク ヘイメン ポリオミノ ハコヅメ モンダイ ノ カイホウ
• Solution of Planar Polyomino Packing Problem Based on Topological Characteristics
• 計算科学と数値シミュレーションの理論と実践

抄録

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.

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 43 (12), 4009-4022, 2002-12-15

  東京 : 情報処理学会

キーワード

• 論文（論文賞受賞）

詳細情報

• CRID: 1050282812860628224
• NII論文ID: 110002711502
• NII書誌ID: AN00116647
• ISSN: 18827764
• ISSN: 03875806
• NDL書誌ID: 6405880
• Web Site: http://id.nii.ac.jp/1001/00011414/
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I6405880
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles