研究内容

長方形および直方体のパッキングアルゴリズム
〜　限られたスペースにどうやってものを詰め込むか　〜

私たちの研究室は「もの」の組み合わせをコンピュータの内部でどのように表現すれば効率的なアルゴリズムができるかを研究してきました。 特に，効率的なアルゴリズムのためのデータ構造を発表してきました。 長方形（直方体）のパッキングとは，与えられた長方形（直方体）をできるだけ小さい面積（体積）内に詰め込む問題です。 この問題を手掛けることになったのは，超大規模集積回路(VLSI)設計において，より小さなチップに回路ブロックを配置する研究プロジェクトに参加したことがきっかけでした。 もちろんパッキングは，回路設計だけでなく，鉄板，板，布などの素材から切り出し問題，倉庫やトラックへの荷物の積み込みなど，様々な場面に登場します。

また，アルゴリズムも道具の1種ですから，思いもよらない使い方というものがあり，これまでになかった意外な応用が見つかることがあります。 こうした発見もがアルゴリズムの研究の面白いところです。

※研究対象は「もの」の組み合わせ構造ですから何でもありです。 長方形や直方体だけ，パッキングだけを扱っているというわけではありません。 詳しく「卒業論文・学位論文」「外部発表」を参照してください。