第9回 有向構造と最悪時の保証
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 180分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
強連結成分を縮約して到達可能性を整理する¶
有向グラフ の二頂点 が互いに到達可能なとき と書く。長さ0の経路も認める。この関係の同値類を強連結成分と呼ぶ。各成分を一頂点に縮約し、異なる成分間の辺だけを残した単純有向グラフを縮約グラフとする。 の頂点数 、辺数 とし、元のグラフと全辺を反転したグラフの隣接リストを使用できる。
(1) 強連結成分の具体例(5点)¶
頂点 、辺 を持つグラフの強連結成分と縮約グラフを求めよ。縮約グラフの入次数0、出次数0の頂点も示せ。
(2) 同値関係と縮約DAG(6点)¶
~ が同値関係であり、縮約グラフがDAGになることを証明せよ。また、元グラフでの到達可能性が、成分間の縮約グラフでの到達可能性と対応することを示せ。
(3) 成分の終了時刻(6点)¶
元グラフのDFSの終了時刻を 、成分 の最大終了時刻を とする。異なる成分間に辺 があれば となることを証明せよ。先に発見される成分によって場合分けすること。
(4) 二回のDFSと非再帰実装(7点)¶
まず元グラフで終了順を計算し、次に逆グラフで終了時刻の降順に未訪問根からDFSする方法を説明・証明せよ。第1走査は再帰を使わず、頂点と次に調べる出辺位置を持つスタックで実装する擬似コードを書け。
(5) 開始点と終了点の最小数(5点)¶
選んだ開始頂点のいずれかから全頂点へ到達できるようにするため、開始頂点の最小個数を求めよ。同様に、各頂点から選んだ終了頂点のいずれかへ到達できるための最小個数も求め、(1)に適用せよ。
(6) 到達集合と不要辺の除去(6点)¶
縮約DAGで到達可能性を変えずに不要な辺をすべて除きたい。各頂点の到達集合をビット列で求め、後続頂点をトポロジカル順に処理するアルゴリズムを設計せよ。(1)の結果と時間計算量を示せ。1語で ビットのORを行えるものとする。
参考解答・採点の観点 — 問題1
(1) 強連結成分の具体例
、、、 の4成分。縮約辺は 。入次数0は のみ、出次数0は のみ。各群内は相互に到達可能で、群を逆方向へ戻る経路はない。
(2) 同値関係と縮約DAG
0経路から反射性、定義から対称性、経路連結から推移性が成立する。縮約に有向閉路があるとその閉路上の全成分が相互に到達可能となり、別成分という定義に反する。元経路は縮約経路へ移り、縮約経路は各成分内の経路と成分間の実辺をつないで元経路へ戻せる。
(3) 成分の終了時刻
のいずれかの頂点が最初に発見された時点を考える。 が先なら、その探索はまだ未訪問の の全頂点へ到達でき、 はその頂点の終了より前に終了する。 が先なら から へ到達できないので、 の全頂点が の最初の発見より前に終了する。どちらでも 。他成分を経由する到達があっても同じ議論が使える。
(4) 二回のDFSと非再帰実装
order = empty; mark all vertices unvisited
for each root r:
if r is visited: continue
mark r; push (r,0)
while stack is nonempty:
(v,j) = top frame
if j == outdegree(v):
pop; append v to order
else:
u = adjacency[v][j]; increment top frame index
if u is unvisited: mark u; push (u,0)
mark all vertices unvisited
for r in reverse(order):
if r is unvisited:
DFS from r in reversed graph, assigning one new component ID未処理成分の最大 の成分 は、元の縮約DAGで未処理成分からの入辺を持たない。(3)による。逆グラフでは他の未処理成分へ出られず、 内にはすべて到達できるため、1回のDFSがちょうど を回収する。これを帰納的に繰り返す。時間 、補助空間 。終了順は発見順と異なり、各頂点の全出辺を処理した後に追加する必要がある。
(5) 開始点と終了点の最小数
開始側の最小個数は縮約DAGの源点数。源点へは他成分から入れないので各源点に少なくとも1頂点必要。DAGの任意の頂点は入辺を逆にたどれば源点へ至るため、各源点から1頂点選べば十分。終了側は同じ議論を逆向きにして終点数。(1)は開始1個、終了1個で、例えば と をそれぞれ選べる。
(6) 到達集合と不要辺の除去
縮約頂点数を 、辺数を とする。逆トポロジカル順で ⋃ を計算する。各 で後続 をトポロジカル順位の昇順に並べ、covered を空にする。 なら を除き、そうでなければ残して covered に をORする。以前の後続から へ到達できれば辺は不要。後の後続はトポロジカル順位が大きく へ戻れないため、covered にない への辺は必須。この操作は到達関係を保つ。
(1)では を除き を残す。隣接リストを順位順に整える時間 を含め、時間 、空間 。元グラフの成分分解には別途 。
問題2 · 動的計画法(35点)¶
負のコストと資源予算を両立する経路¶
有向非巡回グラフ の各辺 に整数コスト と非負整数の資源消費 が与えられる。コストは負でもよく、資源消費0の辺もある。始点 から終点 へ、総消費が 以下となる経路の最小コストを求めたい。 は非負整数で、トポロジカル順序を利用できる。辺と頂点の格納領域を除いた補助空間を評価し、算術演算と比較は単位時間とする。
(1) 状態と負コスト(5点)¶
消費量をちょうど とする状態を定義し、初期値と求める最終値を示せ。非負コスト用のダイクストラ法を直接使えない理由と、DAGの性質を使えば負のコストを扱える理由を説明せよ。
(2) DAG上の緩和(6点)¶
トポロジカル順の緩和を用いた擬似コードを書け。資源消費0の辺があっても依存関係に循環が生じないことを示し、時間・補助空間計算量を求めよ。
(3) 予算制約の具体例(6点)¶
、頂点順 とする。辺 (始点,終点,コスト,消費) は 。全状態の最小コスト表、最適値、最適経路と総消費を求めよ。
(4) 候補ラベルの支配(6点)¶
同じ頂点の二つの候補ラベル (消費量,コスト) について、 が 、 を満たすなら を捨ててよいことを証明せよ。負のコストの辺がある場合と、ちょうど 消費する問題に変更した場合を区別せよ。
(5) 擬多項式時間と背包への対応(6点)¶
が2進数で入力される場合、(2)の計算量が入力長の多項式とは限らないことを説明せよ。各品物の採用・不採用を層状DAGの二経路で表し、重さ上限付き価値最大化をこの経路問題へ変換せよ。
(6) 一枚の券を使う拡張(6点)¶
通過する辺のうちちょうど1本に券を使い、その辺のコストだけを0にできるとする。資源消費は変えない。状態を拡張して最適経路を求めよ。負のコストの辺へ券を使うと不利になること、および券を使わない解を誤って採用しないための条件を明記せよ。
参考解答・採点の観点 — 問題2
(1) 状態と負コスト
を の総消費がちょうど の最小コストとする。、その他は。答えは 。負の辺では、一度確定した距離が後から減る可能性があるためダイクストラの確定の根拠が成立しない。DAGでは先行頂点の処理後にしか辺を緩和せず、負の閉路もないので同じ問題は起こらない。
(2) DAG上の緩和
D[all vertices,0..B] = infinity; D[s,0] = 0
for v in topological order:
for each edge e=(v,u):
for b=0,...,B-r(e):
if D[v,b] is finite:
D[u,b+r(e)] = min(D[u,b+r(e)], D[v,b]+c(e))
return min(D[t,0..B])の辺は飛ばす。資源が0でも、頂点のトポロジカル順位は必ず増えるので循環依存はない。時間 、補助空間 。前状態を記録すれば同空間内で復元できる。
(3) 予算制約の具体例
| 頂点 | 消費0 | 消費1 | 消費2 | 消費3 |
|---|---|---|---|---|
| 0 | ||||
| 4 | ||||
| -1 | 1 | |||
| 0 | 2 | |||
| 2 | -2 |
最適値-2、経路 、消費3。 はコスト0だが消費4で予算を超える。
(4) 候補ラベルの支配
同じ続きを付けたとき、消費は 、コストは 。後者が予算内なら前者も予算内で、コストも悪化しない。 が負でもこの不等式は成立するので支配された候補を捨てられる。(3)では の は に、 の は に支配される。ただしちょうど の制約では、少ない消費を補う続きを必ず作れるとは限らず、この支配関係による削除は一般には正しくない。
(5) 擬多項式時間と背包への対応
の記述長は であり、 個の状態を作る方法は数値 に依存する擬多項式時間である。品物 の重さ 、価値 に対し、層頂点 から へ採用・不採用の二つの内部頂点を介する経路を作る。不採用側の全コスト・消費を0、採用側の最初の辺を 、残る辺を とする。各 経路は品物集合に一対一対応し、消費は総重量、コストは総価値の負数。したがって最小コストは価値最大化を表す。平行辺なしのDAGで実現できる。
(6) 一枚の券を使う拡張
を券の使用済み状態 で定義する。通常遷移はコスト を加え を保つ。 の場合だけ、コスト0で へ移る追加遷移を許す。いずれも消費 を加える。初期状態は 、答えは に限定する。 に券を使うと負の利得を失い、コストが増えるため、常に最小コスト辺へ使う貪欲法は不適切。全状態を比較すれば最適な使用位置を選べる。時間 、空間 のオーダーは同じ。
問題3 · 整列アルゴリズム(30点)¶
速い分割整列に最悪時の上限を付ける¶
個のレコードを比較により整列する。クイックソートの三分割でキーがピボット未満、等しい、超える区間へ分ける。残る分割回数の予算を初期値 とし、予算0ではその区間をヒープソートする。長さが固定定数 以下なら挿入整列する。この方法をイントロソートと呼ぶ。ピボット選択にはランダム性を仮定せず、各分割に区間長に比例する時間がかかるものとする。
(1) 三分割と安定性(5点)¶
区間の左端 lt、走査位置 、右端 gt を使う三分割の擬似コードとループ不変条件を示せ。入力 、ピボット2を処理し、キーだけで三分割すると安定性が保証されないことを確認せよ。
(2) 最悪入力と等値キー(4点)¶
(1)の三分割を使い、先頭をピボットにするクイックソートについて、相異なるキーが降順に並ぶ入力の最悪計算量を漸化式で求めよ。また、全キーが同じ入力で三分割が改善をもたらす理由を述べよ。
(3) 分割予算の引き継ぎ(7点)¶
分割予算を左右両方の部分区間に正しく引き継ぐイントロソートの擬似コードを書け。挿入整列、ヒープソート、等値区間を再帰対象から外す条件を明記せよ。
(4) 最悪時間の保証(6点)¶
分割段階、予算切れでのヒープソート、短い区間の挿入整列をそれぞれ評価し、全入力について最悪時間が であることを証明せよ。ピボットが極端に偏る場合も含めること。
(5) 小さい側だけの再帰(4点)¶
常に小さい側だけを再帰呼出しし、大きい側をループで処理するよう(3)を改良せよ。補助スタックが になる理由と、ループへ移った側でも予算を減らす必要がある理由を説明せよ。
(6) 安定化の時間と空間(4点)¶
安定整列が必要な場合、比較対象に元位置を付加して実現する方法を示せ。最悪時間と追加空間がどう変わるかを述べ、同じキーの要素が多い場合の三分割の利点との関係も説明せよ。
参考解答・採点の観点 — 問題3
(1) 三分割と安定性
lt=lo; i=lo; gt=hi; p=copy of pivot key
while i<=gt:
if key(A[i])<p: swap A[lt],A[i]; lt++; i++
else if key(A[i])>p: swap A[i],A[gt]; gt--
else: i++
return (lt,gt)不変条件は [) が未満、[) が等値、 が未処理、(] が超過。超過側へ交換した直後は新しく来た要素が未処理なので を増やさない。 では最後に1とを交換し となる。
(2) 最悪入力と等値キー
降順の相異なるキーでは先頭が最大である。(1)の分割後、小さい側は元の降順を保ち長さとなる。従って、より。昇順入力はこの三分割で残りの順序が変わるため、毎回先頭が最小という説明をそのまま使ってはならない。全キーが同じ場合、等値区間が全体となり左右は空で、一度の走査で終わる。等値を片側へ送る二分割ではの再帰が残り得る。
(3) 分割予算の引き継ぎ
INTRO(lo,hi,budget):
L=hi-lo+1
if L<=1: return
if L<=t: insertionSort(A[lo..hi]); return
if budget==0: heapSort(A[lo..hi]); return
(lt,gt)=partition3(A,lo,hi)
INTRO(lo,lt-1,budget-1)
INTRO(gt+1,hi,budget-1)
call INTRO(0,N-1,2*floor(log2(N))) if N>=2予算は再帰深さを表す局所値なので、片側の処理で減った値をもう片側へ流用するのではなく、両方へ同じ を渡す。
(4) 最悪時間の保証
各分割深さで処理する区間は互いに素なので、1段の仕事は 。分割深さは高々 で、合計 。予算切れの区間は互いに素で、その長さを とすると 。ヒープソート合計は 。短い区間も互いに素で、挿入整列費用の合計は 。偏ったピボットでも予算により分割の継続回数が制限される。
(5) 小さい側だけの再帰
分割後に とし、小さい側を で処理する。大きい側の を現在フレームへ代入し、 としてループを続ける。小さい側の長さは元区間の半分以下なので、積まれるフレームのサイズは少なくとも半減し、深さ 。大きい側でも1回分割した事実は同じであり、予算を減らさないと偏り続ける入力で最悪保証が失われる。分割とヒープソート自体の補助領域は 。
(6) 安定化の時間と空間
比較キーを (元キー,元位置) の辞書順にする。各レコードの元位置は一意なので、最終整列順は元キーの昇順、同キーでは元位置の昇順となる。最悪時間は のまま。元位置タグを新設するなら の追加領域と のスタックが必要。同じ元キーでも全比較キーは異なるため、三分割による大きな等値区間の省略は失われる。