- 501 名前：デフォルトの名無しさん mailto:sage [2012/01/21(土) 01:16:56.46 ]
-
Sequence-pair - Wikipedia
技術的背景
集積回路設計の一工程である配置計画では、回路として実現するために必要な様々なモジュールを、シリコン基板上にどのように配置するかを検討する。
「集積回路を出来るだけ小さく設計する」という要求は、配置計画において「モジュールを互いに重なることなく、出来るだけ小さい矩形領域内に配置する」という要求に置き換えられる。
隙間無く配置する作業はモジュールが数個から十数個程度であればまるでパズルのようだが、これが数百、数千、それ以上となると、とても人間が手に負える規模ではないことが明らかだろう。
このような理由から、「モジュールを互いに重なることなく、出来るだけ小さい矩形領域内に配置せよ」という要求はフロアプラン問題と呼ばれ、
1980年代になると集積回路設計の自動化に取り組む内外の研究者の格好の研究対象となった。
フロアプラン問題はモジュールの形状を矩形に限定すると、大きさの異なる矩形をできるだけ隙間無く詰め込む問題となる。
この問題は矩形パッキング問題と呼ばれ、NP困難であり[1]、多項式時間で最適解を得る方法は知られていない。
ブロックの数が増えれば増えるほど配置のバリエーションが爆発的に増えていくため、問題解決のために配置の全バリエーションを探索するのは非現実的である。
切出し・詰込み問題に対する実用的解法
切出し・詰込み問題は，いくつかの図形を互いに重ならないように与えられた領域内に配置する問題であり，多くの分野に応用を持つ最適化問題である．
この問題は，長方形詰込み問題，円詰込み問題，コンテナ詰込み問題，多角形詰込み問題など図形の次元や形状によりさまざまなバリエーションを持つ．
切出し・詰込み問題のバリエーションの多くは NP 困難のクラスに属する組合せ最適化問題であり，実用的な規模の問題例に対して厳密な最適解を求めることは非常に困難である．
本稿では，さまざまな形状や大きさの多角形を長方形の容器に詰め込む多角形詰込み問題を取り上げて代表的な近似解法を紹介する．
www6.ocn.ne.jp/~seisan/612/612-56.pdf
|
 |
