研究内容:組合せ構造の表現法

矩形パッキング問題

 矩形パッキング問題とは矩形(長方形)の集合が与えられたとき、これらを重なることなく内部に収める最小面積の矩形(およびそのときの矩形の配置)を見つける問題である。矩形パッキンング問題はVLSIの設計におけるモジュール配置問題を直接の動機としているが、多くの組合せ最適化問題と同様NP困難であるため、発見的手法により準最適解を得るのが現実的である。

 一般に発見的手法においては(準)最適解を得るまでに、数多くの許容解の生成と評価を繰り返す。そのため、許容解の適切な表現法が探索アルゴリズムの性能の鍵を握る。すなわち、生成と評価を効率よく行うことが可能であるような解の表現法が不可欠である。

 高橋は矩形配置の表現法であるLOT法を考案した。後にLOT法はP. Guo, C. K. Chen, and T. Yoshimuraとの共著によりO-Tree法として発表される。

 以下はO-Tree法の概略である。


左下詰めの配置に対して, 順序木が一意に対応する.


順序木を行きがけ順になぞり, ビット列と矩形名列による表現を得る.


逆に任意のビット列と矩形名列から矩形配置を得ることができる.ただし, 得られる配置が左下詰めとは限らない.


関連論文

  1. P. -N. Guo, T. Takahashi, C. -K. Cheng, and T. Yoshimura,Floorplan Using a Tree Representation,IEEE Trans. Computer-Aided Design,Vol.20, No.2, pp.281-289, 2001.( IEEE CIRCUITS AND SYSTEMS MAGAZINE, SECOND QUARTER 2003に解説あり:T. Takahashi, P. -N. Guo, C. -K. Cheng, and T. Yoshimura, Floorplan Using a Tree Representation: A Summary)

  2. T. Takahashi,A New Encoding Scheme for Rectangle Packing Problem,Proc. Asia and South Pacific design Automation Conference 2000 (ASP-DAC2000), pp. 175-178, 2000.

  3. T. Takahashi,A Simple Encoding Scheme for Rectangle Packing Problem,Proc. 1999 International Technical Conference on Circuits/Systems, Computers and Communication(ITC-CSCC1999), Vol. 1, pp. 352-354, 1999.

ページのトップへ戻る