第7回 縮約と最適な結合順序
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 180分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
追加辺によって消える橋を一括して求める¶
単純連結無向グラフ に新しい辺を追加する。橋をすべて除いた後の連結成分を頂点に縮約し、元の橋を辺とするグラフ を橋木と呼ぶ。追加辺の両端が同じ縮約頂点に属する場合もある。頂点数を 、辺数を 、橋木の頂点数を とする。辺の追加だけを行い、削除は行わない。複数追加する場合の新しい辺は相異なるものとする。
(1) 橋木の性質(5点)¶
橋木 が連結かつ閉路を持たないことを証明せよ。また、各縮約成分の内部の辺が追加後に橋になることはないことを示せ。単に橋木という名称から木であると仮定してはならない。
(2) 一本の追加辺の影響(5点)¶
縮約頂点 に属する頂点間に辺を1本追加する。元の橋のうち橋でなくなるものが、 の 経路上の辺とちょうど一致することを、必要性と十分性に分けて証明せよ。
(3) 橋と縮約成分の具体例(6点)¶
四つの三角形 、、、 に加え、辺 がある。辺 を追加した後の橋と縮約成分を求めよ。続けて を追加するとどう変わるか。
(4) 一括追加と順序依存性(6点)¶
元の に 本の辺を一括追加する場合を考える。橋木の各辺について、追加辺の端点を結ぶ木経路に少なくとも一度含まれるかどうかを調べれば十分であることを証明せよ。追加の順序による影響も論じよ。
(5) 差分と木パスの被覆(7点)¶
橋木を根付き木とし、追加辺の縮約端点を 、最低共通祖先を とする。差分配列に を行い、後順走査で子の値を親へ足す方法を設計せよ。各木辺の被覆回数になる理由を示せ。
(6) 全体の処理と計算量(6点)¶
橋の発見、縮約、最低共通祖先の前処理、差分集計までを含む全体の擬似コードと計算量を示せ。最低共通祖先は2の累乗個の祖先を保存して二分持ち上げで求めるものとし、その処理を説明せよ。
参考解答・採点の観点 — 問題1
(1) 橋木の性質
の任意の経路は縮約後も経路を与えるので は連結。 に閉路があると、その閉路上の元の橋について、端点間を他の縮約辺と成分内の経路で結べる。その橋を消しても接続が残り、橋の定義に反する。よって は木。元の非橋辺にはそれを避ける端点間経路があり、辺を追加してもその経路は失われないため、新たな橋にはならない。
(2) 一本の追加辺の影響
経路上の橋 を除くと は二つに分かれ、 は異なる側にある。追加辺が両側を再接続するため は橋でなくなる。経路外の橋を除いた分割では は同じ側にあり、追加辺は分割をまたがない。したがってその橋は残る。 の場合は木経路が空であり、どの橋も消えない。
(3) 橋と縮約成分の具体例
最初の橋木は 、、、、辺 、、。 の追加で と が消え、残る橋は 。縮約成分は と 。
続いて が残る橋をまたぐので も橋でなくなる。全12頂点が一つの縮約成分となり、橋はない。
(4) 一括追加と順序依存性
元の橋 を取り除いた二分割を固定する。追加辺のいずれかがこの分割をまたぐなら、 を使わない再接続ができる。どの追加辺もまたがないなら、 を除いた二群は依然として分離する。追加辺が分割をまたぐことは、元の橋木でその端点間経路が を含むことと同値。元の非橋辺と追加辺自身は、追加によって橋にはならない。追加辺は追加時点で既存の端点間経路と閉路を作るからである。判定は元の分割と追加辺の集合だけで決まり、順序に依存しない。
(5) 差分と木パスの被覆
すべての追加辺について差分更新し、根以外の頂点 の部分木和 を求める。親辺 の被覆回数は 。ある1組 の寄与は、部分木に端点が1個だけあると1、両方入ると 、どちらもないと0。 が部分木内にあるのは両端点が入る場合だけなので、親辺をまたぐ経路の本数を正確に数える。したがって の元の橋だけが残る。同じ縮約端点なら差分は相殺される。
(6) 全体の処理と計算量
find every bridge of G by DFS discovery/low values
flood-fill G while ignoring bridges; assign component IDs
build T from the bridges and component IDs
root T; compute depth and up[v][0] = parent(v)
for j = 1,...,ceil(log2(b+1)):
up[v][j] = up[up[v][j-1]][j-1]
Delta[all vertices] = 0
for each added edge x-y:
A = component[x]; B = component[y]
L = LCA(A,B)
Delta[A] += 1; Delta[B] += 1; Delta[L] -= 2
for v in postorder excluding root:
if Delta[v] == 0: output original bridge parent(v)-v
Delta[parent(v)] += Delta[v]LCAは深い側を深さ差の2進表現に沿って持ち上げ、深さをそろえる。同じ頂点なら終了。異なる場合、上位の から、 祖先が異なるときだけ両方を持ち上げ、最後に親を返す。時間は 、補助空間 。追加辺を保存せず逐次読めば の保存領域は不要。
問題2 · 動的計画法(35点)¶
最適な行列積の個数と順位¶
行列 のサイズはそれぞれ であり、 は正整数とする。行列の順序は変えず、二項積の括弧付けだけを変える。 と の行列の積の費用は abc とし、総費用を最小化したい。費用の異なる計算経路だけでなく、同じ最小費用を持つ異なる括弧付けをすべて数える。括弧付けは内部節点の左右が区別される完全二分木として扱う。
(1) 状態と境界条件(5点)¶
区間 の最小費用 と、その費用を達成する括弧付け数 を定義し、境界条件を示せ。 の積のサイズが括弧付けによらないことも説明せよ。
(2) 最小費用と括弧付け数(7点)¶
最後の積を と に分ける場合の費用を導き、 の漸化式を示せ。最適な分割が複数ある場合の個数の計算では、加算と乗算をどのように使うか。
(3) 全区間の具体例(6点)¶
、 とする。すべての区間について を求め、最適な括弧付けを列挙せよ。単に最適値だけを答えてはならない。
(4) 正しさと二重計数(6点)¶
区間長に関する帰納法でDPの正しさを証明せよ。また、分割位置を区別することが二重計数を防ぐ理由を示し、最適な左右の部分木の任意の組が全体の最適解になる条件を述べよ。
(5) 指定順位の復元(6点)¶
最適括弧付けを、根の分割位置 の昇順、次に左部分木の順位、最後に右部分木の順位で再帰的に並べる。 が与えられたとき、 番目だけを列挙なしで復元するアルゴリズムを示せ。(3)の2番目も答えよ。
(6) 復元と大整数の計算量(5点)¶
DPの時間・空間計算量と(5)の復元時間を、算術演算を単位時間として求めよ。個数が ビットに収まることを説明し、大整数の乗算を単位時間とみなせない場合の注意点も述べよ。
参考解答・採点の観点 — 問題2
(1) 状態と境界条件
は区間積の最小スカラー乗算数、 はその最適括弧付け数。、。区間積のサイズは 。結合するたびに中間次元が一致し、外側の行数と列数だけが残るので、括弧付けによらない。
(2) 最小費用と括弧付け数
分割 の候補費用は 。。
。
左右の最適木は独立に選べるため、固定した の組合せ数は積となる。根の分割位置が異なる木は相異なるため、最適な 全体について加算する。区間長の順で処理する。
(3) 全区間の具体例
| 区間 | ||
|---|---|---|
| 各 | 0 | 1 |
| 12 | 1 | |
| 12 | 1 | |
| 12 | 1 | |
| 20 | 1 | |
| 20 | 1 | |
| 28 | 2 |
全区間 の分割 の候補費用はそれぞれ。最適木は と 。どちらも の積に12、残る2回の積に8ずつ必要。
(4) 正しさと二重計数
長さ1の区間は境界条件どおり。長い区間の任意の木には一意な根の分割 がある。左右の部分木がその区間で最適でなければ、より安い木に置換して全体を改善できる。したがって最適木は最適な左右の組から生まれる。逆に の分割で左右の最適木を選べば、全体の費用は 。根の は各木について一意で、固定 では左右の木の組も一意なので二重計数はない。
(5) 指定順位の復元
各最適分割 のブロックの大きさを とする。 の昇順にブロックを調べ、 なら 。該当ブロックでは右の個数 を使い、左順位 、右順位 とする。左右を同様に復元する。
各ブロックは左順位を先、右順位を後に変化させる直積順序なので、この割算で位置を一意に求められる。(3)の2番目は根の分割 を持つ 。
(6) 復元と大整数の計算量
DPは 時間・ 空間。復元時、長さ の区間で高々 個の分割を調べる。二分木全体での区間長の和は なので復元時間は 、出力長は 。最適分割リストを前計算しても最悪上界は同じ。
すべての括弧付け数は第 カタラン数であり、完全二分木を左右括弧の列へ符号化すると高々 通り。よって個数は ビット。各DP更新には ビットの個数の乗算があり、例えば筆算乗算では1回 ビット演算となるため、個数計算全体の単純な上界は 。費用のビット演算は別途考える必要がある。
問題3 · 整列アルゴリズム(30点)¶
自由な二本併合と最適併合木¶
整列済みの 本のレコード列があり、その長さを正整数 とする。今回は隣接という制限を設けず、任意の二列を併合できる。長さ の併合費用は である。全入力を の順に連結したときの安定性は維持したい。各レコードに元の連結列内の位置を記録し、比較ではキーの後にその位置を用いてよい。
(1) 併合木と重み付き深さ(5点)¶
任意の併合順が葉重み を持つ完全二分木に対応することを説明し、総費用が となることを示せ。ここで は葉 の深さである。
(2) 最短二列の併合例(4点)¶
常に最短の二列を併合する方法を、重み で実行せよ。同じ重みなら、その木に含まれる元の列番号の最小値が小さい方を先に選ぶ。各併合費用、総費用、各元の列の深さを求めよ。
(3) 交換法と貪欲法の証明(7点)¶
最小の二重みを兄弟の最深葉に置く最適木が存在することを交換法で証明せよ。続いてその二葉を一葉へ縮約し、貪欲法全体の最適性を帰納法で示せ。
(4) 最小ヒープと安定性(6点)¶
最小ヒープを用いて最適併合木を構築する擬似コードを示せ。構築時間と、実際にレコードを併合する総時間を区別して求めよ。元のキーだけで比較した場合と、元位置を付加した場合の安定性も説明せよ。
(5) 自由併合と隣接併合(4点)¶
長さ の列について、自由併合の最小費用と、隣接列だけを併合する場合の最小費用を求めよ。この差が貪欲法の証明のどの前提に由来するかを説明せよ。
(6) 同重みと不均等な長さ(4点)¶
重みがすべて同じで の場合の最小費用を と で表せ。また、1本の列が極端に長い場合、列数だけを均等に分割する方法より貪欲併合が有利になる理由を述べよ。
参考解答・採点の観点 — 問題3
(1) 併合木と重み付き深さ
各併合を内部節点、元の列を葉とする。各内部節点の費用は、その部分木に含まれる葉重みの和。一つの葉 の要素は、葉から根までの 個の併合に参加する。費用を葉ごとに数え直すと、総費用は 。任意の完全二分木も、その内部節点を後順に処理すれば合法な自由併合順を与える。
(2) 最短二列の併合例
併合は 、、、。3回目で選ぶ12は、最小元番号1を持つ合成木である。総費用は 。元の列の深さは で、 と一致する。
(3) 交換法と貪欲法の証明
最適木の最深葉の一つを選ぶと、その兄弟も葉で同じ深さである。兄弟が内部節点なら、さらに深い葉があることになり矛盾する。小さい重み が浅い位置、より大きい重み が深い位置にあるなら、交換後の費用差は (深浅。これを繰り返し、最小二重みをその最深兄弟葉へ移せる。費用は増えず、依然として最適木である。
この二葉を重み の葉へ縮約すると費用はちょうど 減る。縮約木が残りの重みに対して最適でなければ、より良い縮約木へ置換して元の最適木を改善できる。したがって最小二重みを先に結び、縮約問題を最適に解く帰納法が成立する。
(4) 最小ヒープと安定性
H = min-heap containing each leaf (weight, minOriginalIndex)
while |H| > 1:
x = extractMin(H); y = extractMin(H)
z = node(left=x, right=y, weight=x.weight+y.weight)
z.minOriginalIndex = min(x.minOriginalIndex,y.minOriginalIndex)
insert(H,z)
return the remaining root葉のヒープ構築は 、 回の併合選択は 、木の空間は 。実際の併合は木の後順に行い、時間は 。キーだけで比較すると、元の入力で離れた列を先に結ぶため、同じキーの順を最後の左右優先だけで保証できない。比較キーを (元キー,元位置) にすれば、最終的に元位置の昇順となり、自由な併合順でも安定になる。
(5) 自由併合と隣接併合
自由併合では両端の1を先に結び、。隣接制限では最初に1と100を結ぶほかなく、。交換法は葉の配置を自由に交換しても合法な木であることを用いている。葉の左から右の順序を固定する隣接併合では、この交換を任意には行えない。
(6) 同重みと不均等な長さ
同重みで葉数がなら貪欲法は各段で同じ重みの木を組にし、全葉の深さが の完全な木を作る。費用は Nh。極端に長い列は、貪欲法では小さい列の合成重みが十分大きくなるまで選ばれにくく、浅い葉になる。列数で均等に分ける方法は、その長い列も 回処理する。総費用が重み付き深さであるため、重い葉を浅くすることが有利である。