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

• Item type: Journal(1)
• 公開日: 2002-12-15
• タイトル: 位相的特徴量に基づく平面ポリオミノ箱詰め問題の解法
• タイトル / 言語: en
• タイトル: Solution of Planar Polyomino Packing Problem Based on Topological Characteristics
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文（論文賞受賞）
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 計算科学と数値シミュレーションの理論と実践
• 著者所属: 神奈川工科大学
• 著者所属: 筑波技術短期大学
• 著者所属: 神奈川工科大学
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Kanagawa Institute of Technology
• 著者所属(英): en
• 著者所属(英): Tsukuba College of Technology
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Kanagawa Institute of Technology
• 著者名: 村井, 保之; 巽, 久行; 徳増, 眞司
• 著者名(英): Yasuyuki, Murai; Hisayuki, Tatsumi; Shinji, Tokumasu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: VLSIフロアプランや板金板取などを含む一般的な板取ないし配置問題に関する研究の一環として，少なくとも1つの解が存在する特殊な配置問題である平面ポリオミノ箱詰め問題を取り上げた．本論では，この解法として，ピース配置に関わる位相的特徴量の潰し合いに着目した配置手順発見のための大域的な探索手法を開発した．この手法の中身は空間的な評価としての``盤面の評価''とそれに基づく手順の評価としての``攻めての評価''を活用して，最も有望な順序でピースを選択し配置するアルゴリズムからなっているが，本論ではさらに，原問題を拡張して2つの最適化問題を派生させ，これらについても前記アルゴリズムをベースとした解法を構成した．あわせて，これら手法の有効性を数値実験により検証した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 43, 号 12, p. 4009-4022, 発行日 2002-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764