http://www.nda.ac.jp/~yamada/labo/ 理工学3号館1階北側中央部分教授山田武夫 [email protected] 助教授片岡靖詞 [email protected] 助手渡辺宏太郎 [email protected] 情報数理研究室の研究って？ NP困難問題とよばれる，普通に計算するとべらぼうに時間のかかる問題を，短時間で計算するための工夫（アルゴリズムの研究・開発）をしています．具体的には下のような問題と，それらの応用が対象です． • 組合せ最適化 (より一般的には数理計画法) – ナップサック問題 • 一定の大きさのナップサックに収容する商品の組で価値の総和が最大となるものを求める問題です – 巡回セールスマン問題 • n 個の都市の全てを最短距離で訪問するにはどのように回れば良いかという問題です – グラフ（点と線からなる図形）の計算に関する問題 • 各中継点を結ぶ通信ネットワークで総距離最短のものを求める問題や， • 出発点から目的地まで最短の経路を見つける問題，などです ● 他に，シミュレーション，微分方程式の数値解法の研究も … 組合せ最適化関連図アルゴリズムの世界（いろいろな解法があります）数理計画法 ○ 単体法 ○ 内点法 ○ 整数計画法 ○ 非線形最適化組合せ最適化問題近似解法 ○欲張り（Greedy）法 ○局所探索（LS）法 ○ Lagrange緩和計算機による実装 ○ プログラミング ○ 可視化 ○ 数値実験現実問題への応用 ○ 物流，交通，輸送など厳密解法 ○ 分枝限定法釘づけテスト，上下界値の高速な算出 etc. ○ 動的計画法（ドイツの15000都市についての巡回セールスマン問題の解：セールスマンが通った経路）問題例（１）ナップサック問題１（任○堂）２（お昼）３（デジカメ）４（地図）重量１重量３重量３重量３価値２価値５価値４価値３重量W まで収納可能なナップサックにできるだけ価値の総和が大きくなるように商品を詰め込もうという問題です商品iの価値をpi，重量をwiと書けば次のように定式化できますナップサック重量W=６まで収納可 N 最大化　å pi xi i =1 N 制約条件　å wi xi £ W ( xi = 0 or 1) i= 1 上の例だと最大化: 2 x1 + 5x2 + 4 x3 + 3x4 制約条件： x1 + 3x2 + 3x3 + 3x4 £ 6, xi = 0 or 1 です計算量の壁ナップサック問題は，2ｎ個の組み合わせを全て調べれば解くことができます（全探索）．しかし，10000商品の場合その数は210000≒103000個というとんでもない数になってしまい，現在最速の計算機を1億台並べて並列計算しても，地球が滅亡するまでに計算が終了することはないでしょう．ちなみに，本研究室の計算機IBM RS6000は236.5MIPS（１秒間に約2億3千万回の演算を実行）というまあまあ速いものですが，これだと102983年以上かかります．何の工夫もない全探索ではせいぜい30～40商品の問題が限界です．これです．他にDOS/V機 Pentium4 2.8GHzにLinux を導入して数台稼動中！全探索の計算時間 n! 2n 1.1n 計算量の壁！巡回セールスマン問題ナップサック問題 n2 n 計算容易 n 問題サイズアルゴリズムの重要性計算量の壁をぶち破るには，巧妙な枝刈りを導入した高度な技法が要求されます．このために，個々の問題の数学的特徴を利用して，調べなければならない場合の数を劇的に削減するというのが腕のふるいどころで，ここに研究の難しさと，（成功した場合の）醍醐味があります． 10,000商品程度のナップサック問題ならば，良いアルゴリズムを使えばほんの数秒で解くことができます問題例（２）巡回セールスマン問題巡回セールスマン問題（TSP： Traveling Salesman Problem）すべての都市を最短距離で回る巡回路を見出せ. アメリカ532都市の問題 n 都市の場合，n! 通りの巡回路があり， n=100 でもこれは9.33×10157というとんでもない数になります. 普通の計算法ではどんなコンピュータを用いても，計算終了前に地球は破滅しているでしょう. TSP 研究の最前線右のような例題（ベンチマークといいます）について，世界中の研究者が覇を競っています米国13509都市の最短巡回路 Applegate, Bixby, Chvatal, Cook, Helsgaun による現在の世界記録（2004.5）スエーデンの24,978都市の最短巡回路 http://www.tsp.gatech.edu/sweden/index.html ＶＬＳＩの3038 素子の最短巡回路分枝限定法「計算量の壁をぶち破るには，枝刈りの技法が必要」と書きましたが，この枝刈りとはいったいどういうものでしょうか？この技法の代表例に分枝限定法があります．例えば，ナップサック問題ならば，図(A)のように全商品の組合せは2ｎ通りですが，分枝限定法では目的関数の上下界値と暫定値を用いて，それ以上探索しなくてもよい‘子問題’を図(B)のように決めます．上下界値のギャップが小さい場合，探索しなければならない子問題数が劇的に少なくなるというのがポイントです． 0 X1=1 (A) X2=1 X2= 0 X1=0 X2=1 X3=1 6 X2=0 ．．． 1 X2=1 X2=0 8 XN=1 XN=0 X3=0 X4=1 7 X2=1 (探索終了） 5 探索終了．．．ナップサック問題の例題の動き (x1,x2,x3,x4)=(0,1,1,0)が最適解となり任○堂と地図は持っていかない． 2 3 最適値=9 上界値=8=暫定値 (B) X4=0 暫定値=7 X2=0 4 暫定値=8 上界値=5<7 に更新 (探索終了）局所探索法局所探索法とは，適当な解 x に対して x に少しの変形を加えることによって得られる解の集合 N(x) （x の近傍と呼ばれる）内に x よりも良い解 x’ があれば，解を x=x’ に更新して，更新ができなくなるまでこの操作を続けていく方法です．近傍の採り方によりいろいろなやり方があります．卒研だと学生の自由な発想が発揮できる部分でもあります．ナップサック問題における例巡回セールスマン問題における例最適解 (2,3) (2,4) 8 9 (3,4) x’ 巡回路のなかから任意の枝を2本選んで, その部分を上のように入れかえて移りあう解の集合をN(x) とします．x’ における巡回路長が x におけるそれより短い場合，x を x’ に更新します． (2) 2 3 (2) (4) 4 3 (1,2 )7 7 x (1) (1,3) 6 (1,4) 5 x1 x2 局所最適解ナップサックに入っている商品とそうでない商品の対を入れ替えて移りあう解の集合を N(x) とします．上の図でx=x1のときは，最適解にたどり着くことができますが，x=x2（商品3だけ入っている状態）から出発すると，局所最適解に落ち込みます．最適解の概念図局所最適解全域最適解局所探索法実行可能解ｘ近傍 N(x) 一般に組合せ最適化問題には局所最適解が多数あり，局所探索法のみでは全域最適解を得られる望みはほとんどありません．それでは局所探索法は無意味なのでしょうか？いいえ，そうではありません．局所探索法のような近似解法は，短時間でまあまあの解を求めたい場合には強力な道具になります．また，分枝限定法などの厳密解法において下界値を得るのにも用いられます．近年では様々な近似解法が提案されており，それらの総称としてメタヒューリスティックスという言葉が用いられています． (このページの図は東京海洋大学の久保幹男先生の資料から無断で拝借しました）数理計画法との関連問題例（１）のナップサック問題でも紹介しましたが，組合せ最適化問題を数学的に定式化すると数理計画問題というものになります．数理計画法の代表例が，下のような線形計画問題です．右のような図をご覧になったことがありませんか？目的関数Ｚ＝３ｘ＋２ｙ → 最大制約条件４ｘ＋１ｙ ≦ ７２２ｘ＋２ｙ ≦ ４８１ｘ＋３ｙ ≦４８ｘ≧０，ｙ≧０組合せ最適化問題の場合には，特に斜線の領域内の格子点で最大化（最小化）を考える整数計画問題になります．数理計画問題としては大変難しい部類の問題です．数理計画問題の効率的解法自体，現在もホットな研究分野ですが，これまでの研究を取り入れたソフトウエアが幾つか市販されています．これをソルバー（値段は結構高い）といいますが，当研究室でも4種類程保有していて，卒研などに利用しています．計算の複雑さの理論データのサイズn に対して足し算，掛け算，大小比較などの基本演算をn の多項式回実行して計算が終了するような問題はクラスPの問題とよばれます（例えば，n 人の学生を身長順に並べ替えることはn2 回の比較・入れ替えでできます）．これに対して計算機科学ではクラスNPという問題群がよく出てきます．これは，非決定性計算という計算方式（莫大な数の計算機を並列に動かせるような仮想の方式）で演算の回数がn の多項式になるような問題の集合です．巡回セールスマン問題やナップザック問題もNPに属していますが，実は NPに属する全ての問題を巡回セールスマン問題（やナップザック問題）を使って解くことができます（ NP完全というとても高度な議論が必要です）． P⊆NP であることは自明ですが、実はP≠NP は証明されていません．P=NP?問題といって, 理論計算機科学最大の未解決問題です． NP NP完全 P （最小全域木，最短路，最大ネットワーク流，・・・) （巡回セールスマン問題，ナップザック問題，・・・) この問題はクレイ数学研究所が懸賞をかけている７つの難問の１つで，解ければ100万ドルもらえます．（http://www.claymath.org/）応用数学のノーベル賞と言われるネバンリンナ賞も計算量の理論の研究者が受賞しています． Razborov (90) Wigderson(9４) 最近の研究紹介本研究室の最近の研究成果です．専門書でもこれらの成果が引用されています． 1.Yamada, T., M. Futakawa and S. Kataoka, "Some exact algorithms for the knapsack sharing problem," European Journal of Operational Research, 106 (1998), 177-183. 2.Kataoka, S., N. Araki and T. Yamada, "Upper and lower bounding procedures for minimum rootes k-subtree problem", European Journal of Operational Research, 122 (2000), 561-569. 3.Yamada, T. and Y. Nasu, "Heuristic and exact algorithms for the simultaneous assignment problem," European Journal of Operational Research, 123 (2000), 531-542. 4.Samphaiboon N. and T. Yamada, "Heuristic and exact algorithms for the precedence constrained knapsack problem," J. Optimization Theory and Applications, 105 (2000), 659-676. 5.Yamada, T. and H. Kinoshita, "Finding all the negative cycles in a directed graph," Discrete Applied Mathematics, 118 (2002) 279-291. 6.Yamada, T., S. Kataoka and K. Watanabe, "Heuristic and Exact Algorithms for the Disjunctively Constrained Knapsack Problem", Information Processing Society of Japan Journal, Vol. 43, No. 9 (2002), 2864-2870. 7.Watanabe, K., T. Yamada and S. Kataoka, "A remark on the regularity of the coefficient matrix appearing in the charge simulation method", Japan J. Indust. Appl. Math., 20 (2002) 279-284. 8.Yamada, T., S. Kataoka and K. Watanabe, "Heuristic and exact algorithms for the spanning tree detection problem", to appear in Computers & Operations Research. 9.Yamada, T., K. Watanabe and S. Kataoka, "Algorithms to solve the knapsack constrained maximum spanning tree problem", to appear in Int. Journal of Computer Mathematics 卒業研究本科の卒業研究では，身近な題材から数理計画法, 組合せ最適化やシミュレーションなどに関連したテーマを選んでいます．４７期 (H15.3卒）中川貴裕「４色問題のためのアルゴリズムの研究」大城健司「防衛大学校における弁当食作業の現状と改善」近藤唯「カナダオオヤマネコの個体数変動に関する研究」白石真規「平面グラフにおけるラベルの自動生成」中村哲也「ルービック・キューブの解法に関する研究」田中清美「３工程直列システムの性能評価」４色問題４８期 (H16.3卒）阿久津勝俊「スケルトンパズルの解法」飯田一仁「限定された視界の下で起伏・障害のある面での経路探索」大嶋崇士「CP暗号の実装と拡張」高似良佳和「ナップザック選択問題における上下界値の評価」谷口俊介「対称オイラー方陣の構成法」谷口北ク斗「包絡分析法DEAによる勤務地比較」松延隆廣「ルービック・キューブの解法」ルービックキューブの解法修士論文研究科では，様々な数理計画法・組合せ最適化問題について，解法理論を研究し，アルゴリズムを開発・実装しています．また，国内外での研究発表及び論文投稿も活発に行なっています．３５期 (H10.3卒）那須靖「同時割当問題に関する研究」３６期 (H11.3卒）荒木紀雄「最小根付きk-部分木問題の厳密解法」木下治信「有効グラフにおける負サイクルの全列挙」ナタウット「順序制約付きナップサック問題の解法に関する研究」３７期 (H12.3卒）末澤浩道「マックスミン型多重ナップサック問題の解法」３８期 (H13.3卒）加治屋政誉司「最小拘束問題の解法と大規模問題への展望」高橋元法「全域木検出問題の解法」３９期 (H14.3卒）坂森義成「最小拘束問題の分枝限定法」４０期 (H15.3卒）間方仁一「進行方向片側のみサービス可能な巡回路問題」４１期 (H16.3卒）藤本晶子「一般化ナップサック共有問題の解法に関する研究」英文版が European Journal of Operational Research 採録決定！ http://www1.elsevier.com/homepage/sae/orms/eor/menu.htm