共通・他の領域 私たちの研究室は「もの」の組み合わせをコンピュータの内部でどのように表現すれば効率的なアルゴリズムができるかを研究してきました。特に、効率的なアルゴリズムのためのデータ構造を発表してきました。 長方形（直方体）のパッキングとは、与えられた長方形（直方体）をできるだけ小さい面積（体積）内に詰め込む問題です。この問題を手掛けることになったのは、超大規模集積回路(VLSI)設計において、より小さなチップに回路ブロックを配置する研究プロジェクトに参加したことがきっかけでした。 もちろんパッキングは、回路設計だけでなく、鉄板、板、布などの素材から切り出し問題、倉庫やトラックへの荷物の積み込みなど、様々な場面に登場します。さらに、アルゴリズムも道具の1種ですから、思いもよらない使い方というものがあり、これまでになかった意外な応用が見つかることがあります。こうした発見もがアルゴリズムの研究の面白いところです。 分かりやすい例としてパッキングを紹介しましたが、研究対象は「もの」の組み合わせ構造、すなわち何でもありです。長方形や直方体だけを扱っているというわけではありません。2002 IEEE Circuits and Systems CAD Transaction Best Paper: Pei Ning Guo, Toshihiko Takahashi, Chung Kuan Cheng, Takeshi Yoshimura, Floorplanning using a tree representation, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No. 2, pp.281-289, 2001.※お問い合わせは新潟大学社会連携推進機構ワンストップカウンターまでonestop@adm.niigata-u.ac.jp●キーワード● 最適化問題、アルゴリズム、パッキング専門分野組合せアルゴリズム、数え上げアルゴリズム、グラフアルゴリズム、離散数学 丸投げの委託研究や形式だけの共同研究でなく、一緒に問題を考え、議論し、研究を楽しめる方なら、業種、企業、地域、分野は問いません。つながりは人と人の間に生まれます。8-3http://researchers.adm.niigata-u.ac.jp/html/301_ja.html自然科学系 准教授高橋 俊彦 TAKAHASHI Toshihiko関連する知的財産論文 等長方形パッキング：与えられた長方形を重なることなく配置する。配置の良し悪しを図る尺度を評価関数と呼ぶ。パッキング問題では配置を囲む長方形の面積が評価関数。VLSI設計では回路の配線長が配置の評価関数となることも多い。直方体パッキング：長方形パッキングの3次元版。VLSIの設計だけでなく、倉庫への荷物の詰め込みなどの応用もある。ただし、3次元の場合は直方体が何に対応しているのかによって、様々な制約条件（重ねてはいけない、隣に置いてはいけないなど）が加わることが多い。研究の目的、概要、期待される効果アピールポイントつながりたい分野(産業界、自治体等)組合せアルゴリズム～限られたスペースにどうやってものを詰め込むか～長方形および直方体のパッキングアルゴリズム
元のページ ../index.html#111