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.

第6回 解の証明書と適応的アルゴリズム

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

← 备考目录

試験時間(目安)満点問題数
180分100点全3問
問題分野テーマ配点
問題1グラフ理論二部判定に証明書を付ける35点
問題2動的計画法指定回数の特別辺を通る最短経路35点
問題3整列アルゴリズム連続整列区間を発見して併合する30点

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

二部判定に証明書を付ける

単純無向グラフ G=(V,E)G=(V,E) の各頂点に 0 または 1 を割り当て、すべての辺の両端を異なる値にしたい。実現可能な割当て、または不可能であることを示す単純奇閉路を出力する問題を考える。GG は非連結でもよい。n=∣V∣n=\vert V\vert、m=∣E∣m=\vert E\vert とし、隣接リストが与えられる。BFSでは未訪問の隣接頂点を番号順に処理する。

(1) BFSの具体例と奇閉路(5点)

V={1,…,8}V=\{1,\ldots ,8\}、E={{1,2},{2,3},{3,4},{4,5},{5,6},{6,1},{3,7},{7,8},{8,4}}E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,1\},\{3,7\},\{7,8\},\{8,4\}\} とする。頂点1からBFSを行い、距離と二部の分割を求めよ。その後、辺 {1,8}\{1,8\} を追加したグラフが二部グラフでないことを、具体的な奇閉路で示せ。

(2) 親経路からの奇閉路復元(6点)

BFS木の距離を dd とする。辺 {u,v}\{u,v\} で d(u),d(v)d(u),d(v) の偶奇が等しいとき、親ポインタと最低共通祖先を利用して単純奇閉路を構成せよ。構成した列に頂点の重複がなく、長さが奇数になることを証明せよ。

(3) 線形時間の判定と検証(6点)

二部の割当てまたは奇閉路を必ず出力する O(n+m)O(n+m) 時間のアルゴリズムを示せ。第三者が、その出力だけから結論の正しさを確認する方法も説明せよ。非連結グラフと孤立頂点を取りこぼしてはならない。

(4) 最短奇閉路(7点)

不可能の場合には最短の奇閉路を出力したい。すべての根からBFSを行い、同じ偶奇を持つ辺について d(u)+d(v)+1d(u)+d(v)+1 が最小の組を選ぶ方法を考える。この方法の正しさと O(n(n+m))O(n(n+m)) 時間の実装を示せ。各候補の親経路を毎回展開してはならない。

(5) 色差を保持するUnion-Find(6点)

辺が1本ずつ到着し、最初に矛盾が発生するまで割当ての実現可能性を調べたい。各頂点から集合代表への色の差を1ビットで保持する Union-Find を設計せよ。サイズによる併合のみを使い、各操作を O(log⁡(n+1))O(\log(n+1)) 時間にせよ。

(6) 矛盾時の証明書(5点)

(5)で矛盾を初めて検出した際にも奇閉路を出力したい。Union-Find の親ポインタをグラフの辺と見なしてよいかを論じ、正しい証明書を得るための追加データと処理を示せ。矛盾検出後の追加時間は O(n+m)O(n+m) 以内とせよ。

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

指定回数の特別辺を通る最短経路

単純有向非巡回グラフ GG の始点 ss と終点 tt が指定される。各辺 ee には整数コスト w(e)w(e) とラベル b(e)∈{0,1}b(e)\in \{0,1\} がある。ラベル1の辺をちょうど rr 本通る s−ts-t 経路の最小コストと、そのコストを達成する異なる頂点列の数を求めたい。負のコストも認める。経路数は剰余を取らず正確に数える。トポロジカル順序は入力として与えられ、ss は先頭、tt は末尾である。

(1) 状態と初期値(5点)

各頂点と使用済みのラベル1の本数を状態とする動的計画法を定義し、最適コストと個数の初期値を示せ。到達不能な状態、および長さ0の経路をどのように扱うかを明記せよ。

(2) コストと個数の更新(6点)

辺をトポロジカル順に緩和する際の更新式を導け。新しい候補が現在値より小さい場合、等しい場合、大きい場合を区別せよ。状態数と辺の処理回数も示せ。

(3) 具体例と全最適経路(6点)

r=2r=2、頂点順 s,a,b,c,d,ts,a,b,c,d,t とする。辺の組 (始点,終点,w,bw,b) は (s,a,2,0),(s,b,1,1),(a,c,1,1),(a,d,3,0),(b,c,2,0),(b,d,4,1),(c,d,1,0),(c,t,4,1),(d,t,2,1)(s,a,2,0),(s,b,1,1),(a,c,1,1),(a,d,3,0),(b,c,2,0),(b,d,4,1),(c,d,1,0),(c,t,4,1),(d,t,2,1)。全頂点のコスト表を完成させ、最適値、最適経路数、すべての最適経路を求めよ。

(4) 正しさと重複計数(7点)

漸化式が最小コストと個数を同時に正しく求めることを証明せよ。負の辺があっても証明が成立する理由、および複数の遷移から同じ経路を重複して数えない理由を説明せよ。

(5) 辞書順最小の復元(6点)

最適経路のうち、頂点の全順序 s<a<b<c<d<ts<a<b<c<d<t による辞書順最小の経路を復元したい。逆向きの動的計画法と前向きの選択を組み合わせる方法を示し、(3)での結果を求めよ。

(6) 算術演算とビット計算量(5点)

単位時間の算術演算モデルでの時間・空間計算量を示せ。さらに、単純DAGにおける経路数のビット数が O(n)O(n) であることを示し、コスト演算を単位時間としたまま、個数の加算をビット単位で数えるときの時間上界を求めよ。

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

連続整列区間を発見して併合する

NN 個のレコードをキーの非減少順に安定整列したい。入力を左から走査し、キーが非減少となる極大の連続区間をランと呼ぶ。ラン数を rr、長さを n1,…,nrn_{1},\ldots ,n_{r} とする。併合は隣接する二つの区間にだけ行い、長さ a,ba,b の併合に a+ba+b の費用がかかるものとする。元の相対順序を保つ安定な併合を使う。ラン境界の検出時間も全体の計算量に含める。

(1) ランと安定性(5点)

入力 [1a,3,5,2a,2b,4,0,6,7,1b,8][1_{a},3,5,2_{a},2_{b},4,0,6,7,1_{b},8] のランを求め、安定整列の結果を示せ。非増加の区間を逆転してランにする工夫が安定性を壊す例も示し、どの種類の下降区間なら安全に逆転できるかを説明せよ。

(2) 安定な隣接併合(5点)

二つの隣接ランを安定に併合する擬似コードを示せ。比較回数が高々 a+b−1a+b-1 となること、同じキーの際の選択が入力全体の安定性を保つことを証明せよ。

(3) ラン数による均等分割(5点)

ランの個数をほぼ半分に分け、各側を再帰的に併合する方法を設計せよ。時間が O(N(1+log⁡r))O(N(1+\log r))、補助空間が O(N)O(N) となる理由を、各要素が参加する併合回数を用いて説明せよ。

(4) 不均等なラン長(5点)

r=2hr=2^{h} とし、先頭 r−1r-1 本のランの長さが1、最後のランの長さが MM であるとする。ラン数で均等に分割する方法と、短いランを先にまとめてから最後のランを併合する方法の費用を比較せよ。M≥r2M\ge r^{2} のとき、両者の費用比を評価せよ。

(5) 最小併合費用の区間DP(6点)

入力のラン順を保ったまま併合費用を最小化したい。区間 [i,j][i,j] に対する状態を定義し、漸化式、境界条件、最適な併合順の復元法を示せ。前計算を含む時間・空間計算量も求めよ。

(6) 具体例と隣接制約(4点)

長さ [1,1,1,M][1,1,1,M] の4ランについて(5)の最小費用を求めよ。ただし M≥3M\ge 3 とする。また、ランの位置を無視して常に最短の2本を併合する方法が、そのまま隣接併合のアルゴリズムにはならない理由を具体例で説明せよ。