http://www.nda.ac.jp/~yamada/labo/
理工学3号館1階北側中央部分
教
授 山田 武夫 [email protected]
助教授 片岡 靖詞 [email protected]
助
手 渡辺宏太郎 [email protected]
情報数理研究室の研究って?
NP困難問題とよばれる,普通に計算するとべらぼうに時間のかかる問
題を,短時間で計算するための工夫(アルゴリズムの研究・開発)をし
ています.具体的には下のような問題と,それらの応用が対象です.
• 組合せ最適化 (より一般的には数理計画法)
– ナップサック問題
• 一定の大きさのナップサックに収容する商品の組で価値の総和が最大
となるものを求める問題です
– 巡回セールスマン問題
• n 個の都市の全てを最短距離で訪問するにはどのように回れば良いか
という問題です
– グラフ(点と線からなる図形)の計算に関する問題
• 各中継点を結ぶ通信ネットワークで総距離最短のものを求める問題や,
• 出発点から目的地まで最短の経路を見つける問題,などです
●
他に,シミュレーション,微分方程式の数値解法の研究も …
組合せ最適化関連図
アルゴリズムの世界
(いろいろな解法が
あります)
数理計画法
○ 単体法
○ 内点法
○ 整数計画法
○ 非線形最適化
組合せ
最適化問題
近似解法
○欲張り(Greedy)法
○局所探索(LS)法
○ Lagrange緩和
計算機による実装
○ プログラミング
○ 可視化
○ 数値実験
現実問題への応用
○ 物流,交通,輸送など
厳密解法
○ 分枝限定法
釘づけテスト,上下
界値の高速な算出
etc.
○ 動的計画法
(ドイツの15000都市についての
巡回セールスマン問題の解:セー
ルスマンが通った経路)
問題例(1) ナップサック問題
1(任○堂)
2(お昼)
3(デジカメ)
4(地図)
重量1
重量3
重量3
重量3
価値2
価値5
価値4
価値3
重量W まで収納可能なナップサックにできるだけ価値の総和が
大きくなるように商品を詰め込もうという問題です
商品iの価値をpi,重量をwiと書けば次のように定式化できます
ナップサック
重量W=6まで収納可
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
です
計算量の壁
ナップサック問題は,2n 個の組み合わせを全て調べれば解くことができます(全探索).
しかし,10000商品の場合その数は210000≒103000個というとんでもない数になってしまい,
現在最速の計算機を1億台並べて並列計算しても,地球が滅亡するまでに計算が終了
することはないでしょう .
ちなみに,本研究室の計算機IBM RS6000は236.5MIPS(1秒間に約2億3千万回の演
算を実行)というまあまあ速いものですが,これだと102983年以上かかります.何の工夫
もない全探索ではせいぜい30~40商品の問題が限界です.
これです.他にDOS/V機
Pentium4 2.8GHzにLinux
を導入して数台稼動中!
全探索の
計算時間
n!
2n
1.1n
計算量
の壁!
巡回セールスマ
ン問題
ナップサック問
題
n2
n
計算容
易
n
問題サイズ
アルゴリズムの重要性
計算量の壁をぶち破るには,巧妙な枝刈り を導入した高度な技法が要求されま
す.このために,個々の問題の数学的特徴を利用して,調べなければならない場
合の数を劇的に削減するというのが腕のふるいどころで,ここに研究の難しさと,
(成功した場合の)醍醐味があります.
10,000商品程度のナップサック
問題ならば,良いアルゴリズム
を使えばほんの数秒で解くこと
ができます
問題例(2) 巡回セールスマン問題
巡回セールスマン問題 (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
VLSIの3038 素子の最短巡回路
分枝限定法
「計算量の壁をぶち破るには,枝刈り の技法が必要」と書きましたが,この枝刈りとはいったいどうい
うものでしょうか? この技法の代表例に分枝限定法があります.例えば,ナップサック問題ならば,
図(A)のように全商品の組合せは2n 通りですが,分枝限定法では目的関数の上下界値と暫定値を用
いて,それ以上探索しなくてもよい‘子問題’を図(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だけ入っ
ている状態)から出発すると,局所最適解に落
ち込みます.
最適解の概念図
局所最適解
全域最適解
局所探索法
実行可能解x
近傍 N(x)
一般に組合せ最適化問題には局所最適解が多数あり,局所探索法のみでは全域最適解を
得られる望みはほとんどありません.それでは局所探索法は無意味なのでしょうか?
いいえ,そうではありません.局所探索法のような近似解法は,短時間でまあまあの解を求
めたい場合には強力な道具になります.また,分枝限定法などの厳密解法において下界値
を得るのにも用いられます. 近年では様々な近似解法が提案されており,それらの総称と
してメタヒューリスティックスという言葉が用いられています.
(このページの図は東京海洋大学の久保幹男先生の資料から無断で拝借しました)
数理計画法との関連
問題例(1)のナップサック問題でも紹介しましたが,組
合せ最適化問題を数学的に定式化すると数理計画問
題というものになります.数理計画法の代表例が,下の
ような線形計画問題です.右のような図をご覧になった
ことがありませんか?
目的関数
Z =3x + 2y → 最大
制約条件
4x +1y ≦ 72
2x +2y ≦ 48
1x + 3y ≦48
x≧0,y≧0
組合せ最適化問題の場合には,特に斜線の領域内の
格子点で最大化(最小化)を考える整数計画問題になり
ます.数理計画問題としては大変難しい部類の問題で
す.
数理計画問題の効率的解法自体,現在もホットな研究
分野ですが,これまでの研究を取り入れたソフトウエア
が幾つか市販されています.これをソルバー(値段は結
構高い)といいますが,当研究室でも4種類程保有して
いて,卒研などに利用しています.
計算の複雑さの理論
データのサイズn に対して足し算,掛け算,大小比較などの基本演算をn の多項式回実行して計
算が終了するような問題はクラスPの問題とよばれます(例えば,n 人の学生を身長順に並べ替え
ることはn2 回の比較・入れ替えでできます).これに対して計算機科学ではクラスNPという問題群
がよく出てきます.これは,非決定性計算という計算方式(莫大な数の計算機を並列に動かせるよ
うな仮想の方式)で演算の回数がn の多項式になるような問題の集合です.巡回セールスマン問
題やナップザック問題もNPに属していますが,実は NPに属する全ての問題を巡回セールスマン
問題(やナップザック問題)を使って解くことができます( NP完全というとても高度な議論が必要で
す).
P⊆NP であることは自明ですが、実はP≠NP は
証明されていません.P=NP?問題といって, 理論
計算機科学最大の未解決問題です.
NP
NP完全
P
(最小全域木,最短路,最
大ネットワーク流,・・・)
(巡回セールスマン
問題,ナップザック
問題,・・・)
この問題はクレイ数学研究所が懸賞をかけている
7つの難問の1つで,解ければ100万ドルもらえます.
(http://www.claymath.org/)
応用数学のノーベル賞と言
われるネバンリンナ賞も計算
量の理論の研究者が受賞し
ています.
Razborov
(90)
Wigderson(94)
最近の研究紹介
本研究室の最近の研究成果です.専門書でもこれらの成果が引用されています.
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
卒業研究
本科の卒業研究では,身近な題材から数理計画法, 組合せ最適化やシミュレー
ションなどに関連したテーマを選んでいます.
47期 (H15.3卒)
中川貴裕
「4色問題のためのアルゴリズムの研究」
大城健司
「防衛大学校における弁当食作業の現状と改善」
近藤唯
「カナダオオヤマネコの個体数変動に関する研究」
白石真規
「平面グラフにおけるラベルの自動生成」
中村哲也
「ルービック・キューブの解法に関する研究」
田中清美
「3工程直列システムの性能評価」
4色問題
48期 (H16.3卒)
阿久津勝俊 「スケルトンパズルの解法」
飯田一仁
「限定された視界の下で起伏・障害のある面での経路探索」
大嶋崇士
「CP暗号の実装と拡張」
高似良佳和 「ナップザック選択問題における上下界値の評価」
谷口俊介
「対称オイラー方陣の構成法」
谷口北ク斗 「包絡分析法DEAによる勤務地比較」
松延隆廣
「ルービック・キューブの解法」
ルービックキューブの解法
修士論文
研究科では,様々な数理計画法・組合せ最適化問題について,解法理論を研究し,
アルゴリズムを開発・実装しています.また,国内外での研究発表及び論文投稿も
活発に行なっています.
35期 (H10.3卒)
那須 靖
「同時割当問題に関する研究」
36期 (H11.3卒)
荒木紀雄
「最小根付きk-部分木問題の厳密解法 」
木下治信
「有効グラフにおける負サイクルの全列挙」
ナタウット
「順序制約付きナップサック問題の解法に関する研究」
37期 (H12.3卒)
末澤浩道
「マックスミン型多重ナップサック問題の解法」
38期 (H13.3卒)
加治屋政誉司 「最小拘束問題の解法と大規模問題への展望 」
高橋元法
「全域木検出問題の解法 」
39期 (H14.3卒)
坂森義成
「最小拘束問題の分枝限定法 」
40期 (H15.3卒)
間方仁一
「進行方向片側のみサービス可能な巡回路問題 」
41期 (H16.3卒)
藤本晶子
「一般化ナップサック共有問題の解法に関する研究 」
英文版が European Journal of Operational Research 採録決定!
http://www1.elsevier.com/homepage/sae/orms/eor/menu.htm
ダウンロード

研究室紹介