| 講演名 | 2002/5/16 Selected Sequence-Pairのための効率的な隣接解生成手法 藤吉 邦洋, 児玉 親亮, 清田 紘司, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | n個の矩形のパッキングを長さnの順列の対で表現するsequence-pairに対して、近年、隣接交差と呼ばれる部分列の数をn-3以下に制限したらら"selected sequence-pair"が提案された。これはsequence-pairと同様にどんな矩形パッキングでも表現可能であるという特長をもちながら、矩形数の線形時間にて、その示唆する制約の下での左下詰めパッキングを得ることができるという優れた特長をもつ。しかし、隣接解やその生成法が提案されていなかったため、Simulated Annealing法などと組み合わせてのパッキング探索に用いることができなかった。そこで本稿では、selected sequence-pairでの到達可能性を保証できる隣接解と、その効率的な生成方法を提案し、計算機実験によってその効率の良さを確認する。 |
| 抄録(英) | Recently "selected sequence pair" was proposed which is a sequence-pair with n-3 or less sub-sequences called adjacent cross (n is the number of rectangles). In addition to the merit that it can represent any packing, it has a superior feature that it can obtain a bottom left corner packing under the constraints imposed by itself in linear time of the number of rectangles. However, as the method of generating adjacent solution were not proposed, it was impossible to use selected sequence-pair for search of packing by combining with Simulated Annealing, etc. In this paper, we propose adjacent solution which can guarantee reachability in selected sequence-pair and the procedure to generate adjacent solution and then we confirm its efficiency by experiments. |
| キーワード(和) | Selected Sequence-Pair / パッキング / 隣接交差 / 隣接解 / 到達可能性 / Simulated Annealing法 |
| キーワード(英) | Selected Sequence-Pair / Packing / Adjacent Cross / Adjacent Solution / Reachability / Simulated Annealing |
| 資料番号 | VLD2002-6 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2002/5/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Selected Sequence-Pairのための効率的な隣接解生成手法 |
| サブタイトル（和） | |
| タイトル（英） | An Effective MOVE Operation for Selected Sequence-Pair |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Selected Sequence-Pair / Selected Sequence-Pair |
| キーワード(2)（和/英） | パッキング / Packing |
| キーワード(3)（和/英） | 隣接交差 / Adjacent Cross |
| キーワード(4)（和/英） | 隣接解 / Adjacent Solution |
| キーワード(5)（和/英） | 到達可能性 / Reachability |
| キーワード(6)（和/英） | Simulated Annealing法 / Simulated Annealing |
| 第 1 著者 氏名（和/英） | 藤吉 邦洋 / Kunihiro FUJIYOSHI |
| 第 1 著者 所属（和/英） | 東京農工大学 工学部 電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 第 2 著者 氏名（和/英） | 児玉 親亮 / Chikaaki KODAMA |
| 第 2 著者 所属（和/英） | 東京農工大学 工学部 電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 第 3 著者 氏名（和/英） | 清田 紘司 / Koji KIYOTA |
| 第 3 著者 所属（和/英） | 東京農工大学 工学部 電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 発表年月日 | 2002/5/16 |
| 資料番号 | VLD2002-6 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 72 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |