矩形パッキングのための最大重み減少列を求めるアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitaniにより,矩形パッキング問題における画期的な許容解の表現力法が提案された.この表現方法はSEQ-PAIRと呼ばれ,効率のよい解の探索を可能にし,アルゴリズムの計算時間を飛躍的に向上させた.本報告では重みつきの順列における最大重み減少列を求める問題に対し,効率的アルゴリズムを提案すると同時に,このアルゴリズムをSEQ-PAIRを用いたパッキングアルゴリズムに採用することで,さらに計算時間を減らすことができることを示した.アルゴリズムの計算量はO(nω)であるが,データ構造を工夫することでO(n log n)となる(ただし,ωは最大重み減少列の長さ).
- 社団法人電子情報通信学会の論文
- 1996-07-26
著者
関連論文
- 矩形描画あるいはフロアプランの(4n-3)-ビット表現(グラフ,ペトリネット,ニューラルネット,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 矩形描画あるいはフロアプランの多項式時間数え上げ (第21回 回路とシステム軽井沢ワークショップ論文集) -- (組合せ的アルゴリズム)
- 並べ替え可能な隣接記号を含む2つの文字列の最長共通部分列問題(グラフ,ペトリネット,ニューラルネット及び一般)
- 並べ替え可能な隣接記号を含む2つの文字列の最長共通部分列問題(グラフ,ペトリネット,ニューラルネット及び一般)
- 矩形迷路のパス決定アルゴリズム(グラフ, ペトリ, ニューラルネット及び一般)
- 矩形迷路のパス決定アルゴリズム(グラフ, ペトリ, ニューラルネット及び一般)
- 多端子ネット配線の配線長と混雑度の最小化手法(グラフ,ペトリ,ニューラルネット及び一般)
- 多端子ネット配線の配線長と混雑度の最小化手法(グラフ,ペトリ,ニューラルネット及び一般)
- A-1-21 レクトリニア多角形パッキングの O-Tree 表現
- 矩形パッキングのための最大重み減少列を求めるアルゴリズム