Reverse-Fitを用いた単純な2次元ビンパッキングのアルゴリズム

元データ 2004-01-30 一般社団法人情報処理学会

概要

高さと幅が1以下の長方形を辺の長さが1の単位正方形に重ならないようにパッキングするとき,必要な正方形の個数を最小にするという問題が2次元ビンパッキング問題である.この問題に対して.2002年に発表されたCapraraのアルゴリズムは漸近近似率が良くなるように作られたものであり,現実的な入力においては多くの場合良い結果とならない.本論文では現実的な入力において良い結果を出せるようなアルゴリズムを提案し,計算機上に実装して実験的性能の比較評価を行う.

著者

浅野 孝夫 中央大学理工学部情報工学科
Ono T Graduate School Of Information Science Nagoya University
浅野 孝夫 中央大学大学院理工学研究科情報工学専攻
佐々木 浩高 中央大学大学院理工学研究科情報工学専攻

関連論文

▼もっと見る