2015. 7.29
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Keiichi MIYAJIMA
難しい問題とその対応
問題の分類
コンピュータはすべての問題を解決できるわけではない。
例: 2つのn個の文字列の組
x  ( x1 , x 2 ,  , x n ),
y  ( y1 , y 2 ,  , y n )
が与えられる。
x y から対応する文字列を選んでそれぞれ連
xi1 , xi2 ,  , xi j  y i1 , y i2 ,  , y i j
となる選び方 i , i ,  , i が存在するか否かを判定せよ。
1 2
j
重複を許して、 と
接したとき
問題の分類
例えば
x  ( a , aba ), y  ( aa , b )
とすると、
i1  1, i2  2 , i3  1 とおけば、
x1 x 2 x 3  aabaa  y1 y 2 y 3
となり、答えは“yes”。
一方、
x  ( a , aba , bb ), y  ( ba , b , abb ) とすると、
i1 として1,2,3のどれをとっても先頭の文字列が異なるので、
答えは“no”となる。
x, y
このように、
を具体的に与えられれば、答えを求めることが
できる場合があるが、
を一般的な文字列の組としたとき、
この問題を解くアルゴリズムは存在しない。
x, y
問題の分類
コンピュータはすべての問題を解決できるわけではない。
問題を解くアルゴリズムが存在しない問題:
非可解
問題を解くアルゴリズムが存在する問題:
可解,計算可能
問題の集合
非可解
可解
問題の分類
コンピュータは可解であっても問題を解決できるわけで
はない。
効率の良いアルゴリズムが存在しないので、実際上は
説くことが難しい問題:
手に負えない問題
(intractable)
効率の良いアルゴリズムが存在
する問題:
扱える問題
(tractable)
問題の集合
非可解
手に負えない
扱える
可解
問題の分類
コンピュータは可解であっても問題を解決できるわけで
はない。
効率の良いアルゴリズムが存在しないので、実際上は
説くことが難しい問題:
NP問題
(Non-deterministic Polynomial)
効率の良いアルゴリズムが存在
する問題:
P問題
(Polynomial)
問題の集合
非可解
可解
NP
P
NP-完全問題
NP問題の中でももっとも難しいもの
NP-完全問題
(NP-Complete)
もし、どれか一つのNP-完全問題に効率の良いアルゴリ
ズムが存在するならば、すべてのNP-完全問題に効率の
良いアルゴリズムが存在する。
問題の集合
非可解
NP完全
可解
NP
P
NP-完全問題の例
あなたは冒険者である。冒険の末、あなたはn個の宝の
山を見つけた。しかし、あなたの背負い袋には最大で WMAX
の重さまでしか宝を入れられない。
今、宝1の価値が v1で重さが w1、宝2の価値が v2で重
さが w2 、・・・宝nの価値が vnで重さが wn であるとき、
どのように宝を選べば背負い袋に入る宝の価値の合計
が最大となるか?
その他、巡回セールスマン問題など・・・
NP-完全問題の例
例のような、ナップザック問題や巡回セールスマン問題
のような問題のことを
最適化問題
一見すると簡単なように見えるが・・・
“最適”なものを見つけるためには、すべての可能な組み
合わせを試して、その中から“最適”なものを見つけなけ
ればならない。
n!
Cr 
r!( n  r )!
階乗は指数関数で近似されるので n が大きくなると爆発的に大きく
n
なる
近似アルゴリズム
通常、NPに属する問題をコンピュータで扱うときは、解の
精度を少し犠牲にして、その代わりに計算時間を現実的
なものにしようと考える。
近似アルゴリズム
(approximation algorithm)
近似アルゴリズムで得た解を
近似解、近似値
実際のコンピュータ制御で動くものは、ほとんどすべて
近似解で動いている。
P versus NP
クラスPとクラスNPにおいて
に示される。
では、果たして
大方の予想は P
いない。
P  NPであることは容易
P  NP
P  NP
なのか?
なのか?
 NP であるが、現在でもわかって
一番最初に証明できた者には賞金100万USドル!!
本日のまとめ
TCP/IPアプリケーション
• P問題,NP問題
本日の課題
本日の課題はありません。
確認試験について
講義の最後に口頭で説明します。
日時:8月5日(水)10:30~
場所:E1棟23教室
ダウンロード

難しい問題とその対応