宮崎修一
京都大学 学術情報メディアセンター
アルゴリズム入門（ 8 ）
（近似アルゴリズム）
近似アルゴリズムとは？
効率よく解ける問題（多項式時間アルゴリズムが存在する問題）
ソーティング、最短経路問題、最小全域木問題、
…
効率よく解けそうにない問題（NP
困難問題）最小頂点被覆問題、
MAX SAT
、MAX CUT
、…
本質的に問題が難しいのだが、何とか対応したい
→
幾つかのアプローチ（平均時間計算量、指数時間アルゴリズム、
確率アルゴリズム、近似アルゴリズム）
指数時間アルゴリズム
・最適解（正しい解）を得たい。
・指数時間かかることは仕方ない。
・しかし、指数時間の中でも、できるだけ高速であって欲しい。
（例）
3SAT
（3CNF
式の充足可能性問題）Tamaki,04]
[Iwama, )
3227 .
1 ( 3238 .
1
[Rolf,03]
3280 .
1
] Schuler,03 [Baumer,
3290 .
1
al.,02]
et r [Hofmeiste 3302
. 1
,99]
[Schoening 334
. 1
al.,98]
et [Paturi 362
. 1
er,79]
Speckenmey [Monien,
618 . 1
n
n n
n n n n n n
・・・
近似アルゴリズム
・指数時間かかるのは困る。多項式時間で解が欲しい。
・代わりに、解の質をあきらめる（最適解でなくてよい）。
・でも、できるだけ良い解が欲しい。
近似アルゴリズムの良さ 例えば最小化問題
「アルゴリズムＡの近似度が
r
である（Ａは
r-
近似アルゴリズムである）」どんな入力に対しても、アルゴリズムＡの出す解のコストは 最適解のコストの
ｒ
倍以内である。⇔
最小頂点被覆問題
7個の頂点 ４個の頂点 枝：道路
頂点：交差点
交差点にガードマンを配置して、全ての道を警備したい。
できるだけ少ないガードマンで済ませるには、どこに配置したら良いか？
ちなみに、
3
個では無理。問題：なぜ？
問題：最適は？
頂点被覆問題に対する 近似度２のアルゴリズム
log log N
問題：どうしてこれは近似度
2
？近似アルゴリズムに対するアプローチ 上限の研究
・ 問題に対する、
c-
近似アルゴリズムを開発する。・
c
の値を小さくしていく方向。下限の研究
・ （Ｐ
≠
ＮＰの仮定の下で）、問題がc-
近似アルゴリズムを 持たないことを示す。・
c
の値を大きくしていく方向。例：
MAX 3SAT
・上限：
8/7-
近似アルゴリズムは存在する・下限： Ｐ
≠
ＮＰならば、(8/7-ε)-
近似アルゴリズムは存在しない（
ε
：任意の正定数）[Hastad 1997]
ちなみに、最小頂点被覆問題は、
1
MAX CUT
入力：グラフ
G
出力：
G
の頂点集合の2
分割間にある枝数が出来るだけ多くなるように
例
4
本5
本MAX CUT
に対する局所探索法近傍：＝
1
頂点だけを反対側の グループへ移すアルゴリズムが終了した時の性質
どの頂点も、
Ａ Ｂ
両端がＡ内にある枝数：
E
全ての枝数：E
Ａ Ｂ
v
とすると への枝数
、 への枝数
から
頂点 v A e
AvB e
Bvv B v
A
e
e A
v ならば
Ａ Ｂ
v
とすると への枝数
、 への枝数
から
頂点 v A e
AvB e
Bvv B v
A
e
e A
v ならば
Ａ Ｂ
v
. 2
A,A A,Bv B v
A
E E
e e
v A
を足し合わせると について、
の全ての頂点
v B v
A
v B v
A
e e
B v
e e
A v
ならば
ならば
Ａ Ｂ
v
. 2
B,B A,Bv A v
B
E E
e e
v B
を足し合わせると について、
の全ての頂点
v B v
A
v B v
A
e e
B v
e e
A v
ならば
ならば
. 2
2 E
A,A E
A,Bと E
B,B E
A,Bより、 E
A,A+ E
B,B E
A,B. 2 .
,
, ,
, ,
,
E E E
E E
E E
E E
E
B A
B A B
A B
A B
B A
A
−
+
+
=
一方、最適解 つまり、
なので、
よって、このアルゴリズムは
2-
近似アルゴリズム。MAX CUT
に対する貪欲アルゴリズムＡ Ｂ
Step 1:
頂点を適当に選び Ａ、Ｂどちらかに 適当に入れる
MAX CUT
に対する貪欲アルゴリズムＡ Ｂ
Step 1:
頂点を適当に選び Ａ、Ｂどちらかに 適当に入れる
MAX CUT
に対する貪欲アルゴリズムＡ Ｂ
Step 2
以降:
頂点を適当に選び、
これまで既に入っている 頂点とのカットがより
大きくなる方に入れる。
MAX CUT
に対する貪欲アルゴリズムＡ Ｂ
Step 2
以降:
頂点を適当に選び、
これまで既に入っている 頂点とのカットがより
MAX CUT
に対する貪欲アルゴリズムＡ Ｂ
Step 2
以降:
頂点を適当に選び、
これまで既に入っている 頂点とのカットがより
大きくなる方に入れる。
MAX CUT
に対する貪欲アルゴリズムＡ Ｂ
Step 2
以降:
頂点を適当に選び、
これまで既に入っている 頂点とのカットがより
MAX CUT
に対する貪欲アルゴリズムＡ Ｂ
Step 2
以降:
頂点を適当に選び、
これまで既に入っている 頂点とのカットがより
大きくなる方に入れる。
MAX CUT
に対する貪欲アルゴリズムＡ Ｂ
Step 2
以降:
頂点を適当に選び、
これまで既に入っている 頂点とのカットがより
MAX CUT
に対する貪欲アルゴリズムＡ Ｂ
Step 2
以降:
頂点を適当に選び、
これまで既に入っている 頂点とのカットがより
大きくなる方に入れる。
近似度の解析
Ａ Ｂ
近似度の解析
Ａ Ｂ
左へ入れた場合
利得
近似度の解析
Ａ Ｂ
近似度の解析
Ａ Ｂ
右へ入れた場合
利得
近似度の解析
Ａ Ｂ
アルゴリズムは、この
2
つのうち、大きい方（小さくない方）の利得を 得るように動く。
（このうち、半分は得る。）
近似度の解析
Ａ Ｂ
この部分を、全部の頂点について 足し合わせたら、ちょうど全ての枝
アルゴリズムは、全枝の 半分はカットする。
MAX CUT
の現在最良 の近似度は1.138…
巡回セールスマン問題
京都駅から出発して、観光して、京都駅に戻って来たい。
同じところは
2
度通らない。できるだけ短い経路で回る。応用：
コンビニの配送計画
自動販売機のジュース補給配送計画
集積回路
(VLSI)
の配線ロボットのアームの動き最適化TSPLIB
様々なベンチマーク集合に対する、解法競争が行われている
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
TSPLIB
のベンチマークの1
つ 日本の9847
都市その最適解
アメリカ
13509
都市きっちり定式化すると
入力： 完全グラフ
G=(V, E)
、各枝𝑒 ∈ 𝐸
に対して、長さ𝑐(𝑒)
。（頂点は観光スポットに対応。枝の長さは移動距離に対応）
出力：
G
の各頂点を1
度ずつ通る閉路。ただし、使われた枝の長さの合計が最小となるもの。
（同じ頂点を
2
度通ってはいけないことに注意）単純なアルゴリズム：
頂点数を
n
とする。それぞれの回り方（
n!
通りの順列）に対して、総距離を計算し、最も短い経路を出力する。
↓
確かに最適解が得られるが、
n!
時間かかる。(n!
＞2
）実際、ＮＰ困難であることが証明されている。
↓
近似アルゴリズム
・枝の重みが三角不等式を満たす場合の
2-
近似アルゴリズム。1.5-
近似アルゴリズム。・ユークリッド平面の場合（例えば先程の京都市の例）は、
n
2
－近似アルゴリズムステップ
1
：最小全域木を求める。（そのコストをＴとする。）（巡回セールスマンの最適解のコストを
OPT
とすると、T
＜OPT
。）問題：なぜ？
2
－近似アルゴリズムステップ
2
：最小全域木沿いにツアーを組む。（同じ枝を
2
度なぞる。）このツアーの長さを
P
とすると、P
＝2T
。2
－近似アルゴリズムステップ
3
：同じところを2
度通らないように飛ばす。このツアーの長さを
L
とすると、L ≦ P
。（三角不等式より）2
－近似アルゴリズムステップ
4
：得られたツアーを出力する。近似度の解析
L ≦ P=2T
＜2OPT
1.5
－近似アルゴリズム ステップ1
までは一緒。T
＜OPT
1.5
－近似アルゴリズムステップ
2
：奇数次数の頂点を選ぶ。（偶数個ある。）問題：なぜ？
1.5
－近似アルゴリズムステップ
3
：緑の頂点間の最小重みマッチングを求める。（枝の長さの総和が最小のもの）
元あった枝と合わせて、
全ての頂点の次数が偶数。
1.5
－近似アルゴリズムステップ
4
：オイラー回路を求める。青のツアー長＝
T
＋1.5
－近似アルゴリズムステップ
5
：先程のオイラー回路で、2
度目の頂点を飛ばす。得られた緑のツアーを出力する。
緑のツアー長 青のツアー長
≦
青のツアー長＝
T
＋奇数次数（緑）の頂点だけのツアーで最短のものを考えよう。
水色のツアー長≦
OPT
（例えば、
OPT
のツアーで、赤色頂点を飛ばせば良い）
そのツアー上の、
1
つとびの枝集合、2
組。の全長＋ の全長
＝ のツアー長
の全長と の全長 のうち短い方を とする。
の全長
≦ 1/2
の全長 そのツアー上の、1
つとびの枝集合、2
組。の全長
≦
の全長≦ 1/2
の全長≦ 1/2 OPT
の枝集合はマッチングの枝集合は最小マッチング
そのツアー上の、
1
つとびの枝集合、2
組。示したかったこと
1.5 − 10
−36（2021
年）では、
「○○よりも良い近似度の多項式時間近似アルゴリズム は存在しない」
というのは、どういう風に示すのか？
判定問題の時と同様に、「リダクション（還元）」を使う。
前の例は、判定問題（
Yes/No
を答える）から判定問題への リダクションだった。近似アルゴリズムの限界
グラフのハミルトン閉路
各頂点を、ちょうど
1
度ずつ通る閉路1
2 6
7
9
3 8
4
5
10
11
13
14
12
ハミルトン閉路問題（判定問題）から巡回セールスマン問題
（最適化問題）へリダクションをする。
ハミルトン閉路問題の 入力グラフ
G
巡回セールスマン問題の 入力グラフ
H
H
の作り方H
の頂点集合はG
と同じH
は完全グラフG
で枝のある所→ H
では枝の重み（長さ）1
例
G H
G
がYES
の例題（G
にハミルトン閉路がある）→ H
は重み1
の枝だけを使って一周することができる。→
総距離n
で一周できる。→
最適の1.8
倍悪い解でも1.8n
以下で収まる。G
がNO
の例題（G
にハミルトン閉路がない）→ H
を一周するどんな経路も、重みn+1
の枝を使う。→
総距離は少なくとも(n-1)+(n+1)=2n
。→
最適解は2n
以上。ハミルトン閉路問題 巡回セールスマン問題
入力
G
入力H
A
の答巡回セールスマン問題に
1.8-
近似アルゴリズムA
が存在したとする。A
を使ってG
を解くことを考える。A YES
≦ 1.8n
最適値はn
NO
最適値は≧2n
≧ A
の答を見ればG
がYES
かNO
か分かる→
ハミルトン閉路問題が解けてしまう→P=NP
最適値は
n
最適値は≧
2n
この
n
と2n
のギャップが、近似度の下限を与えた。YES NO
ポイントはこの
2
つが重ならないこと。≦ 1.8n
≧ 2n
YES NO
A
の答A
の答→ →
1.8n 2n
n
問題：最初の方で巡回セールスマン問題に対する
