研究シーズ集

研究の目的、概要、期待される効果

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