氏名 : 王 超 (281067058)
所属 : 張研
題目 : 可変長方形の最適配置問題
概要 :
長方形配置問題は、与えられた長方形群を重ならないように最小領域に詰め込む問
題です。これまで、長方形の形状が不変である問題(長方形の最適配置問題)が詳し
く研究されてきました。この問題に対する代表的なアルゴリズムとしてBest-Fit法が
あります。この手法は、長方形を一つずつ順に配置する手法で、長方形の数をnとす
ると、O(n log n)時間で動作する高速なアルゴリズムです。
工学的な応用を考えると、長方形の形状が面積条件の下で可変である場合が多くあ
ります。本研究では、そのような問題(可変長方形の最適配置問題)に対するアルゴ
リズムを考えます。本研究のアプローチは、Best-Fit法をベースとし、配置する長方
形とその形状の決定に特徴があります。次に配置する長方形を探すためのデータ構造
である二分探索木を修正することで、長方形の形状が不変の場合と同じ計算量で、さ
らに隙間の少ない配置を得ることを目標とします。
目次に戻る