第19回 分解と再構成・状態の接続・並列の限界
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 210分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
小さな境界で接続するグラフの最小カット¶
無向グラフ の辺容量は非負整数で、異なる端点 が指定される。頂点を0側と1側に分け、を0、を1に置くとき、両側を渡る辺容量和を最小にしたい。袋 を頂点にもつ根付き木が与えられ、全頂点がどこかの袋に入る、各辺の両端が同じ袋に入る、同じ頂点を含む袋は連結な部分木をなす、を満たす。各袋の大きさは 以下、袋数は とする。辺は両端を含む袋のうち最も根に近い袋に1回だけ割り当てる。この分解を使い、 が小さい場合の最小カットを設計せよ。
(1) 袋の連結性と境界(5点)¶
同じ頂点を含む袋の連結性から、辺を割り当てる最も根に近い袋が一意であることを示せ。また、親袋 と子袋 の共通部分が、子の部分木と外部の色付けを接続する境界となる理由を証明せよ。
(2) 局所費用と子状態(6点)¶
を、袋 の割当 を固定したとき、その袋の部分木に割り当てた辺の最小カット容量とする。局所辺費用と子の状態を用いた漸化式を導け。 が袋に現れる場合の禁止状態も定めよ。
(3) 共通部分への投影(7点)¶
各子について全状態 を親の各状態 と直接比較すると が現れる。共通部分への投影表 を作り、状態の結合を 時間に改善する方法を示せ。局所辺費用の計算も含めて評価すること。
(4) 連結条件を外す反例(6点)¶
辺の被覆条件だけを残し、頂点を含む袋の連結条件を外すと DP が誤る。辺 と の容量が各1、根袋 、子袋 の例で、誤った値と本当の最小カットを示せ。
(5) 袋ごとの具体例(6点)¶
根袋 、その子 、その子 を用いる。辺と容量は 。根状態の を固定した4通りの の値を求め、最小カットを一つ示せ。
(6) 割当の復元と計算量(5点)¶
最適な割当を復元する情報と手順を示せ。同じ頂点が複数の袋に出現しても矛盾しない理由、全体時間、表の空間を述べよ。このアルゴリズムが一般の入力の大きさに対して常に多項式とは限らない理由も説明せよ。
参考解答・採点の観点 — 問題1
(1) 袋の連結性と境界
辺の両端 を含む袋の集合は、 を含む連結部分木と を含む連結部分木の交わりである。非空な二つの部分木の交わりも連結で、根に最も近い頂点は一意。子の部分木内と外側の両方に現れる頂点は、両出現を結ぶ袋木のパス上の と に現れるため共通部分にある。別の子の内部と直接接続する辺についても両端を持つ袋と連結性から、色の共通性は親袋を通して管理できる。
(2) 局所費用と子状態
局所費用は
かつ 、または かつ なら 。それ以外では
葉なら子和は0。部分木同士で共有する頂点の色は境界を通じて一致し、各辺は1回だけ局所計上されるので、最小化を子ごとに独立に行ってよい。答えは根の全 の最小。
(3) 共通部分への投影
子 ごとに とし、 を作る。 を1回列挙して対応する へ最小値を入れれば |) 状態操作で完成する。親の各 から を1回参照する。袋木の辺は 本なので結合総時間 。局所辺は全体で 本、各袋状態でその割当辺を調べれば 。空間 。射影表は とし、各ビット と について (共通部分外なら )で作れる。全体で 袋 演算なので、親・子の各状態からは表を1回参照する。 ビットが語に入る場合の評価である。一般のビットモデルでは射影費用に を掛けてもよい。 辺割当の前処理も、根から袋を走査して各頂点の最高袋 を記録し、各辺 uv を の深い方へ割り当てれば 。両最高袋は共通袋への根パス上で比較可能で、深い方が両端を含むことは袋連結性から従う。
(4) 連結条件を外す反例
左の子では にして を切らず、右の子では にして を切らない。根に がないので、この矛盾する二つの色が結合され、誤った答え0となる。本当のグラフは のパスなので は一つの色しか持てず、どちらに置いても容量1の辺を切る。最小は1。頂点の袋連結性は単なる形式条件ではなく、同じ変数の値が離れた部分問題で食い違うことを防ぐ。
(5) 袋ごとの具体例
根の に対する値は 、、、。たとえば を0、を1とするカットは at と ct を渡り、容量。のみを0とするカットも。検算として の容量は順に 。これらの に関する最小値が根表になる。
(6) 割当の復元と計算量
投影表の各 に最小値を達成する子状態 を保存し、根の最小 から子へたどる。共通部分の色が一致する条件で選ばれており、同一頂点の袋集合が連結なので、どこに出現しても同じ色となる。各袋状態表の計算は 、復元は の袋走査で、重複出現をまとめて の頂点色を出力できる。表空間は 。 が入力とともに増えると指数項が増えるので、一般グラフで常に多項式という主張にはならない。
問題2 · 動的計画法(35点)¶
編集距離の最適経路を線形空間で復元する¶
文字列 の長さを とする。1文字の削除・挿入の費用は1、異なる文字への置換は2、同じ文字の対応は0である。最小編集費用と、それを達成する操作列を求めたい。通常の DP 表のセル は の先頭 文字と の先頭 文字を変換する最小費用であり、格子上の辺は削除・挿入・対応を表す。全表を保存する 空間の方法から、行を順方向・逆方向に計算して分割し、作業領域を大きく減らす方法を導け。空文字列の場合も含む。
(1) 通常の編集DPと逆追跡(5点)¶
通常の編集 DP の境界と漸化式を示し、得点だけなら行を2枚使えばよいことを説明せよ。その最後の2行だけから通常の逆追跡ができない理由も述べよ。
(2) 中間行での分割(6点)¶
とする。、 とおく。最適費用が であることを、格子経路が第 行を通る事実から証明せよ。
(3) 逆向きDPと添字(6点)¶
を逆向きの2行 DP で計算する具体的な添字を示せ。誤って の後半と の接頭辞の距離を加える方法に対し、、 で最小の を選ぶと失敗することを示せ。
(4) 分割復元と基底処理(8点)¶
最小の分割位置 を使って前半・後半を再帰復元する擬似コードを書け。 または 、どちらかが0の場合の作業空間の基底処理も述べよ。行配列を解放してから再帰すること。
(5) 時間と補助空間(5点)¶
全計算時間が となることを、各分割後の部分問題の面積から証明せよ。作業空間と出力空間を区別し、列の側を短く選ぶことで の補助空間となる条件を説明せよ。
(6) 編集列の具体例(5点)¶
、、 とする。 の とその和を求め、最適分割と操作列を示せ。複数の最適経路がある入力でも、この方法がそのうち一つを必ず返すことを説明せよ。
参考解答・採点の観点 — 問題2
(1) 通常の編集DPと逆追跡
。
、は同字0、異字2。必要なのは前行と現在行の左セルなので、費用のみなら 空間。最後の2行では、それより前のセルの採用候補が失われ、最終行から前へ移動した時点で逆追跡を続ける情報がない。単に値をローリング保存するだけでは復元機能も残るわけではない。
(2) 中間行での分割
任意の全経路は から へ進むので、第 行のある頂点 を通る。その前後の費用はそれぞれ 以上で、全最適費用。逆に、任意の の最適前半経路と最適後半経路を連結すれば全経路となり、その費用は和に等しい。よっても成り立つ。第 行を横に複数頂点通る場合でも、そのうち一つを選べば同じ証明が成立する。
(3) 逆向きDPと添字
に通常の DP を行い、最終行 を得ると 。両方を反転すると編集列も逆順にできるため距離は不変。誤式では AB を中央で切り、、誤った後半 と 接頭辞の距離 を足すと 。最小の を選ぶが、本当の部分問題は 空の費用1と の費用1で総費用2となり、正解0を失う。
(4) 分割復元と基底処理
restore(X,Y):
if len(X)==0: 挿入 Y を出力; return
if len(Y)==0: 削除 X を出力; return
if len(X)<=1 or len(Y)<=1:
1文字側の文字が他側に現れるか1回走査し、直接操作列を出力; return
必要なら X,Y を交換し、長い方を行側にする
a=floor(len(X)/2)
F=2行DP(Xの前半,Y)
G=2行DP(reverse(Xの後半),reverse(Y))
j*=argmin_j F[j]+G[len(Y)-j]
F,G と作業行を解放
restore(Xの前半,Yの先頭j*文字)
restore(Xの後半,Yの残り)交換した場合は出力操作の挿入と削除を交換し、文字対の左右も戻す。この費用体系は対称なので交換しても距離は変わらない。部分文字列はコピーせず元の範囲を渡す。基底で が1文字なら、 内に同字があればその一つを対応させ、他の文字を挿入する(費用 )。同字がなければ を削除し 全体を挿入する(費用 、置換を使っても同率)。 が1文字なら対称に処理する。直接走査は 作業空間で、長大列の全 DP 表は作らない。
(5) 時間と補助空間
を半分にしたとき子の面積和は 。1辺が1以下の基底を除き、各レベルの総面積は幾何級数として減るため 。空文字の出力など線形費用を含め 。各呼出しで長い側を半分にし、親の行を解放すれば同時に生存する行配列は 以下。2段進むと最大辺も半分以下になるので範囲情報のスタックは 。出力操作は高々 個で、その保存領域は別。基底をより短い1辺として処理し、巨大な表を作らないこと。
(6) 編集列の具体例
、、和。。前半 で を削除し、後半 をそのまま対応させる。最適費用1。全経路費用が分割和に一致する位置を選び、各子でも最適経路を返す帰納法で、同率分割・同率操作があっても少なくとも一つの全最適列が得られる。
問題3 · 整列アルゴリズム(30点)¶
整列ネットワークの正しさと仕事量¶
本の線に値を置く。比較器は指定した2線の小さい値を上側、大きい値を下側へ置き、比較器の位置と接続は入力値によらず固定される。同時に実行できる、線を共有しない比較器の集合を1層とする。総比較器数を仕事量、層数を深さと呼ぶ。バイトニック列とは、巡回回転すると非減少列と非増加列の連結になる列である。昇順バイトニック併合では前半 と後半 を比較し、小さい側を前半へ置いて、両半分を再帰併合する。
(1) 閾値写像と0–1原理(4点)¶
任意の値を閾値 未満なら0、それ以外なら1に写すと、比較器の出力とこの写像が交換することを示せ。それを用いて、入力をすべて整列できるネットワークは任意の全順序入力を整列できることを証明せよ。
(2) バイトニック併合の正しさ(5点)¶
のバイトニック列では、巡回的に1が一つの区間をなす。(前半,後半) の比較後、両半分がバイトニックで、前半の全値が後半の全値以下となることを示せ。そこから一般値のバイトニック併合の正しさを導け。
(3) 仕事量と深さの漸化式(7点)¶
前半を昇順、後半を降順に再帰整列し、全体をバイトニック併合する整列ネットワークを構成せよ。併合と全整列の仕事量・深さの漸化式を立て、 と の閉じた式を求めよ。
(4) 仕事量と深さの下界(6点)¶
固定ネットワークで任意の相異なる キーを整列する場合、仕事量 、深さ が必要であることを別々に証明せよ。後者では、深さ の出力線が影響を受け得る入力線数を考えよ。
(5) 具体例と番兵(4点)¶
のバイトニック整列の仕事量と深さを求め、(4)の下界に対して何倍の対数因子を余分に使うかを述べよ。 が2の冪でない場合に、番兵を使って拡張する方法も示せ。
(6) 安定性の反例と修正(4点)¶
各比較器が同キーを交換しなくても、ネットワーク全体の安定性は保証されない。3線の比較器列 と入力 で示せ。任意の正しいネットワークを安定整列にする修正を述べよ。
参考解答・採点の観点 — 問題3
(1) 閾値写像と0–1原理
閾値写像 は単調で、、maxについても同じ。これを全比較器に順に適用できる。もし一般値の最終出力で なのに なら、 を選ぶと出力に1の後の0が生じる。対応する入力は整列されないことになり矛盾。
(2) バイトニック併合の正しさ
0または1の巡回区間の長さが 以下なら、その区間の中の点は半周離れた同じ区間の点を持たない。0が 個以上なら前半はすべて0になり、1が 個以上なら後半はすべて1になる。同数なら前半0・後半1。このため全前半全後半である。片側に残る0または1の位置も元の巡回区間の半周への射影であり一つの巡回区間なので、両半分がバイトニックとなる。再帰で両半分を整列すれば全体も整列する。一般バイトニック列を閾値化するとバイトニック列になるので、整列違反を閾値で検出する(1)の議論を制限入力にも適用できる。
(3) 仕事量と深さの漸化式
併合の仕事 、 から 。深さ 。半分の昇順と降順を並行に整列すると連結はバイトニックになる。全整列は なので 、深さ 。降順版は比較器の出力向きを反転すればよい。
(4) 仕事量と深さの下界
個の比較結果列は高々種類。相異なるキーの 通りの入力順位を正しい出力へ送るためには、それぞれに対応する移動結果が区別される必要があり、。よって 。深さ0では各出力は入力1本に依存し、各比較層で依存集合の大きさは高々2倍なので深さ で高々本。最小値を出す線はすべての入力に依存する必要がある。依存しない入力を非常に小さくすれば出力が誤るため、、。
(5) 具体例と番兵
なので仕事 、深さ 。漸近的には仕事 、深さ で、それぞれの下界より対数因子1個多い。一般 は次の2の冪 に拡張し、実キーより大きい番兵を置いて整列後に捨てる。番兵を通常の入力レコードと誤って混同しないよう識別情報を付ける。
(6) 安定性の反例と修正
最初の により となり、残りの比較器は同キーを交換しないので が より先になる。この3比較器列は3要素を整列するが安定ではない。キーを (本来のキー,元の位置) の辞書順にして比較すれば、同キーは元の位置で全順序化される。任意の正しいネットワークはこの組も整列できるので、最後に元の位置を取り除けば安定な出力になる。