第6回 解の証明書と適応的アルゴリズム
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 180分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
二部判定に証明書を付ける¶
単純無向グラフ の各頂点に 0 または 1 を割り当て、すべての辺の両端を異なる値にしたい。実現可能な割当て、または不可能であることを示す単純奇閉路を出力する問題を考える。 は非連結でもよい。、 とし、隣接リストが与えられる。BFSでは未訪問の隣接頂点を番号順に処理する。
(1) BFSの具体例と奇閉路(5点)¶
、 とする。頂点1からBFSを行い、距離と二部の分割を求めよ。その後、辺 を追加したグラフが二部グラフでないことを、具体的な奇閉路で示せ。
(2) 親経路からの奇閉路復元(6点)¶
BFS木の距離を とする。辺 で の偶奇が等しいとき、親ポインタと最低共通祖先を利用して単純奇閉路を構成せよ。構成した列に頂点の重複がなく、長さが奇数になることを証明せよ。
(3) 線形時間の判定と検証(6点)¶
二部の割当てまたは奇閉路を必ず出力する 時間のアルゴリズムを示せ。第三者が、その出力だけから結論の正しさを確認する方法も説明せよ。非連結グラフと孤立頂点を取りこぼしてはならない。
(4) 最短奇閉路(7点)¶
不可能の場合には最短の奇閉路を出力したい。すべての根からBFSを行い、同じ偶奇を持つ辺について が最小の組を選ぶ方法を考える。この方法の正しさと 時間の実装を示せ。各候補の親経路を毎回展開してはならない。
(5) 色差を保持するUnion-Find(6点)¶
辺が1本ずつ到着し、最初に矛盾が発生するまで割当ての実現可能性を調べたい。各頂点から集合代表への色の差を1ビットで保持する Union-Find を設計せよ。サイズによる併合のみを使い、各操作を 時間にせよ。
(6) 矛盾時の証明書(5点)¶
(5)で矛盾を初めて検出した際にも奇閉路を出力したい。Union-Find の親ポインタをグラフの辺と見なしてよいかを論じ、正しい証明書を得るための追加データと処理を示せ。矛盾検出後の追加時間は 以内とせよ。
参考解答・採点の観点 — 問題1
(1) BFSの具体例と奇閉路
距離は順に 。二部は と 。追加後には という長さ5の単純奇閉路がある。したがって、どのように色を変更してもすべての辺を異色にはできない。
(2) 親経路からの奇閉路復元
BFSでは辺の両端の距離差は高々1なので、同じ偶奇なら 。最低共通祖先を とし、木経路 、辺 、木経路 を連結する。 は異なる同深さの頂点なので一方が他方の祖先にはならない。二つの木経路は 以外で交わらず、得られる閉路は単純である。長さは で、奇数となる。
(3) 線形時間の判定と検証
各未訪問頂点を新たなBFS根とし、根を色0、発見した子を親と反対色にする。同色の辺が見つかったら(2)の閉路を出力し、なければ全頂点の色を出力する。各辺は定数回調べ、親経路の展開は矛盾時に一度だけなので 時間、補助空間 。割当ての検証は全辺の両端色を比較する。奇閉路の検証は、相異なる頂点、閉路の各辺の存在、長さの奇数性を調べる。辺を辞書に登録するか隣接リストを走査すれば で検証できる。
(4) 最短奇閉路
各BFSについて、同色辺の値 だけを比較し、最良の根と辺を記録する。全走査後にその根からBFSをもう一度行い、選んだ辺から閉路を一度だけ復元する。
最短奇閉路の長さを とする。その閉路上の根からBFSを行うと、閉路上の全頂点の距離は高々 。奇閉路上の全辺が異色なら一周後に色が反転するため矛盾する。したがって同色辺が存在し、その候補値は高々 。一方、どの候補も(2)により長さが候補値以下の奇閉路を作るので、候補値は 以上。全BFSでの最小値は であり、復元した閉路の長さも 。各BFSは 、候補走査も 、最後の復元は 。
(5) 色差を保持するUnion-Find
は代表 と を返す。辺 の制約は 。代表が同じなら を確認する。異なる代表 を結ぶ際には、小さい集合の根を大きい根の子にし、根間の差を とする。どちらを子にしてもこの差は同じ。
根間の差と各頂点の既存の差を合わせると、新しい辺の制約が満たされ、過去の制約も保たれる。サイズによる併合では親を1本増やされるたびに所属集合の大きさが少なくとも2倍になる。深さは であり、差のXORを累積する find と併合も同時間。
(6) 矛盾時の証明書
Union-Find の親は集合代表を結ぶ管理上のポインタであり、元の辺とは限らない。そのままでは閉路の証明書にならない。
異なる集合を併合した実際の到着辺だけを、別の森 に保存する。 は最大 本の辺を持ち、各集合内の頂点をつなぐ。矛盾辺 が到着したら、 内の唯一の 経路をDFSで求め、その辺を加える。既存制約から は同色なので経路長は偶数、追加後の閉路は奇数である。森の探索と出力は 、森の補助空間も 。
問題2 · 動的計画法(35点)¶
指定回数の特別辺を通る最短経路¶
単純有向非巡回グラフ の始点 と終点 が指定される。各辺 には整数コスト とラベル がある。ラベル1の辺をちょうど 本通る 経路の最小コストと、そのコストを達成する異なる頂点列の数を求めたい。負のコストも認める。経路数は剰余を取らず正確に数える。トポロジカル順序は入力として与えられ、 は先頭、 は末尾である。
(1) 状態と初期値(5点)¶
各頂点と使用済みのラベル1の本数を状態とする動的計画法を定義し、最適コストと個数の初期値を示せ。到達不能な状態、および長さ0の経路をどのように扱うかを明記せよ。
(2) コストと個数の更新(6点)¶
辺をトポロジカル順に緩和する際の更新式を導け。新しい候補が現在値より小さい場合、等しい場合、大きい場合を区別せよ。状態数と辺の処理回数も示せ。
(3) 具体例と全最適経路(6点)¶
、頂点順 とする。辺の組 (始点,終点,) は 。全頂点のコスト表を完成させ、最適値、最適経路数、すべての最適経路を求めよ。
(4) 正しさと重複計数(7点)¶
漸化式が最小コストと個数を同時に正しく求めることを証明せよ。負の辺があっても証明が成立する理由、および複数の遷移から同じ経路を重複して数えない理由を説明せよ。
(5) 辞書順最小の復元(6点)¶
最適経路のうち、頂点の全順序 による辞書順最小の経路を復元したい。逆向きの動的計画法と前向きの選択を組み合わせる方法を示し、(3)での結果を求めよ。
(6) 算術演算とビット計算量(5点)¶
単位時間の算術演算モデルでの時間・空間計算量を示せ。さらに、単純DAGにおける経路数のビット数が であることを示し、コスト演算を単位時間としたまま、個数の加算をビット単位で数えるときの時間上界を求めよ。
参考解答・採点の観点 — 問題2
(1) 状態と初期値
を から までラベル1の辺をちょうど 本使う経路の最小コスト、 をその最適経路数とする。、。その他は 、。 はトポロジカル順の先頭なので に入る辺はない。 の状態だけを保持し、最終結果は 。
(2) コストと個数の更新
辺 に対し で が有限なら を計算する。 なら 、 に置き換える。 なら に を加え、 なら変更しない。各 をトポロジカル順に処理すれば、その時点で の値は確定している。状態数は 、遷移数は高々 。
(3) 具体例と全最適経路
コスト表は次のとおり。
| 頂点 | |||
|---|---|---|---|
| 0 | |||
| 2 | |||
| 1 | |||
| 3 | |||
| 5 | 4 | 5 | |
| 7 | 6 |
最適値は6、個数は2。経路は と 。 の と の にはそれぞれ2本の最適経路が到達し、これらが の へ継承される。
(4) 正しさと重複計数
トポロジカル順に帰納法を用いる。 に終わる非空経路は最後の辺 と、その辺の前までの経路に一意に分かれる。後者のラベル本数は であり、最適な全経路の接頭経路もその状態で最適でなければならない。より安い接頭経路に置換できてしまうからである。各最後の辺ごとの候補の最小を取り、最小値を達成する候補の個数だけを加えればよい。
DAGには循環がなく、負の辺があっても依存先は必ず先に処理される。異なる最後の辺から作る経路は最後の頂点対が異なるので重複しない。同じ最後の辺から作る経路は帰納的に区別済みである。
(5) 辞書順最小の復元
を から までラベル1の辺をちょうど 本使う最小コストとし、逆トポロジカル順で計算する。、他の の状態は。復元中の頂点を 、残り本数を とし、 を満たす出辺のうち終点 が最小のものを選ぶ。 に到着するまで繰り返す。
選択可能な辺は必ず最適経路の接頭辺であり、最初の相違位置で最小の頂点を選ぶため辞書順最小となる。(3)では 。逆DPは 、復元の出辺走査の総量は 、表の空間は 。
(6) 算術演算とビット計算量
時間は 、空間は 。特定の 経路は、内部頂点の集合を決めるとトポロジカル順で並ぶので頂点列が一意に定まる。したがってその数は高々 で、各個数は ビット。個数の加算1回は ビット演算で実施でき、全時間の上界は 。これはコストのビット演算を除いた上界である。厳密な大整数演算まで単位時間とみなした計算量とは区別する。
問題3 · 整列アルゴリズム(30点)¶
連続整列区間を発見して併合する¶
個のレコードをキーの非減少順に安定整列したい。入力を左から走査し、キーが非減少となる極大の連続区間をランと呼ぶ。ラン数を 、長さを とする。併合は隣接する二つの区間にだけ行い、長さ の併合に の費用がかかるものとする。元の相対順序を保つ安定な併合を使う。ラン境界の検出時間も全体の計算量に含める。
(1) ランと安定性(5点)¶
入力 のランを求め、安定整列の結果を示せ。非増加の区間を逆転してランにする工夫が安定性を壊す例も示し、どの種類の下降区間なら安全に逆転できるかを説明せよ。
(2) 安定な隣接併合(5点)¶
二つの隣接ランを安定に併合する擬似コードを示せ。比較回数が高々 となること、同じキーの際の選択が入力全体の安定性を保つことを証明せよ。
(3) ラン数による均等分割(5点)¶
ランの個数をほぼ半分に分け、各側を再帰的に併合する方法を設計せよ。時間が 、補助空間が となる理由を、各要素が参加する併合回数を用いて説明せよ。
(4) 不均等なラン長(5点)¶
とし、先頭 本のランの長さが1、最後のランの長さが であるとする。ラン数で均等に分割する方法と、短いランを先にまとめてから最後のランを併合する方法の費用を比較せよ。 のとき、両者の費用比を評価せよ。
(5) 最小併合費用の区間DP(6点)¶
入力のラン順を保ったまま併合費用を最小化したい。区間 に対する状態を定義し、漸化式、境界条件、最適な併合順の復元法を示せ。前計算を含む時間・空間計算量も求めよ。
(6) 具体例と隣接制約(4点)¶
長さ の4ランについて(5)の最小費用を求めよ。ただし とする。また、ランの位置を無視して常に最短の2本を併合する方法が、そのまま隣接併合のアルゴリズムにはならない理由を具体例で説明せよ。
参考解答・採点の観点 — 問題3
(1) ランと安定性
ランは 、、、 で、長さは 。安定整列結果は 。
例えば非増加区間 を逆転すると となり、同じキーの3の順が逆転する。厳密に減少する区間なら内部に同じキーがないため、その逆転は安定性を壊さない。
(2) 安定な隣接併合
MERGE(L,R):
i ← 0; j ← 0; B ← empty
while i < |L| and j < |R|:
if key(L[i]) ≤ key(R[j]): append L[i] to B; i ← i+1
else: append R[j] to B; j ← j+1
append all remaining elements of L, then R, to B
return B各比較で1個出力し、どちらかが空になると比較をやめる。最後の少なくとも1個は比較せず出力するので高々 回。左右は元の入力で左が先にある隣接区間であり、同じキーでは左を選ぶ。各区間内の順序も保つため、安定性は併合のたびに継承される。
(3) ラン数による均等分割
ラン境界を で検出する。ラン添字の区間 を中央で二分し、両側を再帰処理して安定併合する。ラン葉の深さは高々 。各要素は自分のランから根までの各併合で一度処理されるため、総併合費用は高々 。検出を加えて 。 でも が必要。作業配列1本を全併合で再利用すれば 、再帰スタックは 。
(4) 不均等なラン長
均等な木ではすべての葉の深さが なので費用は 。短い 本を均等併合する費用は 、最後の長いランとの併合は 。したがって別法は 。 なら後者は 、前者は で、比は 。ラン数だけで均等にする戦略は、長いランを何度も読み直す点で不利になる。
(5) 最小併合費用の区間DP
、 をラン の最小併合費用とする。
、
。
最後の併合は必ず隣接区間 と を結ぶので、すべての有効な木を漏れなく比較している。区間長の昇順で計算し、最小化した を保存して左右へ再帰すれば順序を復元できる。長さの累積和に 、DPに 時間・ 空間。実際の整列にはさらに の要素処理と の作業領域が必要。
(6) 具体例と隣接制約
4ランの括弧付け5通りの費用は、順に 、、、、。 では最小は 。
例えば長さ では最短の2本は両端にあり、隣接していない。これらを先に結ぶ操作は入力の連続区間という不変条件を破る。自由な二本併合の最適性と、ラン順を保つ隣接併合の最適性は別の問題である。