ｽﾗｲﾄﾞ ﾀｲﾄﾙなし

宮崎修一

京都大学 学術情報メディアセンター

アルゴリズム入門（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 ・・・

近似アルゴリズム ・指数時間かかるのは困る。多項式時間で解が欲しい。 ・代わりに、解の質をあきらめる（最適解でなくてよい）。 ・でも、できるだけ良い解が欲しい。 近似アルゴリズムの良さ 例えば最小化問題 「アルゴリズムＡの近似度_{が r である} （Ａは r-近似アルゴリズムである）」 どんな入力に対しても、アルゴリズムＡの出す解のコストは 最適解のコストのｒ 倍以内である。 ⇔

最小頂点被覆問題 7個の頂点 ４個の頂点 枝：道路 頂点：交差点 交差点にガードマンを配置して、全ての道を警備したい。 できるだけ少ないガードマンで済ませるには、どこに配置したら良いか？ ちなみに、3個では無理。 問題：最適は？

頂点被覆問題に対する 近似度２のアルゴリズム

2 - log log N

近似アルゴリズムに対するアプローチ 上限の研究 ・ 問題に対する、c-近似アルゴリズムを開発する。 ・ cの値を小さくしていく方向。 下限の研究 ・ （Ｐ≠ＮＰの仮定の下で）、問題がc-近似アルゴリズムを 持たないことを示す。 ・ cの値を大きくしていく方向。 例：MAX 3SAT ・上限： 8/7-近似アルゴリズムは存在する ・下限： Ｐ≠ＮＰならば、(8/7-ε)-近似アルゴリズムは存在しない （ε：任意の正定数） [Hastad 1997] ちなみに、最小頂点被覆問題は、

安定結婚問題（の最適化問題）

・1.137 （unless P=NP) [Yanagisawa 2007] ・ 2 [easy]

・ ( ) [Iwama, Miyazaki, Okamoto 2004]2 - c N

log N

・ ( ) [Iwama, Miyazaki, Yamauchi 2005]2 - c N

1 √

・ 1.875 [Iwama, Miyazaki, Yamauchi 2007]

・ 1.4706 [Iwama, Miyazaki, Yanagisawa 2010] ・ 1.667 [Kiraly 2008]

・ 1.5 [McDermid 2009] ・ 1.5 [Kiraly 2008] [McDermid 2009] ・ 1.667 [Irving, Manlove 2008]

・1.333 （under UGC) [Yanagisawa 2007]

General _{One-sided ties}

・1.105 （unless P=NP) [Halldorosson, Iwama, ’ ・1.25 （under UGC) [Halldorosson, Iwama,

Miyazaki, Yanagisawa 2007] ’

・ 1.4667 [Huang Kavitha 2014] ・ 1.4643 [Radnai 2014]

MAX CUT 入力：グラフG 出力：Gの頂点集合の2分割 間にある枝数が出来るだけ多くなるように 例 4本 5本

MAX CUTに対する局所探索法

近傍：＝1頂点だけを反対側の グループへ移す

アルゴリズムが終了した時の性質

Ａ Ｂ

Ａ Ｂ

v

とすると

への枝数

、

への枝数

から

頂点

B

e

e

A

v

e

e

A

v

∈

ならば

≤

Ａ Ｂ

v

とすると

への枝数

、

への枝数

から

頂点

B

e

e

A

v

e

e

A

v

∈

ならば

≤

Ａ Ｂ

v

.

2

E

E

e

e

v

A

≤

≤ を足し合わせると

について、

の全ての頂点

e

e

B

v

e

e

A

v

≥

∈

≤

∈

ならば

ならば

Ａ Ｂ

v

.

2

E

E

e

e

v

B

≤

≤ を足し合わせると

について、

の全ての頂点

e

e

B

v

e

e

A

v

≥

∈

≤

∈

ならば

ならば

.

2

2

E

≤

E

と

E

≤

E

より、

E

+

E

≤

E

.

.

2

E

E

E

E

E

E

E

E

E

E

≤

≥

−

≥

+

+

=

一方、最適解

つまり、

なので、

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都市

きっちり定式化すると 入力： 完全グラフG=(V, E)、各枝𝑒𝑒 ∈ 𝐸𝐸に対して、長さ𝑐𝑐(𝑒𝑒)。 （頂点は観光スポットに対応。枝の長さは移動距離に対応） 出力： Gの各頂点を1度ずつ通る閉路。 ただし、使われた枝の長さの合計が最小となるもの。 （同じ頂点を2度通ってはいけないことに注意）

単純なアルゴリズム： 頂点数をnとする。 それぞれの回り方（n!通りの順列）に対して、総距離を計算し、 最も短い経路を出力する。 ↓ 確かに最適解が得られるが、n!時間かかる。 (n! ＞ 2 ） 実際、ＮＰ困難であることが証明されている。 ↓ 近似アルゴリズム ・距離空間が三角不等式を満たす場合の 2-近似アルゴリズム。1.5-近似アルゴリズム。 ・ユークリッド平面の場合（例えば先程の京都市の例）は、 n

2－近似アルゴリズム

ステップ1：最小全域木を求める。（そのコストをＴとする。）

（巡回セールスマンの最適解のコストをOPTとすると、T＜OPT。）

2－近似アルゴリズム

ステップ2：最小全域木沿いにツアーを組む。 （同じ枝を2度なぞる。）

このツアーの長さをPとすると、

2－近似アルゴリズム

ステップ3：同じところを2度通らないように飛ばす。

このツアーの長さをLとすると、

2－近似アルゴリズム

ステップ4：得られたツアーを出力する。

近似度の解析

1.5－近似アルゴリズム ステップ1までは一緒。

1.5－近似アルゴリズム

ステップ2：奇数次数の頂点を選ぶ。（偶数個ある。）

1.5－近似アルゴリズム

ステップ3：緑の頂点間の最小重みマッチングを求める。 （枝の長さの総和が最小のもの）

元あった枝と合わせて、

1.5－近似アルゴリズム

ステップ4：オイラー回路を求める。

1.5－近似アルゴリズム ステップ5：先程のオイラー回路で、2度目の頂点を飛ばす。 得られた緑のツアーを出力する。 緑のツアー長 青のツアー長 ≦ 青のツアー長_＝T＋

奇数次数（緑）の頂点だけのツアーで最短のものを考えよう。

水色のツアー長_≦OPT

（例えば、OPTのツアーで、 赤色頂点を飛ばせば良い）

そのツアー上の、1つとびの枝集合、2組。

の全長＋ の全長

の全長と の全長

のうち短い方を とする。

の全長

≦1/2 の全長 そのツアー上の、1つとびの枝集合、2組。

の全長 ≦ の全長 ≦ 1/2 の全長 ≦ 1/2 OPT の枝集合はマッチング の枝集合は最小マッチング そのツアー上の、1つとびの枝集合、2組。 示したかったこと

では、 「○○よりも良い近似度の多項式時間近似アルゴリズム は存在しない」 というのは、どういう風に示すのか？ 判定問題の時と同様に、「リダクション（還元）」を使う。 前の例は、判定問題_{（Yes/Noを答える）から}判定問題への リダクションだった。 近似アルゴリズムの限界

グラフのハミルトン閉路 各頂点を、ちょうど1度ずつ通る閉路 1 2 6 7 9 8 3 4 5 10 11 13 14 12

ハミルトン閉路問題（判定問題）から巡回セールスマン問題 （最適化問題）へリダクションをする。 ハミルトン閉路問題の 入力グラフG 巡回セールスマン問題の 入力グラフH Hの作り方 Hの頂点集合はGと同じ Hは完全グラフ Gで枝のある所 → Hでは枝の重み（長さ）1 → Hでは枝の重みn+1

例

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 ≧ 2n Aの答を見ればGがYESかNOか分かる →ハミルトン閉路問題が解けてしまう

最適値はn 最適値は≧2n このnと2nのギャップが、近似度の下限を与えた。 YES NO ポイントは この2つが重ならないこと。 ≦ 1.8n ≧ 2n YES NO Aの答 Aの答 → → 1.8n 2n n

問題：最初の方で巡回セールスマン問題に対する

1.5-近似アルゴリズムを見たが、1.8-近似アルゴリズム が存在しないことが示せてしまった。