2007年12月27日計算機数理科学専攻・計算論講座
平田研究室（平田富夫教授、柳浦睦憲准教授、小野孝男助教）

本研究室では、グラフ問題や組合せ問題のような離散構造をもつ問題に対するアルゴリズムの研究を行っています。

そのような問題の多くは、問題規模が大きくなると現在の計算機で厳密に解くことは難しいことが知られています。しかし、そのような難しい問題であっても、計算機を用いてなんとか解かなければならない離散最適化問題が、情報処理に関わる種々の場面でますます増えてきています。

このような現実を踏まえ、たとえ求まる解が最適ではなくとも、それに十分近い近似解を出力できるアルゴリズムの設計論が今日の重要な研究テーマとなっています。

本研究室では、グラフの彩色問題や集合被覆問題を中心とした代表的な組合せ最適化問題に対する高性能アルゴリズムを開発するとともに、実際の応用にも力を注いでいます。以下に具体的な研究テーマの例をいくつかご紹介します。

・グラフ彩色問題

与えられたグラフの点や辺に規定の制約を満たすように色を塗る問題で、さまざまなバリエーションがあります。以下に、辺の両端の点の色が異なるようにグラフの各点に色を塗った例（図1、左）と、各点の回りの辺に各色が丁度一度ずつ用いられるように辺を彩色した例（図1、右）を示します。

• 図1：グラフ彩色の例

単純に見えますが、時間割作成やスケジューリングなどに幅広い応用を持つ重要な問題です。グラフ彩色問題の一種であるnearly equitable edge coloring problemに対する効率的なアルゴリズムの開発に成功し、その成果第6回情報学術フォーラム（情報処理学会、電子情報通信学会情報・システムソサイエティ、電子情報通信学会ヒューマンコミュニケーショングループ共催）において、FIT論文賞を受賞しました（写真）。

• 写真：FIT論文賞受賞者

・パッキング問題

与えられた複数の多角形をできるだけ隙間なく詰め込む問題で、鉄鋼や服飾産業などに幅広い応用を持ちます。メタヒューリスティクスに基づくアルゴリズムなどの開発を進めています。図2は9つの長方形のピースを枠内に置くときの無駄な隙間をできるだけ小さくする置き方を求めるパズルで、問題の面白さ・難しさを実際に体験してもらうために作成したものです。

• 図2：木製パッキングパズル

一見簡単そうに思えるかもしれませんが、結構骨が折れます。腕試しをしたい方はぜひとも研究室にいらしてください。

・組合せ最適化による織機の性能改善

織物は縦糸と横糸が交差して成り立っています。図3は縦糸と横糸が交差する様子を拡大して模式的に示したものです。

• 図3． 織物の縦糸（赤）と横糸（白）の交差の様子

このように、縦糸と横糸に異なる色を用い、どちらの糸が上に来るかを変更することで、さまざまな模様を作ることができます。そのようにして得られる模様の例を図4に挙げておきます。

•  図4． 織物の模様の例

織機の能力を最大限に引き出すことを組合せ最適化問題ととらえることで、限られた能力の織機でも複雑な模様を織ることができることを発見できました。

このように、応用上役に立つ問題を常に意識しつつ、理論と実践の両面から研究を進めています。
参考UR：http://www.al.cm.is.nagoya-u.ac.jp/