著者
高橋 俊彦
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. 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)となる(ただし,ωは最大重み減少列の長さ).

言及状況

Twitter (1 users, 1 posts, 0 favorites)

こんな論文どうですか? 矩形パッキングのための最大重み減少列を求めるアルゴリズム,1996 http://ci.nii.ac.jp/naid/110003294429 H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitaniにより

収集済み URL リスト