データ構造と
アルゴリズム
第十二回
知能情報学部
知能情報学科
新田直也
さまざまな問題とアルゴリズム

離散最適化問題




巡回セールスマン問題
最大クリーク問題
グラフ分割問題
グラフ問題



最短経路問題
ハミルトン閉路問題
最大マッチング問題
最短経路問題

出発地から目的地までの最短の経路を求める.


駅すぱあと
カーナビゲーション
http://www.me.sophia.ac.jp/or/lab/ishizuka/OC/spath_01.html
最短経路問題の定義

問題の定義:

重みつきグラフの2頂点が与えられたとき,その2点を結
ぶ重み和最小の経路を求めよ.
2
2
2
1
3
4
2
2
3
1
3
2
1
ダイクストラのアルゴリズム(1)

1.
近い頂点から順番に,最短経路と最短距離を求めていく.
 頂点毎のデータ: 各時点での最短距離,確定か否か
 辺毎のデータ: 最短経路に含まれるか否か
出発頂点までの最短距離を0とし確定にする
2
2
2
1
0
3
4
2
2
3
1
3
2
1
ダイクストラのアルゴリズム(2)
2.
確定した頂点の隣接頂点までの仮の最短距離を計算
2
1
0
2
2
1 42
2
3
3
3.
2
1
3
2
1
3
最も仮の最短距離が短い頂点を確定,最短経路も確定
2
1
0
3
2
2
2
1 42
2
3
3
1
3
2
1
ダイクストラのアルゴリズム(3)
2.
確定した頂点の隣接頂点までの仮の最短距離を計算
2
3
2
2
3
1
1
1 42
0
2
2
3
3.
2
3
3
5
1
最も仮の最短距離が短い頂点を確定,最短経路も確定
2
3
2
2
3
1
1
1 42
0
2
2
3
2
3
3
5
1
ダイクストラのアルゴリズム(4)
2.
確定した頂点の隣接頂点までの仮の最短距離を計算
2
3
2
2
3
1
1
1 42
0
2
2
3
3.
2
3
3
5
4
1
最も仮の最短距離が短い頂点を確定,最短経路も確定
2
3
2
2
3
1
1
1 42
0
2
2
3
2
3
3
4
1
ダイクストラのアルゴリズム(5)
2.
確定した頂点の隣接頂点までの仮の最短距離を計算
2
3
2
2
3
1
1
1 42 5
0
2
2
3
1
3
5
4
3
2
3.
最も仮の最短距離が短い頂点を確定,最短経路も確定
2
3
2
2
3
1
1
1 42 5
0
2
2
3
1
4
3
3
2
ダイクストラのアルゴリズム(6)
2.
確定した頂点の隣接頂点までの仮の最短距離を計算
2
3
2
2
3
1
1
6
1 42 5
0
2
2
3
1
3
5
4
3
2
3.
最も仮の最短距離が短い頂点を確定,最短経路も確定
2
3
2
2
3
1
1
6
1 42 5
0
2
2
3
1
4
3
3
2
ダイクストラのアルゴリズム(7)
2.
確定した頂点の隣接頂点までの仮の最短距離を計算
2
3
2
2
3
1
1
5
1 42 5
0
2
2
3
1
3
5
4
3
2
3.
最も仮の最短距離が短い頂点を確定,最短経路も確定
2
3
2
2
3
1
1
5
1 42 5
0
2
2
3
1
4
3
3
2
ダイクストラのアルゴリズムの
最悪時間計算量


頂点の数を n とする.
最悪時間計算量


頂点を確定する回数 → 最悪 n
一回の確定当たりの計算:



隣接頂点の数 → 最悪 n
仮の最短距離最小の頂点の探索 → 最悪 n
最悪時間計算量は,O(n2) (nの多項式である!!)
2
3
2
2
3
1
1
2
5
1 4 5
0
2
2
3
1
4
3
3
2
ハミルトン閉路問題

与えられたグラフが,全頂点をちょうど1回だけ通過
する閉路(ハミルトン閉路)を持つか否かを判定せよ.
→持つ
→持たない
ハミルトン閉路問題の解法(1)




適当な順番で頂点が番号付けられているとする.
ハミルトン閉路は頂点の置換(並び替え)で表現できる.
(以下の例では,<1,4,5,8,3,2,7,6>)
頂点数をnとしたとき,可能な置換の総数は,n!
すべての置換がハミルトン閉路になるわけではない.
例: <1,2,3,4,5,6,7,8>
1
6
2
7
8
5
4
3
ハミルトン閉路問題の解法(2)

ハミルトン閉路問題の総当り探索アルゴリズム:



n!通りの頂点の置換を列挙
各置換がハミルトン閉路を成しているか否かを判定
1つでもハミルトン閉路を成す置換があれば Yes を出力
して終了,すべて調べて見つからなければ No を出力
<1,2,3,4,5,6,7,8>
<1,2,3,4,5,6,8,7>
<1,2,3,4,5,7,6,8>
<1,2,3,4,5,7,8,6>
<1,2,3,4,5,8,6,7>
<1,2,3,4,5,8,7,6>
<1,2,3,4,6,5,7,8>
:
→
→
→
→
→
→
→
×
×
×
×
×
×
×
1
6
2
7
8
5
4
3
ハミルトン閉路問題の解法(3)

総当り探索アルゴリズムの最悪時間計算量:




与えられた置換がハミルトン閉路を成しているか否かの
判定: O(n)
置換の総数: n!個
最悪時間計算量: O(n!) × O(n) = O(2n)
(指数時間であることに注意!)
ハミルトン閉路問題を多項式時間で解くアルゴリズ
ムは知られていない.
巡回セールスマン問題

全都市を最短の
道のりで巡回してくる

商品の配送計画など
スウェーデンの24,978都市に
ついて解いたもの
(Xeron 2.8GHz dual CPU×96,
84.8 CPU years)
http://www.tsp.gatech.edu/
巡回セールスマン問題の定義

問題の定義:


重みつき完全グラフが与えられたとき,重み和最小のハミ
ルトン閉路を求めよ.
(完全グラフ:すべての頂点間に辺が存在しているグラフ)
(決定問題版)巡回セールスマン問題:
重み和が k 以下のハミルトン閉路が存在するか否か?
3
2
1
2 3 2
2
2 3
1
→重み和8
巡回セールスマン問題の解法
ハミルトン閉路問題同様,全頂点置換を総当り.
 総当り探索アルゴリズムの最悪時間計算量:





与えられた置換が長さ k 以下のハミルトン閉路を成して
いるか否かの判定: O(n)
置換の総数: n!個
最悪時間計算量: O(n!) × O(n) = O(2n)
巡回セールスマン問題を多項式時間で解くアルゴリ
ズムは知られていない.
問題のクラス

多項式時間問題(クラスP)

多項式時間で解くアルゴリズムが知られている問題



最短経路問題など…
ほとんどの実用的な問題はここに入る
非決定性多項式時間問題(クラスNP)

解の候補が与えられた時に,それが解となっているか否
かを多項式時間で判定できる問題



ハミルトン閉路問題,巡回セールスマン問題など
一般に,解くのに指数時間かかる
「手に負えない」問題とも言われる
P≠NP予想

クラスPとクラスNPは一致するか否かは未解決問題.
(P≠NP予想,またはP=NP問題という)



恐らく,情報科学分野で一番難しい問題.
ミレニアム懸賞問題の1つ.
(アメリカのクレイ数学研究所によって2000年に発表され
数学の7つの未解決問題,100万ドルの懸賞金)
NP完全問題:



NPの中で一番難しい問題.
ハミルトン閉路問題,決定問題版巡回セールスマン問題
は,NP完全問題.
NP完全問題を多項式時間で解くアルゴリズムを発見す
れば,P=NPを証明したことになる.
ダウンロード

12回目