イベント
情文カフェ第21回：身近にある組合せ最適化
2013年10月4日
情報文化学部はいわゆる理系・文系両方の教員が集まっているところですが，それはとりもなおさず多様な領域の相互作用の中で生まれる新たな発見のシーズが隠れていることを意味しています．そのようなシーズを顕在化させること，また話し手，聞き手双方がもっているセレンディピティをも顕在化させることを目指して，開いているカフェが情文カフェです．
原則として第4水曜日18時から，情報文化学部（全学教育棟北側）2階Phononで行っています．参加自由なので気楽にどうぞ．
日時：2013年10月23日(水)，18時00分より
場所：情報文化学部（共通教育棟北側）2階Phonon
スピーカー：柳浦 睦憲 教授（情報科学研究科）
タイトル：身近にある組合せ最適化
概要：
車で移動しているとき，「今いる所から目的地に最も早く着くにはどうしたらよいだろう」ということを考える機会がときどきあると思います．このように最も良い方策を見つける問題を一般に最適化問題と呼びます．その中でもとくに組合せ的な性質を持つ組合せ最適化問題に関する話題を，身近な例を題材に挙げつつ紹介します．
参加者の感想
今回は、組合わせ最適化問題について、その考え方が応用されている身近なものを例に挙げながらお話をしてくださいました。たとえば、スポーツの対戦表。有利不利を無くすために、全チームのホーム戦とアウェー戦それぞれの試合数ができる限り同数になるように試合を組む際に、組合わせ最適化問題の考え方が用いられていたりするそうです。他にも、コンビニへの商品配達や宅配などの配送計画立てや工場での製品の機械への割当、病院の看護師の勤務表を制作する際にも用いられているそうです。
私たち自身も無意識のうちに、組合わせ最適化問題の考え方を利用していることがあります。買い物で様々な店を回る場合、どのように回ると無駄が少ないか考えていると思います。このときに組合わせ最適化問題の考え方が使われています。このような、最短距離を求める問題を巡回セールスマン問題と呼びます。組合わせ最適化と聞いても、恥ずかしながら、まったくもって具体的な事例は思いつかなかったのですが、とても身近なところで組合わせ最適化の考えが利用されていることを実感しました。
最適化問題の解を最適解と呼びますが、組合わせ最適化問題は探索すべき解候補の数があまりにも膨大なため、最適解を求めることは多くの場合現実的ではありません（その難しさを説明する概念として、NP困難性というものがあります）。そのため、近似解を求めることとなります。近似解とは、条件を満たす解の中で良いもののことです。なぜ近似解を求めるのかというと、短時間で良い解を求めたいという要求は多く、また、必ずしも最適解でなくてもよい場合があるからだそうです。たとえば、買い物のルートを決めるのに時間をかけて綿密な計算をする人はまずいないと思います。ルートを決める時間も自分の大切な時間なので、そんなことをするよりもある程度短いルートをさっさと決めて出発する方が断然早いからです。そのため、近似解を求める計算方法の研究も重要だといいます。方法の例として欲張り法や局所探索法など、アルゴリズムの講義で学んだものが挙げられていました。
組合わせ最適化問題の最適解は見つけることが困難だと上で述べましたが、一方で一見難しそうでも、最適解を効率よく求める問題もあるようです。その一つとして、最短路問題が挙げられます。これは出発地点から目的地までの最短ルートを決定する際に、ダイクストラ法というアルゴリズムを利用することで、瞬時に最短路を得ることが可能だそうです。これはカーナビのルート検索などに応用されています。また、文書整形問題というものもあります。お馴染みのWordなどで英文を打つ際、どの程度単語間のスペースを増やせば改行がうまくいき、きれいなレイアウトの英文となるのかを、動的計画法と呼ばれる方法を使うことで、最適解（最適な改行位置の組合わせ）を求めることができるそうです。これもまた意外なところで組合わせ最適化問題の考え方が用いられていることを実感しました。
組合わせ最適化と聞いても、はじめは全くピンと来なかったのですが、お話を聴いたことで、この考え方が身近に多く存在していることがわかりました。柳浦先生、有意義なお話をありがとうございました。
（社会システム情報学科 常富大輝）
資料
- 柳浦研究室紹介ページ
（http://www.co.cm.is.nagoya-u.ac.jp/~yagiura/cop.html）
- マルチメディアライブラリー第13編， システム制御情報学会，2010年1月.
（http://www.co.cm.is.nagoya-u.ac.jp/~yagiura/iscie-dvd/）
- オペレーションズ・リサーチ
（http://www.orsj.or.jp/e-library/elcorsj58.html），58巻 (2013) 12月号
特集: はじめようメタヒューリスティクス（オーガナイザ：柳浦先生）
「メタヒューリスティクス事始め —まずは局所探索法から—」
・・・梅谷俊治（大阪大学大学院情報科学研究科），
柳浦睦憲（名古屋大学大学院情報科学研究科）
「概説メタ戦略」
・・・今堀慎治（名古屋大学大学院工学研究科），
柳浦睦憲（名古屋大学大学院情報科学研究科）
等
