PowerPoint プレゼンテーション

第3回
• アルゴリズムと計算量
2015/9/30
1
巡回セールスマン問題の計算量
n個の都市を訪問する巡回路の数は
n 1 n  2 3 2 1  n 1!
n!を近似的に表すStirlingの公式
n
1
1
139
n 
 1 
n!  2n   1 


 O 4  
2
3
 e   12n 288n 51840n
 n 
Big Oh 記法
関数1 / n 4 の定数倍の大きさを気に
しないときは無視できるという意味
2015/9/30
2
巡回セールスマン問題（計算量）
Stirlingの公式はn!がおよそnnであることを示唆
巡回セールスマン問題はハノイの塔(2n)より困難
2015/9/30
3
O記号(Big O Notation)
• 関数がおおよそ何々以下であることを表すための記号
• 定義（O(f(n)): オーダーf(n))
– 関数g(n)がO(f(n))であるとは，ある定数cとmが存在し
て，全てのn＞mに対して |g(n)|＜ c |f(n)|
が成り立つこと（微積分のε-δ論法)．
多項式オーダー（良いアルゴリズム）
指数オーダー（悪いアルゴリズム）
2015/9/30
4
入力サイズ
問題の大きさを表す代表的なパラメータ
入力サイズ
たとえば
巡回セールスマン問題の場合は都市の数
最小木問題の場合はスパイの数
ハノイの塔の場合は板の数
最大安定集合問題の場合は首脳の数
2015/9/30
5
指数時間・多項式時間
指数時間アルゴリズム
=
入力サイズの指数関数で計算時間が表現できるアルゴリズム
効率的でないアルゴリズムの代名詞
多項式時間アルゴリズム
=
入力サイズの多項式関数で計算時間が表現できるアルゴリズム
効率的なアルゴリズムの代名詞
2015/9/30
6
指数時間アルゴリズムの計算時間
入力
サイズ
計算時間
2
n
2
n 2
n
10
2.1105 秒 0.001 秒
20
1.05 102 秒 4.19 秒
10 秒
2.68時間
30
40
50
3.05時間
130日
100
26798 宙齢
204日
893年
2.68 108 宙齢
3
n
n!
5.9 104 秒
0.036秒
34.9秒
771年
23.8日
5.61106 宙齢
3.86世紀
1.72 1022宙齢
0.015宙齢
6.42 1038宙齢
1.09 1022宙齢
1.77 10132宙齢
100MIPS(million instructions per second)の計算機を用いた場合
1宙齢=150億年
2015/9/30
7
多項式時間アルゴリズムの計算時間
入力
計算時間
3
サイズ
n n log 2 n n 2
n
1107 秒 3.32 10 秒 110 秒 110 秒
10
2 10 秒 8.64 10 秒 4 10 秒
8 10 秒
20
3 10 秒 1.47 10 秒 9 10 秒 2.7 10 秒
30
4 10 秒 2.13 10 秒 1.6 10 秒 6.4 10 秒
40
5 10 秒 2.82 10 秒 2.5 10 秒 1.25 10 秒
50
0.01秒
110 秒 6.64 10 秒 110 秒
100
10秒
110 秒 9.97 10 秒 110 秒
1000
1秒
2.78時間
10000 110 秒 1.3310 秒
7
7
6
5
0.0015秒
6
5
0.032秒
7
6
7
6
5
7
6
5
6
6
4
1.67分
5
2
115日
5
4
2015/9/30
7
n
5
3
6
4
0.243秒
4
1.02秒
3
3.13秒
31世紀
8
クラスP
多項式時間アルゴリズムで解を求めることができる問題
の集合をクラスPと呼ぶ．
ある問題がクラスPにはいっていることを証明
多項式時間アルゴリズムをひとつ見つければよい,簡単
ある問題がクラスPに入っていないことを証明
???,難しい（背理法などを用いる）
2015/9/30
9
クラスNP
決定問題
答えがYESかNOの問題
例）Euler閉路問題
あるグラフに対してEuler閉路は存在するか否か
クラスNP
決定問題がYESであるための「証拠」が，入力サイズの多項式
の大きさでおさえられるとき，その決定問題はクラスNPに入る．
例）Euler閉路問題
Euler閉路問題がYESであるための証拠はEuler閉路そのもの
である．入力サイズはグラフの頂点数であり，Euler閉路を
通過する点の順番で表現した場合その大きさは点数の
多項式でおさえることができる．
2015/9/30
10
NP完全
クラスNPに属する問題=NP問題
それを解くことができれば全てのNP問題を（帰着によって）
解くことができる問題=NP完全問題
クラスNPのなかで最も難しいクラス=NP完全
2015/9/30
11
PとNPとNP完全の包含関係
NP
多くの人が信じて
いる世界
NP完全
巡回セールスマン問題（決定問題）
ナップサック問題（決定問題）
最大安定集合問題（決定問題）
NP=P
NP完全
P
Euler閉路問題
最短路問題
最大流問題
最小費用流問題
線形計画問題
2015/9/30
こういう可能性も
ある
12
P=NP?
NP
多くの人が信じて
いる世界
NP完全
P
NP=P
NP完全
こういう可能性も
ある
どちらが正しいかまだわかっていない
計算量理論の重要な問題
解いた人にはクレイ数学研究所から100万ドルの賞金
2015/9/30
13
NP完全=難しい?
ある問題を解くことを上司に命令される
↓
どんなにがんばってもその問題を効率的に解く方法を
見つけられない
↓
「僕もこの問題を解けないけれども，
みんなも解くことができない」と説明する
2015/9/30
14
NP困難
決定問題ではなく，少なくともNP完全問題以上に難しい問題
=
NP困難問題
NP困難に属する問題
•巡回セールスマン問題
•最大安定集合問題
など他多数
2015/9/30
15

Download Report