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.

第7回 縮約と最適な結合順序

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

← 备考目录

試験時間(目安)満点問題数
180分100点全3問
問題分野テーマ配点
問題1グラフ理論追加辺によって消える橋を一括して求める35点
問題2動的計画法最適な行列積の個数と順位35点
問題3整列アルゴリズム自由な二本併合と最適併合木30点

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

追加辺によって消える橋を一括して求める

単純連結無向グラフ GG に新しい辺を追加する。橋をすべて除いた後の連結成分を頂点に縮約し、元の橋を辺とするグラフ TT を橋木と呼ぶ。追加辺の両端が同じ縮約頂点に属する場合もある。頂点数を nn、辺数を mm、橋木の頂点数を bb とする。辺の追加だけを行い、削除は行わない。複数追加する場合の新しい辺は相異なるものとする。

(1) 橋木の性質(5点)

橋木 TT が連結かつ閉路を持たないことを証明せよ。また、各縮約成分の内部の辺が追加後に橋になることはないことを示せ。単に橋木という名称から木であると仮定してはならない。

(2) 一本の追加辺の影響(5点)

縮約頂点 A,BA,B に属する頂点間に辺を1本追加する。元の橋のうち橋でなくなるものが、TT の A−BA-B 経路上の辺とちょうど一致することを、必要性と十分性に分けて証明せよ。

(3) 橋と縮約成分の具体例(6点)

四つの三角形 {1,2,3}\{1,2,3\}、{4,5,6}\{4,5,6\}、{7,8,9}\{7,8,9\}、{10,11,12}\{10,11,12\} に加え、辺 {3,4},{6,7},{5,10}\{3,4\},\{6,7\},\{5,10\} がある。辺 {2,8}\{2,8\} を追加した後の橋と縮約成分を求めよ。続けて {1,11}\{1,11\} を追加するとどう変わるか。

(4) 一括追加と順序依存性(6点)

元の GG に qq 本の辺を一括追加する場合を考える。橋木の各辺について、追加辺の端点を結ぶ木経路に少なくとも一度含まれるかどうかを調べれば十分であることを証明せよ。追加の順序による影響も論じよ。

(5) 差分と木パスの被覆(7点)

橋木を根付き木とし、追加辺の縮約端点を A,BA,B、最低共通祖先を LL とする。差分配列に Δ[A]++,Δ[B]++,Δ[L]−=2\Delta [A]++, \Delta [B]++, \Delta [L]-=2 を行い、後順走査で子の値を親へ足す方法を設計せよ。各木辺の被覆回数になる理由を示せ。

(6) 全体の処理と計算量(6点)

橋の発見、縮約、最低共通祖先の前処理、差分集計までを含む全体の擬似コードと計算量を示せ。最低共通祖先は2の累乗個の祖先を保存して二分持ち上げで求めるものとし、その処理を説明せよ。

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

最適な行列積の個数と順位

行列 A1,…,AnA_{1},\ldots ,A_{n} のサイズはそれぞれ pi−1×pip_{i-1}\times p_{i} であり、pip_{i} は正整数とする。行列の順序は変えず、二項積の括弧付けだけを変える。a×ba\times b と b×cb\times c の行列の積の費用は abc とし、総費用を最小化したい。費用の異なる計算経路だけでなく、同じ最小費用を持つ異なる括弧付けをすべて数える。括弧付けは内部節点の左右が区別される完全二分木として扱う。

(1) 状態と境界条件(5点)

区間 [i,j][i,j] の最小費用 M(i,j)M(i,j) と、その費用を達成する括弧付け数 C(i,j)C(i,j) を定義し、境界条件を示せ。Ai…AjA_{i}\ldots A_{j} の積のサイズが括弧付けによらないことも説明せよ。

(2) 最小費用と括弧付け数(7点)

最後の積を Ai…AkA_{i}\ldots A_{k} と Ak+1…AjA_{k+1}\ldots A_{j} に分ける場合の費用を導き、M,CM,C の漸化式を示せ。最適な分割が複数ある場合の個数の計算では、加算と乗算をどのように使うか。

(3) 全区間の具体例(6点)

n=4n=4、(p0,p1,p2,p3,p4)=(2,2,3,2,2)(p_{0},p_{1},p_{2},p_{3},p_{4})=(2,2,3,2,2) とする。すべての区間について M,CM,C を求め、最適な括弧付けを列挙せよ。単に最適値だけを答えてはならない。

(4) 正しさと二重計数(6点)

区間長に関する帰納法でDPの正しさを証明せよ。また、分割位置を区別することが二重計数を防ぐ理由を示し、最適な左右の部分木の任意の組が全体の最適解になる条件を述べよ。

(5) 指定順位の復元(6点)

最適括弧付けを、根の分割位置 kk の昇順、次に左部分木の順位、最後に右部分木の順位で再帰的に並べる。1≤z≤C(1,n)1\le z\le C(1,n) が与えられたとき、zz 番目だけを列挙なしで復元するアルゴリズムを示せ。(3)の2番目も答えよ。

(6) 復元と大整数の計算量(5点)

DPの時間・空間計算量と(5)の復元時間を、算術演算を単位時間として求めよ。個数が O(n)O(n) ビットに収まることを説明し、大整数の乗算を単位時間とみなせない場合の注意点も述べよ。

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

自由な二本併合と最適併合木

整列済みの kk 本のレコード列があり、その長さを正整数 w1,…,wkw_{1},\ldots ,w_{k} とする。今回は隣接という制限を設けず、任意の二列を併合できる。長さ a,ba,b の併合費用は a+ba+b である。全入力を A1,A2,…,AkA_{1},A_{2},\ldots ,A_{k} の順に連結したときの安定性は維持したい。各レコードに元の連結列内の位置を記録し、比較ではキーの後にその位置を用いてよい。

(1) 併合木と重み付き深さ(5点)

任意の併合順が葉重み wiw_{i} を持つ完全二分木に対応することを説明し、総費用が ∑iwidi\sum_i w_{i}d_{i} となることを示せ。ここで did_{i} は葉 ii の深さである。

(2) 最短二列の併合例(4点)

常に最短の二列を併合する方法を、重み (2,3,7,8,12)(2,3,7,8,12) で実行せよ。同じ重みなら、その木に含まれる元の列番号の最小値が小さい方を先に選ぶ。各併合費用、総費用、各元の列の深さを求めよ。

(3) 交換法と貪欲法の証明(7点)

最小の二重みを兄弟の最深葉に置く最適木が存在することを交換法で証明せよ。続いてその二葉を一葉へ縮約し、貪欲法全体の最適性を帰納法で示せ。

(4) 最小ヒープと安定性(6点)

最小ヒープを用いて最適併合木を構築する擬似コードを示せ。構築時間と、実際にレコードを併合する総時間を区別して求めよ。元のキーだけで比較した場合と、元位置を付加した場合の安定性も説明せよ。

(5) 自由併合と隣接併合(4点)

長さ (1,100,1)(1,100,1) の列について、自由併合の最小費用と、隣接列だけを併合する場合の最小費用を求めよ。この差が貪欲法の証明のどの前提に由来するかを説明せよ。

(6) 同重みと不均等な長さ(4点)

重みがすべて同じで k=2hk=2^{h} の場合の最小費用を N=∑wiN=\sum w_{i} と hh で表せ。また、1本の列が極端に長い場合、列数だけを均等に分割する方法より貪欲併合が有利になる理由を述べよ。