第3回 アルゴリズムと計算量 2019/2/24.

Presentation on theme: "第3回 アルゴリズムと計算量 2019/2/24."— Presentation transcript:

1 第3回 アルゴリズムと計算量 2019/2/24

2 n個の都市を訪問する巡回路の数は n!を近似的に表すStirlingの公式 Big Oh 記法 関数 の定数倍の大きさを気に
巡回セールスマン問題の計算量 n個の都市を訪問する巡回路の数は n!を近似的に表すStirlingの公式 Big Oh 記法 関数 の定数倍の大きさを気に しないときは無視できるという意味 2019/2/24

3 Stirlingの公式はn!がおよそnnであることを示唆
巡回セールスマン問題（計算量） Stirlingの公式はn!がおよそnnであることを示唆 巡回セールスマン問題はハノイの塔(2n)より困難 2019/2/24

4 関数がおおよそ何々以下であることを表すための記号 定義（O(f(n)): オーダーf(n))
O記号(Big O Notation) 関数がおおよそ何々以下であることを表すための記号 定義（O(f(n)): オーダーf(n)) 関数g(n)がO(f(n))であるとは，ある定数cとmが存在して，全てのn＞mに対して |g(n)|＜ c |f(n)| 　が成り立つこと（微積分のε-δ論法)． 多項式オーダー（良いアルゴリズム） 指数オーダー（悪いアルゴリズム） 2019/2/24

5 問題の大きさを表す代表的なパラメータ 入力サイズ たとえば 巡回セールスマン問題の場合は都市の数 最小木問題の場合はスパイの数
ハノイの塔の場合は板の数 最大安定集合問題の場合は首脳の数 2019/2/24

6 入力サイズの指数関数で計算時間が表現できるアルゴリズム
指数時間・多項式時間 指数時間アルゴリズム = 入力サイズの指数関数で計算時間が表現できるアルゴリズム 効率的でないアルゴリズムの代名詞 多項式時間アルゴリズム = 入力サイズの多項式関数で計算時間が表現できるアルゴリズム 効率的なアルゴリズムの代名詞 2019/2/24

7 100MIPS(million instructions per second)の計算機を用いた場合
指数時間アルゴリズムの計算時間 入力 サイズ 計算時間 10 20 30 40 50 100 100MIPS(million instructions per second)の計算機を用いた場合 1宙齢=150億年 2019/2/24

8 多項式時間アルゴリズムの計算時間 入力 サイズ 計算時間 10 20 30 40 50 100 1000 10000 2019/2/24

9 多項式時間アルゴリズムをひとつ見つければよい,簡単
クラスP 多項式時間アルゴリズムで解を求めることができる問題 の集合をクラスPと呼ぶ． ある問題がクラスPにはいっていることを証明 多項式時間アルゴリズムをひとつ見つければよい,簡単 ある問題がクラスPに入っていないことを証明 ???,難しい（背理法などを用いる） 2019/2/24

10 あるグラフに対してEuler閉路は存在するか否か
クラスNP 決定問題 答えがYESかNOの問題 例）Euler閉路問題 あるグラフに対してEuler閉路は存在するか否か クラスNP 決定問題がYESであるための「証拠」が，入力サイズの多項式 の大きさでおさえられるとき，その決定問題はクラスNPに入る． 例）Euler閉路問題 Euler閉路問題がYESであるための証拠はEuler閉路そのもの である．入力サイズはグラフの頂点数であり，Euler閉路を 通過する点の順番で表現した場合その大きさは点数の 多項式でおさえることができる． 2019/2/24

11 それを解くことができれば全てのNP問題を（帰着によって） 解くことができる問題=NP完全問題 クラスNPのなかで最も難しいクラス=NP完全
2019/2/24

12 NP NP完全 P 多くの人が信じて いる世界 NP=P NP完全 こういう可能性も ある PとNPとNP完全の包含関係
巡回セールスマン問題（決定問題） ナップサック問題（決定問題） 最大安定集合問題（決定問題） NP=P NP完全 P Euler閉路問題 最短路問題 最大流問題 最小費用流問題 線形計画問題 こういう可能性も ある 2019/2/24

13 解いた人にはクレイ数学研究所から100万ドルの賞金
P=NP? 多くの人が信じて いる世界 NP NP完全 NP=P NP完全 こういう可能性も ある P どちらが正しいかまだわかっていない 計算量理論の重要な問題 解いた人にはクレイ数学研究所から100万ドルの賞金 2019/2/24

14 どんなにがんばってもその問題を効率的に解く方法を 見つけられない 「僕もこの問題を解けないけれども， みんなも解くことができない」と説明する
NP完全=難しい? ある問題を解くことを上司に命令される ↓ どんなにがんばってもその問題を効率的に解く方法を 見つけられない 「僕もこの問題を解けないけれども， みんなも解くことができない」と説明する 2019/2/24

15 決定問題ではなく，少なくともNP完全問題以上に難しい問題
= NP困難問題 NP困難に属する問題 巡回セールスマン問題 最大安定集合問題 など他多数 2019/2/24