| 講演名 | 2000/3/3 Sequence-Pairを用いたパッキングにおける矩形回転による面積最小化 : 局所的なスライス構造の利用 大村 智一, 藤吉 邦洋, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 矩形パッキング問題において、矩形を90^。回転することにより全体面積を最小化する「矩形回転による面積最小化問題」は、スライス構造ではO(n^2)時間にて解けるが一般構造ではNP困難である。本稿では、一般構造の矩形パッキングでの「矩形回転による面積最小化問題」を効率良く解くために、局所的なスライス構造を利用する手法を提案する。具体的には、一般構造パッキングはsequence-pairで表されるものとし、この上での極大な局所スライス構造の必要十分条件を示す。そして、この部分にスライス構造特有の面積最小化手法を応用することにより、矩形回転の組合せの候補数を大幅に減らせることを示す。提案手法をSimulated Annealing法に組み込んで計算機実験を行ない、その有効性を確かめた。 |
| 抄録(英) | In the rectangle packing problem, "area optimization problem", which is to minimize the whole area by rotating rectangles for 90 degrees, is proved to be NP-hard in general. But it can be solved in O(n^2) time if the packing is restricted to the slicing structure. In this paper, we propose a method using local slicing structure to solve the problem efficiently. The packing is supposed to be represented by sequence-pair, and the necessary and sufficient condition for the maximum local slicing structure is presented and proved. It is shown that the combination of the rotations can be reduced drastically by using the proposed method. The experimental results show the effectiveness of the proposed method. |
| キーワード(和) | sequence-pair / スライス構造 / 面積最小化 / 矩形回転 / パッキング |
| キーワード(英) | sequence-pair / slicing structure / area optimization / rectangle rotation / packing |
| 資料番号 | VLD99-119,ICD99-276 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2000/3/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Sequence-Pairを用いたパッキングにおける矩形回転による面積最小化 : 局所的なスライス構造の利用 |
| サブタイトル（和） | |
| タイトル（英） | Area Optimization of Packing Represented by Sequence-Pair |
| サブタイトル（和） | |
| キーワード(1)（和/英） | sequence-pair / sequence-pair |
| キーワード(2)（和/英） | スライス構造 / slicing structure |
| キーワード(3)（和/英） | 面積最小化 / area optimization |
| キーワード(4)（和/英） | 矩形回転 / rectangle rotation |
| キーワード(5)（和/英） | パッキング / packing |
| 第 1 著者 氏名（和/英） | 大村 智一 / Tomokazu OHMURA |
| 第 1 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 第 2 著者 氏名（和/英） | 藤吉 邦洋 / Kunihiro FUJIYOSHI |
| 第 2 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 発表年月日 | 2000/3/3 |
| 資料番号 | VLD99-119,ICD99-276 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 659 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |