Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

第9回 有向構造と最悪時の保証

グラフ理論・動的計画法・整列アルゴリズム

← 备考目录

試験時間(目安)満点問題数
180分100点全3問
問題分野テーマ配点
問題1グラフ理論強連結成分を縮約して到達可能性を整理する35点
問題2動的計画法負のコストと資源予算を両立する経路35点
問題3整列アルゴリズム速い分割整列に最悪時の上限を付ける30点

問題1 · グラフ理論(35点)

強連結成分を縮約して到達可能性を整理する

有向グラフ GG の二頂点 u,vu,v が互いに到達可能なとき u vu~v と書く。長さ0の経路も認める。この関係の同値類を強連結成分と呼ぶ。各成分を一頂点に縮約し、異なる成分間の辺だけを残した単純有向グラフを縮約グラフとする。GG の頂点数 nn、辺数 mm とし、元のグラフと全辺を反転したグラフの隣接リストを使用できる。

(1) 強連結成分の具体例(5点)

頂点 a,…,ha,\ldots ,h、辺 a→b,b→c,c→a,c→d,b→e,d→e,e→d,e→f,f→g,g→f,g→h,a→f,b→ha\to b,b\to c,c\to a,c\to d,b\to e,d\to e,e\to d,e\to f,f\to g,g\to f,g\to h,a\to f,b\to h を持つグラフの強連結成分と縮約グラフを求めよ。縮約グラフの入次数0、出次数0の頂点も示せ。

(2) 同値関係と縮約DAG(6点)

~ が同値関係であり、縮約グラフがDAGになることを証明せよ。また、元グラフでの到達可能性が、成分間の縮約グラフでの到達可能性と対応することを示せ。

(3) 成分の終了時刻(6点)

元グラフのDFSの終了時刻を f(v)f(v)、成分 CC の最大終了時刻を F(C)F(C) とする。異なる成分間に辺 C→DC\to D があれば F(C)>F(D)F(C)>F(D) となることを証明せよ。先に発見される成分によって場合分けすること。

(4) 二回のDFSと非再帰実装(7点)

まず元グラフで終了順を計算し、次に逆グラフで終了時刻の降順に未訪問根からDFSする方法を説明・証明せよ。第1走査は再帰を使わず、頂点と次に調べる出辺位置を持つスタックで実装する擬似コードを書け。

(5) 開始点と終了点の最小数(5点)

選んだ開始頂点のいずれかから全頂点へ到達できるようにするため、開始頂点の最小個数を求めよ。同様に、各頂点から選んだ終了頂点のいずれかへ到達できるための最小個数も求め、(1)に適用せよ。

(6) 到達集合と不要辺の除去(6点)

縮約DAGで到達可能性を変えずに不要な辺をすべて除きたい。各頂点の到達集合をビット列で求め、後続頂点をトポロジカル順に処理するアルゴリズムを設計せよ。(1)の結果と時間計算量を示せ。1語で ww ビットのORを行えるものとする。

問題2 · 動的計画法(35点)

負のコストと資源予算を両立する経路

有向非巡回グラフ GG の各辺 ee に整数コスト c(e)c(e) と非負整数の資源消費 r(e)r(e) が与えられる。コストは負でもよく、資源消費0の辺もある。始点 ss から終点 tt へ、総消費が BB 以下となる経路の最小コストを求めたい。BB は非負整数で、トポロジカル順序を利用できる。辺と頂点の格納領域を除いた補助空間を評価し、算術演算と比較は単位時間とする。

(1) 状態と負コスト(5点)

消費量をちょうど bb とする状態を定義し、初期値と求める最終値を示せ。非負コスト用のダイクストラ法を直接使えない理由と、DAGの性質を使えば負のコストを扱える理由を説明せよ。

(2) DAG上の緩和(6点)

トポロジカル順の緩和を用いた擬似コードを書け。資源消費0の辺があっても依存関係に循環が生じないことを示し、時間・補助空間計算量を求めよ。

(3) 予算制約の具体例(6点)

B=3B=3、頂点順 s,a,b,c,ts,a,b,c,t とする。辺 (始点,終点,コスト,消費) は (s,a,4,0),(s,b,1,2),(a,b,−5,1),(a,c,2,2),(b,c,1,0),(b,t,3,1),(c,t,−2,2)(s,a,4,0),(s,b,1,2),(a,b,-5,1),(a,c,2,2),(b,c,1,0),(b,t,3,1),(c,t,-2,2)。全状態の最小コスト表、最適値、最適経路と総消費を求めよ。

(4) 候補ラベルの支配(6点)

同じ頂点の二つの候補ラベル (消費量,コスト) について、(b1,c1)(b_{1},c_{1}) が b1≤b2b_{1}\le b_{2}、c1≤c2c_{1}\le c_{2} を満たすなら (b2,c2)(b_{2},c_{2}) を捨ててよいことを証明せよ。負のコストの辺がある場合と、ちょうど BB 消費する問題に変更した場合を区別せよ。

(5) 擬多項式時間と背包への対応(6点)

BB が2進数で入力される場合、(2)の計算量が入力長の多項式とは限らないことを説明せよ。各品物の採用・不採用を層状DAGの二経路で表し、重さ上限付き価値最大化をこの経路問題へ変換せよ。

(6) 一枚の券を使う拡張(6点)

通過する辺のうちちょうど1本に券を使い、その辺のコストだけを0にできるとする。資源消費は変えない。状態を拡張して最適経路を求めよ。負のコストの辺へ券を使うと不利になること、および券を使わない解を誤って採用しないための条件を明記せよ。

問題3 · 整列アルゴリズム(30点)

速い分割整列に最悪時の上限を付ける

NN 個のレコードを比較により整列する。クイックソートの三分割でキーがピボット未満、等しい、超える区間へ分ける。残る分割回数の予算を初期値 2⌊log2N⌋2\lfloor log_{2}N\rfloor とし、予算0ではその区間をヒープソートする。長さが固定定数 t≥2t\ge 2 以下なら挿入整列する。この方法をイントロソートと呼ぶ。ピボット選択にはランダム性を仮定せず、各分割に区間長に比例する時間がかかるものとする。

(1) 三分割と安定性(5点)

区間の左端 lt、走査位置 ii、右端 gt を使う三分割の擬似コードとループ不変条件を示せ。入力 [2a,2b,1][2_{a},2_{b},1]、ピボット2を処理し、キーだけで三分割すると安定性が保証されないことを確認せよ。

(2) 最悪入力と等値キー(4点)

(1)の三分割を使い、先頭をピボットにするクイックソートについて、相異なるキーが降順に並ぶ入力の最悪計算量を漸化式で求めよ。また、全キーが同じ入力で三分割が改善をもたらす理由を述べよ。

(3) 分割予算の引き継ぎ(7点)

分割予算を左右両方の部分区間に正しく引き継ぐイントロソートの擬似コードを書け。挿入整列、ヒープソート、等値区間を再帰対象から外す条件を明記せよ。

(4) 最悪時間の保証(6点)

分割段階、予算切れでのヒープソート、短い区間の挿入整列をそれぞれ評価し、全入力について最悪時間が O(Nlog⁡(N+1))O(N \log(N+1)) であることを証明せよ。ピボットが極端に偏る場合も含めること。

(5) 小さい側だけの再帰(4点)

常に小さい側だけを再帰呼出しし、大きい側をループで処理するよう(3)を改良せよ。補助スタックが O(log⁡(N+1))O(\log(N+1)) になる理由と、ループへ移った側でも予算を減らす必要がある理由を説明せよ。

(6) 安定化の時間と空間(4点)

安定整列が必要な場合、比較対象に元位置を付加して実現する方法を示せ。最悪時間と追加空間がどう変わるかを述べ、同じキーの要素が多い場合の三分割の利点との関係も説明せよ。