| 講演名 | 2000/3/3 Simulated Annealing法探索に適した Sequence-Pairによるパッキング解空間 藤吉 邦洋, 大村 智一, 井尻 堅大, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 与えられた様々なブロックをできるだけ小さい面積の矩形内に配置するというパッキング問題に対して、ブロックが矩形だけのときの表現方法としてsequence-pairが提案され、L型ブロックも扱えるように拡張された。sequence-pairで表現されたパッキングの中から最適解を探索する手法としては、SA法が多く用いられている。これを用いるためには隣接解を定義して解空間を張る必要があるが、これの善し悪しについてはあまり研究されてこなかった。 本稿では、代表的な解空間について考察し実験により評価した。矩形だけの問題で最も優れていた解空間が、L型ブロックを含むとSA法で必要とされる到達可能性を満たさないことを証明し、実験的にもこの解空間が劣ることを示した。これにより到達可能性の重要性が確かめられた。 |
| 抄録(英) | The sequence-pair, which was proposed as the representation of the packing of rectangles, was recently extended to represent the packing of L-shaped blocks. The Simulated Annealing is often used to search the solution space of packings represent by sequence-pairs, but it was not studied whether or not the solution space is appropriate. In this paper, by theoritical and intuitive point of view, we evaluate some representative solution spaces for rectangle packing and L-shaped block packing which are represented by sequence-pair and examined by experiments. |
| キーワード(和) | sequence-pair / パッキング問題 / Simulated Annealing 法 / 解空間 |
| キーワード(英) | sequence-pair / packing problem / Simulated Annearing / solution space |
| 資料番号 | VLD99-118,ICD99-275 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2000/3/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Simulated Annealing法探索に適した Sequence-Pairによるパッキング解空間 |
| サブタイトル（和） | |
| タイトル（英） | Solution Space by Sequence-Pair Suitable for Simulated Annealing Search |
| サブタイトル（和） | |
| キーワード(1)（和/英） | sequence-pair / sequence-pair |
| キーワード(2)（和/英） | パッキング問題 / packing problem |
| キーワード(3)（和/英） | Simulated Annealing 法 / Simulated Annearing |
| キーワード(4)（和/英） | 解空間 / solution space |
| 第 1 著者 氏名（和/英） | 藤吉 邦洋 / Kunihiro FUJIYOSHI |
| 第 1 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 第 2 著者 氏名（和/英） | 大村 智一 / Tomokazu OHOMURA |
| 第 2 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 第 3 著者 氏名（和/英） | 井尻 堅大 / Kendai IJIRI |
| 第 3 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 発表年月日 | 2000/3/3 |
| 資料番号 | VLD99-118,ICD99-275 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 659 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |