1

NP 完全問題に対するアルゴリズムについて学ぶØ 厳密アルゴリズムと近似アルゴリズム
Ø Metric TSP の 2 近似アルゴリズム
Ø 最小全域木を求める Kruskal アルゴリズム

2

3

NP 完全問題は次の 2 つを満たす問題．
Ø クラス NP に属する
Ø クラス NP に属する任意の問題から多項式時間還元可能P（決定性多項式時間）では解けないと思われている
入力サイズが大きくなると膨大な計算時間を要する可能性

世の中の様々な問題は NP 完全問題に定式化できることが多い
諦めずに何らかの形で解く必要がある．
4

厳密アルゴリズム

近似アルゴリズムØ 与えられた問題の厳密解を求める．

Ø 与えられた問題の近似解を求める．

Ø 計算時間は指数時間でもよい．

Ø 計算時間は多項式時間．

Ø 実世界では，厳密解を要求される

Ø 実世界では，一定の性能を保証で状況はある．その解以外では全くきる解を高速に見つけられること意味をなさない状況も多々ある．

が好ましい状況は多い．

Ø できる限り高速に解を求めるアルゴリズムが求められる．

Ø できる限り良質な解を求めるアルゴリズムが求められる．

トレードオフの関係
5巡回セールスマン問題 ( Traveling Salesman Problem ）入力：重み付き無向グラフ G
問：重みの総和が最小のハミルトン閉路を求めよ．

出力：重みの総和が最小のハミルトン閉路（あれば）133533224231452221532124456Metric TSP：TSP に次の制約を加えたもの．
Ø 入力グラフを完全グラフに限定．
Ø 2 点 𝑥, 𝑦 の間の重みを w 𝑥, 𝑦 とするとき，グラフ G の任意の 3 頂点 𝐴, 𝐵, 𝐶 について，下記の三角不等式を満たす．
𝑤 𝐴, 𝐵 ≤ 𝑤 𝐴, 𝐶 + 𝑤(𝐵, 𝐶)
三角不等式を満たさない
AA23

三角不等式を満たす

11BC1BC17

Metric TSP は NP 困難（決定問題では NP 完全問題）
なので、最適解を多項式時間で求めることは難しい
よい近似度を入力サイズの多項式時間で求めるアルゴリズムの能力を「近似度」で比較する．
近似度：

アルゴリズムが出力する解のコストの最悪値
最適解のコストc 近似アルゴリズム ： 近似度

c を満たすアルゴリズム
8多項式時間近似アルゴリズム
Ø 2 近似 [Folklore]Ø 1.5 近似 [Cristofides 1976]
Ø 1.5-10-36 近似 [Karlin, Klein, and Graham 2020]

近似困難性
Ø P=NP でないかぎり、123/122 近似多項式時間アルゴリズ
ムは存在しない [Karpinski, Lampis, and Schmied 2006]9厳密アルゴリズムは動的計画法（ Dynamic Programming ）による O(n22n) 時間アルゴリズムより本質的に高速なアルゴリズ
ムは知られていない

動的計画法での解き方については調べてみてください
日本語の記事も英語の記事もいっぱい出てきます

10

11

閉路（ループ）のないグラフ
Ø 左は 1-2-3-1 というループがあるので木ではない
Ø 右は閉路がないので木113232454512グラフのうち一部の頂点や辺を利用したグラフ
Ø 右 2 つは一番左の部分グラフ

1133222451454513部分グラフのうち全頂点が連結している木Ø 右 2 つは一番左の全域木となっているØ 次スライドで一番左のグラフのすべての全域木を列挙

1133224513245451411133224245145123255134332454515

重み付きグラフの全域木の中で辺の重みの総和が最小のもの
Ø 左のグラフの最小全域木は右の木

4111132224314352414516重み付きグラフの全域木の中で辺の重みの総和が最小のもの
11432214453444532145143244132212112141144351435132443517最小全域木を使った 2 近似アルゴリズム
1.

グラフ G の最小全域木 T を求める

2.

T の各辺を二重にしたグラフ Tʼ を作成する

3.

Tʼ 上で全ての頂点を通る巡回路 Cを求める※ 同じ頂点を 2 度通ってよい

4.

C のうち 2 度目に通る頂点をショートカットした巡回路Cʼ を求める

5.

Cʼ と閉路の辺の重みの総和を出力する
18

1．最小全域木 T を求める
Kruskal 法（後で説明）や Prim 法を用いればよい

112345G2345T19

2．T の各辺を二重にしたグラフ Tʼ を作成する

112345T

2345Tʼ
20

3．Tʼ 上で全ての頂点を通る巡回路 C を求める
※ 同じ頂点を 2 度通ってよい

12

3

1→3→2→3→5→4→5→3→145Tʼ

C
21

4．C のうち 1 度通ったことのある頂点をショートカットした巡回路 Cʼ を求める

1→3→2→3→5→4→5→3→1

C

1→3→2→5→4→1Cʼ

22

5．Cʼ とそのコスト（距離の合計）を出力する
12

3

4

5

1→3→2→5→4→1Cʼ

23

G の頂点数を n、辺の数を m とする
1.

グラフ G の最小全域木 T を求める → O(mlog2n)（後述）

2.

T の各辺を二重にしたグラフ Tʼ を作成する → O(n)3.

Tʼ 上で全ての頂点を通る巡回路 C を求める → O(n)4.

C のうち 2 度目に通る頂点をショートカットした巡回路 Cʼ
を求める → O(n)5.

Cʼ と閉路の辺の重みの総和を出力する → O(n)よって、 O(mlog2n)24最適解の巡回路の辺の重みの総和を OPT
最小全域木の辺の重みの総和を MSTとする。

まず、OPT と MST を比較すると、
MST

OPTが成り立つ。

25

最小全域木の枝を 2 重化したグラフ Tʼ 上で得られた閉路C を考える。
前述の例なら、1 → 3 → 2 → 3 → 5 → 4 → 5 → 3 → 1
この経路のコストは 2 MST となる。
123

45Tʼ

26

次に最終的に得られた巡回路 Cʼ を考える。
Cʼ の辺の重みの総和を ALG とすると、ALG2 MSTを満たす。

なぜ？？

27

C：1 → 3 → 2 → 3 → 5 → 4 → 5 → 3 → 1
Cʼ: 1 → 3 → 2 → 5 → 4 → 1の経路を考えると、まず、 2 → 3 → 5 を 2 → 5 とショートカットする。
Metric TSP では、任意の 3 頂点間の重みの間に三角不等式が成り立っているので、

𝑤 2, 5 ≤ 𝑤 2, 3 + 𝑤(3, 5)が成り立つ。その他のショートカットも同じ議論が成り立つので、
ALG

2 MSTが得られる。
28

これまでの議論により、
Ø MST

OPT

Ø ALG

2 MSTが得られたので、
ALG

2 MST

2 OPTとなることから、前述したアルゴリズムの近似度が 2であることが示される。

29

30

左のグラフの最小全域木は右となる。
これを Kruskal アルゴリズムで求める。

131522232544114553114531

Kruskal のアルゴリズム：n はグラフ G の頂点数1.

辺が n-1 本採用されるまで下記を繰り返す
A) 辺の重みが小さい順に辺を選択していく

Øもし、選択した辺がこれまでに採用した辺集合と閉路を作ってしまうなら却下し、次の辺の選択に移るØそうでなければ、その辺を採用する2.

採用した n-1本の辺集合から構成される木 T を出力する

32

辺の重みが小さい順に辺を選択するので，まずは (2, 4) か (3, 5) を選択する（どちらを選択してもよい）今、(2, 4) を選択することにする。
最初の辺なので、閉路を作らないので採用する。
1351322423524114555351145533次に辺の重みが小さいのは (3, 5) なのでこれを選択する。
2 本目の辺なので、閉路を作らないので採用する。

1335423541145552221351145534

次に辺の重みが小さいのは (1, 4) なのでこれを選択する。
これまで採用した辺と閉路を作らないので採用する。

1335423541145552221351145535

次に辺の重みが小さいのは (1, 2) なのでこれを選択する。
しかし、この辺は、これまで採用した辺と閉路を作ってしまうので却下する。
1335423541145552221351145536

次に辺の重みが小さいのは (2, 5) なのでこれを選択する。
これまで採用した辺と閉路を作らないので採用する。

1335423541145552221351145537辺を 4 本 (= n-1 本) 採用したので、この時点でアルゴリズ
ムは終了し、これまで採用した辺で構成された木を出力する。

131522242354114351145538

Kruskalのアルゴリズム：G の頂点数 n，辺の数 m1.

辺が n-1 本採用されるまで下記を繰り返す
・閉路が構成されるかのチェック → O(m)+O(nlog2n)・素集合データ構造を利用する2.

採用した n-1 本から構成される木 T を出力する → O(n)辺のソートが必要：O(mlog2m) = O(mlog2n) ← mn2

よって、O(mlog2n)
39

NP 完全問題へのアプローチの 1 つである近似アルゴリズムの基礎について学んだ
Ø Metric TSP の 2 近似アルゴリズム
Ø 最小全域木を求める Kruskal アルゴリズム

扱うデータの規模は年々巨大になってきているØ O(n3) 時間のアルゴリズムでも使い物にならない可能性もØ どうやって高速によい解を見つけるかは非常に重要Ø 最悪計算時間が保証されているとさらに嬉しい40