1
アルゴリズムとデータ
構造
第１3回計算困難な問題を扱うには？
2016/01/20
アルゴリズムとデータ構造 2015
2
P≠NP予想
P≠NP予想とは
クラスPとクラスNPは等しくないという予想
P
ミレニアム懸賞問題の１つ
NP
ここに属する問題は存在するのか？
クラスP : 決定性チューリング機械において、多項式時間に判定可能な問題のクラス
(Pはpolynomial timeを意味する）
クラスNP : 非決定性チューリング機械において、多項式時間で判定可能な問題のクラス
yes となる証拠が与えられたとき、
その証拠が本当に正しいかどうかを多項式時間で検証可能な問題。
(NPはnondeterministic polynomial timeを意味する)
2016/01/20
アルゴリズムとデータ構造 2015
3
余談：ミレニアム懸賞問題とペレルマン
ミレニアム懸賞問題（millennium prize problems）：アメリカのクレイ数学研究所によって2000
年に発表された100万ドルの懸賞金がかけられている7つの数学上の未解決問題。
P≠NP予想
ホッジ予想
ポアンカレ予想 ※解決済
リーマン予想
ヤン-ミルズ方程式と質量ギャップ問題
ナビエ-ストークス方程式の解の存在と滑らかさ
バーチ・スウィンナートン＝ダイアー予想（BSD予想）
ポアンカレ予想の解決
2002-2003年にグリゴリー・ペレルマンがポアンカレ予想を証明したとする3つのプレ
プリント（専門誌未査読の論文）を発表。複数の数学者による4年の検証を経て証明
が正しいものと認められる。
グレゴリー•ペレルマン(1966-)
ロシアの数学者。16歳で国際数学オリンピックに出場し、全問満点の
金メダル。ステクロフ数学研究所に所属していたが2005年12月に退職
し、現在は実家で母親の年金で生活しているとされる。2006年にフィー
ルズ賞受賞を辞退。2010年にはミレニアム賞受賞を辞退。
2016/01/20
アルゴリズムとデータ構造 2015
計算困難な問題とは？
4
NP
NP困難
P
クラスNP困難 : クラスNPに属するすべての問題から
多項式時間還元可能な問題のクラス
クラスNP完全 : クラスNP困難かつクラスNPに属する
問題のクラス
NP完全
つまり、NP困難な問題が決定性チューリング機械で多項式時間で解けたら、
全てのクラスNPの問題は決定性チューリング機械で多項式時間で解ける。
P=NP!
NP困難な問題
巡回セールスマン問題
ナップサック問題
特殊ケース
ナップサック問題：容量 C のナップサックが一つと、
n 個の品物（各々、価値 pi, 容積 ci）が与えられた
とき、ナップサックの容量 C を超えない範囲でいく
つかの品物をナップサックに詰め、ナップサックに
入れた品物の価値の和を最大化する問題
2016/01/20
NP完全な問題
ハミルトン閉路問題
部分和問題
部分和問題：計算複雑性理論・暗号理論におけ
る問題で、与えられた n 個の整数 a1,...,an から
部分集合をうまく選んで、その集合内の数の和が
与えられた数 N に等しくなるようにできるかどう
かを判定する問題。
アルゴリズムとデータ構造 2015
5
分枝限定法―しらみつぶし法の効率化―
しらみつぶし法(exhaustive search)とは
解の候補をすべてしらみつぶしに探索する方法
効率的なしらみつぶし法の実現のために必要なこと
・すべての解の候補を系統的に列挙する方法
・最適解にはなりえない候補の探索を早い段階で打ち切ること
分枝限定法(branch-and-bound)とは、
問題を次々と場合分けし（分枝操作）、最適解になりえない場合は
分枝操作を打ち切る（限定操作）ことにより効率よく解を探索する方法
2016/01/20
アルゴリズムとデータ構造 2015
6
巡回セールスマン問題とは
グラフGのハミルトン閉路とは
Gの各頂点をちょうど一度ずつ通る閉路
v4
2
1
4
v0
v4
1
3
2
v4
v3
1
存在するか
否かを判定
する問題は
NP完全
v3
v0
v3
v0
4
v1
3
v1
v2
NP困難
v2
v1
v2
巡回セールスマン問題(traveling salesman problem)とは
与えられた辺に重みの付いたグラフにおいて、
辺の重みの総和が最小となるハミルトン閉路を求める問題
v4
2
1
4
v0
3
1
3
4
v3 v
0
4
v1
2
1
1
2
2016/01/20
v4
v2
3
2
1
v3
1
4
v1
v2
3
アルゴリズムとデータ構造
2015
7
v4
すべての解の候補を組織的に列挙する方法
深さ優先探索を行うことにより全てのハミルトン閉路を列挙できる
大域変数
int n; /*頂点数*/
int visit[n];
/* 0: 未訪問
i: i番目に訪問済み */
int adjlist[n]; /*隣接リスト*/
main
{
for(v∈V) visit[v]=0;
SEARCH(v0,0);
}
v1
2016/01/20
v3
v0
v2
v1
v2
v2
逆回り
※頂点vに隣接する頂点は隣接リストadjlist[v]で与えらるものとする。
void SEARCH(int v, int level)
{
visit[v]=++level;
if(level==n) {
if(v0∈adjlist[v]) ハミルトン閉路を出力;
}
else {
for(w∈adjlist[v]) {
if(visit[w]==0) SEARCH(w,level);
}
}
visit[v]=0;
}
v3
v0
v4
v1
逆回り
v3
v4
v4
v2
v1
v3
v3 v4 v2 v4 v2 v3 v3 v4 v1 v4 v1 v3 v2 v3 v 1 v3 v1 v2
v4 v3 v4 v2 v3 v2 v4 v3 v4 v1 v3 v1 v3 v2 v3 v1 v2 v1
v0
v0 v0
v0 v0
v0 v0
v0
v0
v0 v0 v0
アルゴリズムとデータ構造 2015
8void SEARCH(int v, int level)
{
visit[v]=++level;
if(level==n) {
if(v0∈adjlist[v]) ハミルトン閉路を出力;
}
else {
for(w∈adjlist[v]) {
探索木の枝刈り
v4
v3
v0
if(visit[w]==0 && (w!=v2||visit[v1]>0)) SEARCH(w,level);
}
}
visit[v]=0;
}
逆回り
v0
v2
v1
v2
v3
v4
v1
v1
2頂点v1がv2よりも
先に訪れる場合のみ列挙
同じ閉路の逆回りの探索は無駄!
逆回り
v3
v4
v4
v2
v1
v2
v0
枝刈り
(pruning)
v4
v1
v3
v2
v3
v4
v1
v3
v3 v4 v2 v4 v2 v3 v3 v4 v1 v4 v1 v3 v2 v3 v1 v3 v1 v2
v3 v4 v2 v4 v2 v3
v2 v3
v1
v4 v3 v4 v2 v3 v2 v4 v3 v 4 v1 v3 v1 v3 v2 v3 v1 v2 v1
v4 v3 v4 v2 v3 v2
v3 v2
v2
v0
v0
v0
v0
2016/01/20
v0 v0
v0 v0
v0 v0
v0
v0
v0 v0 v0
v0 v0
v0
アルゴリズムとデータ構造 2015
9
巡回セールスマン問題を分枝限定法で解く(1)
巡回セールスマン問題はコスト最小のハミルトン閉路を求める問題
ある時点までに見つかっているハミルトン閉路の最小コストをUとすれば、
ある場合分けに含まれるすべての閉路のコストがU以上とわかれば、
その場合分けの探索を打ち切ることが可能。
v4
2
1
4
v0
1
3
v3
1
2
Σv∈V vを端点とする異なる２辺の重みの和の最小値
2
4
v1
2016/01/20
与えられたグラフに含まれるハミルトン閉路の
コストの下界は？
3
v2
(1+2)+(1+2)+(1+3)+(1+2)+(1+1)
=
=7.5
2
アルゴリズムとデータ構造 2015
10
巡回セールスマン問題を分枝限定法で解く(2)
途中まで路が与えられた場合のハミルトン閉路のコストの下界は？
Σv∈V vを端点とする異なる２辺(与えられた路に含まれる辺は必ず選択)の重みの和の最小値
2
v4
2
1
4
v0
1
3
v3
1
2
(1+2)+(2+3)+(3+1)+(1+2)+(1+1)
=
=8.5
2
4
v1
2016/01/20
3
v2
アルゴリズムとデータ構造 2015
11
分枝限定法による枝刈り
7.5
v0
v4
8.5
v2
11
12
12
7.5
v3
v4 7.5
11.5
v4
10
v1
8
v3
8
8.5
v3 v4
9 8
v2 v4
9
v4 v3
9 8
v4 v2
v3 v2
v3 v2
9
v0 v0
v0
v0
v0
U=12
9
2
1
7.5
v1
v2 v3
v 2 v3
v1
8.5
v2
4
v0
1
3
v3
1
2
4
v1
3
v2
10
v0
U=9
※左の子から深さ優先探索であることに注意
2016/01/20
アルゴリズムとデータ構造 2015
12
局所探索法
最適化問題(optimization problem)とは
制約条件を満たす解の中から最も目的関数の値が良い解（最適解）を求める問題
制約条件を満たす解のことを(実行)可能解(feasible solution)と呼ぶ。
[例] 巡回セールスマン問題の解C⊆E （Eは辺の集合）
制約条件： Cはハミルトン閉路
目的関数： Cに含まれる辺の重みの和（小さいほど良い）
局所探索法(local search, 逐次改善法, 近傍探索法)とは
適当な可能解sを初期解とし、sの近傍においてsより良い解を選び、sと入れ替えるという
操作を逐次行うことにより最適解に近い解（近似解）を探索する方法
局所探索では、局所最適解が得られる。
目的関数値
真の最適解とは限らない
局所最適解
解sが局所最適解(locally optimal solution)
局所最適解
大域最適解
def
⇔sの近傍にsより良い解が存在しない
解sが大域最適解(globally optimal solution)
def
2016/01/20
実行可能解の空間
⇔sは真の最適解
アルゴリズムとデータ構造 2015
13
局所探索の例（巡回セールスマン問題）
解Cの近傍
解C
u
解C’
v
v’
u
v
v’
u’
u’
(u,v),(u’,v’)はCに含まれる隣接
しない辺で閉路Cにおいて
u,v,u’,v’の順に現れるものとする
v4
2
1
4
v0
4
v1
初期解
2016/01/20
v3
1
2
3
2
1
1
3
v4
v4
v2
コスト12
4
v0
1
3
v3
1
2
4
v1
3
コスト10
2
1
v2
4
v0
1
3
v3
1
2
4
v1
3
v2
コスト9
アルゴリズムとデータ構造 2015
14
発見的アルゴリズム
近似アルゴリズム(approximation algorithm)とは
近似解を求めるアルゴリズム
近似アルゴリズム
近似の精度が保証されないアルゴリズム
＝発見的アルゴリズム(heuristic algorithm)
近似の精度が保証され
るアルゴリズム
メタヒューリスティックとは
特定の問題に依存しない発見的アルゴリズムのこと
代表的なメタヒューリスティック
焼きなまし法(simulated annealing)
タブー探索(taboo search)
ニューラルネットワーク(neural network)
遺伝的アルゴリズム(GA, genetic algorithm)
2016/01/20
誰でもそこそこの性能のア
ルゴリズムを設計できる実
用的なアルゴリズム手法と
して重宝されている
アルゴリズムとデータ構造 2015
15
発見的手法における局所最適解からの脱出の工夫
タブー探索
局所最適解
大域最適解
解が改善される近傍がない場合は、勾配
が最も小さい方へ上ってみる。同じところを
ぐるぐる回ることをさけるために一度たどっ
た場所をタブーリストに登録しておき、二度
と訪れないようにする。
焼きなまし法 (シミュレーティド・アニーリング)
現在の解よりも悪い解へもある確率で遷移させる。どの程度の
確率で遷移するかは温度パラメータの関数で表す。最初は温
度（遷移確率）を高くしておき、徐々に温度を下げる（遷移確率
を小さくする）ことにより最適解に収束させる。
2016/01/20
アルゴリズムとデータ構造 2015

3位 3位