アルゴリズム入門期末試験解答例問

(1)

アルゴリズム入門期末試験解答例

問1.

(1) 与えられた整数を、大きい順（または小さい順）に並べ替える問題。

(2) ^{入力のサイズを}n^{としたとき、}n^{の多項式関数（例えば}3n² など）の時間で動作を終了するアルゴリズムのこと。理論的には効率が良いとされる。

(3) アルゴリズムの動作が、ステップの繰り返しである場合、各ステップにおいて、その時点で最も得となる選択をするアルゴリズムのこと。例としては、最小全域木問題に対するクラスカルのアルゴリズムがある。

(4) 常に最適解を求めるとは限らないが、高速に（多項式時間で）動作し、常に最適解に近い解を求めるアルゴリズム。常に最適解のc倍以内の解を出力するアルゴリズムをc–^{近似アルゴ} リズムという。

(5) 入力が時間とともに逐次的に与えられ、将来の入力が分からないままに、その時その時の入力に対する答を求めるアルゴリズム。後で以前の答を変更することは許されない。例えば、

株価の変動に対して売り買いを決めるアルゴリズムが、この一例である。

問2.

(1) 与えられたグラフの頂点集合V ^を、A^とBにまたがる枝の数が最大になるように、2^つの頂点部分集合AとBに分割する問題。

(2) (i) ^{まず、頂点集合を}A^とB^{に適当に分割する。}A ^からB^へ1^{頂点移す、または}B^からA へ1頂点移すことにより答が改善されるならば、そのように移動する。これを繰り返し行い、

そのような頂点が存在しなくなった時点で、その時の解を出力する。

(ii)^頂点を1^つずつA^かB^{に入れていく。頂点}v^{を入れる番では、}v^をA^{に入れた場合と、}

Bに入れた場合とで、その時点でのCUTのサイズが大きくなる（正確には、「小さくならない」）方に入れる。これを全ての頂点がどちらかの集合に入るまで繰り返し、出力する。

(iii) 各頂点について、それぞれ独立に、確率1/2^でA^{に入れるか}B^{に入れるかを決める。}

(3) (i) アルゴリズムが終了した時点で、AとBにまたがる枝の集合をE_AB、Aの内部にある

枝集合をE_AA^、B^{の内部にある枝集合を}E_BBとする。全ての枝の集合をE^{とすると、}(1)

|E| = |E_AA|+|E_BB|+|E_AB|^{である。今、}A^{に入っている頂点}v_i^{を考える。}v_i^から延びている枝のうち、A^{に向かうものの数を}ei,A、B^{に向かうものの数を} ei,B とする。このときe_i,A ≤e_i,B となる。そうでなければ、v_i ^をBに移すことで改善されるため、アルゴリズムは終了していないはずである。上記の不等式をAに入っている全ての頂点について足しあわせると、(2) 2|E_AA| ≤ |E_AB|が得られる。（この加算により、E_AA^{の各枝はちょうど}2 回ずつ、E_AB^{の各枝はちょうど}1回ずつ数えられていることに注意。）B^{に入っている頂点} viについて同様の考察を行うと、(3) 2|EBB| ≤ |EAB|^{が得られる。}(2)^と(3)^{を足すと、}(4)

|E_AA|+|E_BB| ≤ |E_AB|^となる。(1)^と(4)^から、|E_AB| ≥ |E|/2^{となる。最適解は}|E|^以下なので、近似度2が示された。

(ii)^頂点viを入れる番を考える。viから既にAに入っている頂点へと向かう枝数をxi,A、vi

から既にBに入っている頂点へと向かう枝数をx_i,B とする。貪欲アルゴリズムは、頂点v_i をどちらかに入れることで、今考えている枝（x_i,A+x_i,B本）をカットに含めるか含めないかを完全に決定してしまうことに注意する。x_i,A ≥x_i,B^の場合、v_i^はB^{に入れられる。こ}

(2)

のとき、今見ている枝のうち半分以上となるx_i,A本をカットに加えることが出来る。逆に xi,A < xi,Bの場合、viはAに入れられる。このとき、今見ている枝のうち半分より多いxi,B

本をカットに加えることが出来る。いずれの場合も、各時点で考えている枝数の半分以上はカットに加えるので、最終的に得られるカットのサイズは全枝数の半分以上となる。最適解は全枝数以下なので、近似度は2^となる。

(iii) 与えられた確率分布において、各枝e^{に対して確率変数}x_eを以下のように定義する。e

がカット枝となるならx_e = 1、カット枝とならないならx_e = 0。また、同じ確率分布において、カットのサイズを表す確率変数をX^{とおくと、}X= Σxeである。よって、解のサイズの期待値はE[X] =E[Σx_e]である。ここで、期待値の線型性より、E[Σx_e] = ΣE[x_e]^である。任意の枝eに対して、その両端点がどちらに入るかで4通りの可能性があるが、全て等確率で起こり、そのうち2^{通りにおいて}x_e= 1^、残りの2^{通りにおいて}x_e = 0^となるので、E[x_e] = 1/2となる。よって、E[X] = Σ(1/2) =m/2である。ただし、m は全ての枝の数である。最適解はm^{以下なので、近似度}2^{が示された。}

問3.

(1) ^{グラフの各頂点を}1^{度ずつ通る閉路。}

(2) 持たない。グラフの頂点を後述の図のように色分けする。どの枝も、赤頂点と青頂点をつなぐので、もしハミルトン閉路が存在するなら、赤と青を交互に辿るはずであり、赤と青の個数は同じでなければならない。しかし、個数が違うので、ハミルトン閉路は持たない。（場合分けをして、全ての可能性を潰していても、満点を与える。）

(3) ^{後述の図の通り。}1^→3^→4^→5^→3^→2^→1というオイラー閉路が存在する。頂点1, 2, 4, 5^{の次数が全て}2であることから、ハミルトン閉路を持つためには、これらに継っている枝は全て通らなければならないが、頂点3に接続されている枝が4本選ばれているので、これは無理である。

(4) ハミルトンパス問題を、ハミルトン閉路問題にリダクションする。ハミルトンパス問題の入力となるグラフGが与えられたとき、ハミルトン閉路問題の入力グラフG^{を以下のように} 作る。G^に1^{頂点付け加える。}(^{付け加えた頂点を}v^∗^とする。) v^∗から元あった頂点全てに対して枝を張る。以下では、このリダクションがyes/noを保存していること、すなわち、G がハミルトンパスを持つことと、Gがハミルトン閉路を持つことが同値であることを示す。

まず、Gがハミルトンパスを持つとして、それをv₁−v₂−v₃− · · · −v_n^{とする。すると、}

G^には(v^∗, v1)^と(v^∗, vn)^{という枝があるので、}G^{はハミルトン閉路}v^∗−v1−v2−v3 −

· · · −v_n−v^∗^{を持つ。次に、}Gがハミルトン閉路を持つとする。それを、v^∗^{を始点として}

v^∗−v₁−v₂−v₃− · · · −v_n−v^∗^{とすると、}v₁−v₂−v₃− · · · −v_n^はG^{のハミルトンパス} になっている。

捕捉：「ハミルトンパスはハミルトン閉路の一部であるから、より条件の厳しいハミルトン閉路を見付けることは、ハミルトンパスをみつけることよりも難しい。」という趣旨の解答が多かったが、これでは論理的に難しさを示したことにはならない。なお、上記のリダクションではなく、別のリダクションを示したものがあった。元のグラフの2^{つの頂点に枝を}1^本付け加えて得られるグラフそれぞれに対して、ハミルトン閉路があるか否かをチェックするというものである。これも正解である。

アルゴリズム入門期末試験解答例問