- 著者
-
高橋 俊彦
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. VLD, VLSI設計技術
- 巻号頁・発行日
- vol.96, no.201, pp.31-35, 1996-07-26
- 被引用文献数
-
16
H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitaniにより,矩形パッキング問題における画期的な許容解の表現力法が提案された.この表現方法はSEQ-PAIRと呼ばれ,効率のよい解の探索を可能にし,アルゴリズムの計算時間を飛躍的に向上させた.本報告では重みつきの順列における最大重み減少列を求める問題に対し,効率的アルゴリズムを提案すると同時に,このアルゴリズムをSEQ-PAIRを用いたパッキングアルゴリズムに採用することで,さらに計算時間を減らすことができることを示した.アルゴリズムの計算量はO(nω)であるが,データ構造を工夫することでO(n log n)となる(ただし,ωは最大重み減少列の長さ).