第16回 故障に強い証明・循環する状態・順序制約 グラフ理論・動的計画法・整列アルゴリズム
← 备考目录
問題 分野 テーマ 配点 問題1 グラフ理論 全域木の全辺故障をまとめて診断する 35点 問題2 動的計画法 何周してもよい環状局所アラインメント 35点 問題3 整列アルゴリズム 並列段数を制限した最適な隣接併合 30点
問題1 · グラフ理論(35点) ¶ 全域木の全辺故障をまとめて診断する ¶ 連結単純無向グラフ G = ( V , E ) G=(V,E) G = ( V , E ) の各辺に正の重み w ( e ) w(e) w ( e ) があり、n = ∣ V ∣ ≥ 2 n=\vert V\vert \ge 2 n = ∣ V ∣ ≥ 2 、m = ∣ E ∣ m=\vert E\vert m = ∣ E ∣ とする。全域木 T T T が一つ与えられる。木辺 e e e を除くと T T T は二つの成分に分かれる。その間を結ぶ非木辺の最小重みを r ( e ) r(e) r ( e ) とし、候補がなければ r ( e ) = ∞ r(e)=\infty r ( e ) = ∞ とする。R ( T ) = max { r ( e ) : e ∈ T } R(T)=\max\{r(e):e\in T\} R ( T ) = max { r ( e ) : e ∈ T } を、どの木辺が1本故障しても必要となる修復辺の最大重みと定義する。修復は T T T の残りの辺を保って1本だけ追加する。単一の故障だけを調べる方法から出発し、全木辺に対する判定をまとめる方法を設計せよ。
(1) 修復候補と木パス(5点) ¶ 非木辺 f = { u , v } f=\{u,v\} f = { u , v } が木辺 e e e の修復候補となる必要十分条件を、T T T 上の u − v u-v u − v パスを用いて示せ。「e e e の端点に接続する非木辺だけを調べればよい」という主張への反例も与えよ。
(2) MSTの故障後の総重み(6点) ¶ さらに T T T が最小全域木であるとする。G − e G-e G − e が連結ならば、その最小全域木の総重みは W ( T ) − w ( e ) + r ( e ) W(T)-w(e)+r(e) W ( T ) − w ( e ) + r ( e ) であることを証明せよ。R ( T ) R(T) R ( T ) と故障後の最大総重みは異なる指標であることにも注意せよ。
(3) 全木辺の修復候補(7点) ¶ すべての非木辺について木上のパスをたどることで、各 r ( e ) r(e) r ( e ) と、その値を達成する修復辺を計算するアルゴリズムを示せ。時間と補助空間を評価し、計算結果だけでなく候補辺も保存する意義を述べよ。
(4) 閾値と差分集計(7点) ¶ 重みの閾値 B B B を固定する。T T T を根付き木とし、w ( f ) ≤ B w(f)\le B w ( f ) ≤ B の非木辺 f = { u , v } f=\{u,v\} f = { u , v } ごとに差分配列へ +1 を u , v u,v u , v 、-2 を L C A ( u , v ) LCA(u,v) L C A ( u , v ) に加える。子の値を親へ加算した後、非根頂点 x x x の値が何を表すか証明し、R ( T ) ≤ B R(T)\le B R ( T ) ≤ B の判定法を導け。
(5) 祖先表と二分探索(6点) ¶ 祖先を 2 j 2^j 2 j 段ずつ記録する表を使って LCA を計算する方法を説明せよ。非木辺の重みを整列し、(4)の判定と二分探索で R ( T ) R(T) R ( T ) を求める擬似コードを書け。LCA は最初に各非木辺について1回だけ求め、判定で再利用すること。
(6) 故障診断の具体例(4点) ¶ T T T がパス 1 − 2 − 3 − 4 − 5 1-2-3-4-5 1 − 2 − 3 − 4 − 5 で、木辺の重みが順に 2 , 2 , 3 , 1 2,2,3,1 2 , 2 , 3 , 1 、非木辺が ( 1 , 3 , 4 ) , ( 2 , 4 , 6 ) , ( 3 , 5 , 5 ) , ( 1 , 5 , 9 ) (1,3,4),(2,4,6),(3,5,5),(1,5,9) ( 1 , 3 , 4 ) , ( 2 , 4 , 6 ) , ( 3 , 5 , 5 ) , ( 1 , 5 , 9 ) である。括弧内は両端点と重みである。各 r ( e ) r(e) r ( e ) 、R ( T ) R(T) R ( T ) 、および各故障後の最小全域木の総重みを求めよ。
(1) 修復候補と木パス
T − e T-e T − e の二成分を S , V − S S,V-S S , V − S とする。u , v u,v u , v が別の成分にあることと、唯一の木上パスが e e e を含むことは同値である。これは木辺を除いた二成分間をパスが渡る場合だけ e e e を必要とするためである。反例として木パス 1 − 2 − 3 − 4 1-2-3-4 1 − 2 − 3 − 4 の e = { 2 , 3 } e=\{2,3\} e = { 2 , 3 } を選び、非木辺を { 1 , 4 } \{1,4\} { 1 , 4 } のみとすれば、この辺が唯一の修復辺でありながら e e e のいずれの端点にも接続しない。
(2) MSTの故障後の総重み
T − e T-e T − e に最小候補 f f f を加えると全域木になり、上界 W ( T ) − w ( e ) + r ( e ) W(T)-w(e)+r(e) W ( T ) − w ( e ) + r ( e ) が得られる。G − e G-e G − e の任意の全域木 U U U に e e e を加えると閉路ができ、その閉路には T − e T-e T − e の二成分を渡る辺 h ≠ e h\ne e h = e がある。U + e − h U+e-h U + e − h は G G G の全域木だから、T T T の最小性より W ( T ) ≤ W ( U ) + w ( e ) − w ( h ) W(T)\le W(U)+w(e)-w(h) W ( T ) ≤ W ( U ) + w ( e ) − w ( h ) 。h h h は e e e の修復候補なので w ( h ) ≥ r ( e ) w(h)\ge r(e) w ( h ) ≥ r ( e ) であり、W ( U ) ≥ W ( T ) − w ( e ) + r ( e ) W(U)\ge W(T)-w(e)+r(e) W ( U ) ≥ W ( T ) − w ( e ) + r ( e ) 。上界と一致する。最大総重みには − w ( e ) -w(e) − w ( e ) も含まれるので、単に W ( T ) + R ( T ) W(T)+R(T) W ( T ) + R ( T ) としてはならない。
(3) 全木辺の修復候補
各木辺の r r r を ∞ \infty ∞ 、証明書を未設定にする。非木辺 f f f の両端から深さの大きい側を親へ進め、共通祖先に達するまで、通過する各木辺 e e e について w ( f ) < r ( e ) w(f)<r(e) w ( f ) < r ( e ) なら r ( e ) = w ( f ) r(e)=w(f) r ( e ) = w ( f ) 、証明書= f =f = f と更新する。各パスは高々 n − 1 n-1 n − 1 辺なので O ( m n ) O(mn) O ( mn ) 時間、親・深さ・r r r ・証明書に O ( n ) O(n) O ( n ) 補助空間である。根付き木の構築は O ( n ) O(n) O ( n ) 。保存した f f f を実際に追加すれば修復でき、計算された数値が実現可能であることも確認できる。等重みなら辺番号の小さいものを保存するなど、規則を固定すればよい。
(4) 閾値と差分集計
非木辺1本の差分の寄与を考える。x x x の部分木に u , v u,v u , v がともに入る場合、LCA も入り、合計 1 + 1 − 2 = 0 1+1-2=0 1 + 1 − 2 = 0 。どちらも入らなければ0。一方だけ入る場合、LCA は部分木の外にあり合計1である。したがって部分木和 c [ x ] c[x] c [ x ] は、木辺 { parent ( x ) , x } \{\operatorname{parent}(x),x\} { parent ( x ) , x } の切断を渡る重み B B B 以下の非木辺の本数となる。全非根 x x x で c [ x ] > 0 c[x]>0 c [ x ] > 0 であることが必要十分である。これは T T T と重み B B B 以下の非木辺からなるグラフに橋がないこととも同値だが、T T T の辺自体に w ( e ) ≤ B w(e)\le B w ( e ) ≤ B を要求するわけではない。
(5) 祖先表と二分探索
up [ x ] [ 0 ] = parent ( x ) \operatorname{up}[x][0]=\operatorname{parent}(x) up [ x ] [ 0 ] = parent ( x ) 、up [ x ] [ j + 1 ] = up [ up [ x ] [ j ] ] [ j ] \operatorname{up}[x][j+1]=\operatorname{up}[\operatorname{up}[x][j]][j] up [ x ] [ j + 1 ] = up [ up [ x ] [ j ]] [ j ] を O ( n log n ) O(n \log n) O ( n log n ) で準備する。まず深さ差のビットに従って深い頂点を上げ、両者が異なるときは高い j j j から祖先が異なる範囲だけ同時に上げる。最後の親が LCA で、1回 O ( log n ) O(\log n) O ( log n ) である。
F = 非木辺の一覧、各辺の LCA を前計算
values = F の異なる重みを昇順に整列
check(B):
c[:] = 0
for (u,v,w,lca) in F:
if w <= B: c[u]+=1; c[v]+=1; c[lca]-=2
木の後行順で c[parent(x)] += c[x]
return 全非根 x について c[x]>0
if values が空、または not check(values[-1]): return ∞
二分探索で check が真になる最初の values を返す前計算 O ( n log n + m log n ) O(n \log n+m \log n) O ( n log n + m log n ) 、整列 O ( m log m ) O(m \log m) O ( m log m ) 、判定1回 O ( n + m ) O(n+m) O ( n + m ) 、判定回数 O ( log ( m + 1 ) ) O(\log(m+1)) O ( log ( m + 1 )) 。合計 O ( n log n + m log n + ( n + m ) log ( m + 1 ) ) O(n \log n+m \log n+(n+m)\log(m+1)) O ( n log n + m log n + ( n + m ) log ( m + 1 )) 、補助空間 O ( n log n + m ) O(n \log n+m) O ( n log n + m ) 。
(6) 故障診断の具体例
木辺の順に r = ( 4 , 4 , 5 , 5 ) r=(4,4,5,5) r = ( 4 , 4 , 5 , 5 ) 、したがって R ( T ) = 5 R(T)=5 R ( T ) = 5 。総重み W ( T ) = 8 W(T)=8 W ( T ) = 8 なので、故障後の最小総重みは ( 10 , 10 , 10 , 12 ) (10,10,10,12) ( 10 , 10 , 10 , 12 ) 。たとえば最後の辺の故障には { 3 , 5 } \{3,5\} { 3 , 5 } を追加する。この T T T は最小全域木である。各非木辺の重みが、その木上パスの最大辺重み以上であること、または通常の切断交換によって確認できる。
問題2 · 動的計画法(35点) ¶ 何周してもよい環状局所アラインメント ¶ 文字列 L = L 1 … L m L=L_{1}\ldots L_{m} L = L 1 … L m と環状文字列 C = C 1 … C n C=C_{1}\ldots C_{n} C = C 1 … C n (m ≥ 1 , n ≥ 2 m\ge 1,n\ge 2 m ≥ 1 , n ≥ 2 )がある。C C C は正方向に何周してもよい。L L L の連続部分文字列と周期列 C C C C C … CCCCC\ldots CCCCC … の有限連続部分文字列をアラインする。各列は文字対、L L L の文字とギャップ、またはギャップと C C C の文字であり、両側ギャップは禁止する。文字対の得点は S ( x , y ) S(x,y) S ( x , y ) 、同じ側の連続長 k ≥ 1 k\ge 1 k ≥ 1 のギャップ得点は − ( g o + k g e ) -(g_{o}+k g_{e}) − ( g o + k g e ) (g o , g e > 0 g_{o},g_{e}>0 g o , g e > 0 )である。空アラインメントの得点は0。H ( i , j ) H(i,j) H ( i , j ) は最後に消費した L L L の位置 i i i と C C C の位置 j j j における局所最大得点とし、空も候補に含める。C C C を消費しない列では j j j を固定する。
(1) 境界と空アラインメント(5点) ¶ E ( i , j ) E(i,j) E ( i , j ) を最終列が ( L i , − ) (L_{i},-) ( L i , − ) の最大得点、F ( i , j ) F(i,j) F ( i , j ) を最終列が ( − , C j ) (-,C_{j}) ( − , C j ) の最大得点とする。H ( 0 , j ) , E ( 0 , j ) H(0,j),E(0,j) H ( 0 , j ) , E ( 0 , j ) の境界値を定めよ。空アラインメントと実現不能状態を混同しないよう説明せよ。
(2) 前行からの更新(7点) ¶ p ( 1 ) = n , p ( j ) = j − 1 p(1)=n,p(j)=j-1 p ( 1 ) = n , p ( j ) = j − 1 (j > 1 j>1 j > 1 )とする。前の行の H , E H,E H , E が既知のとき E ( i , j ) E(i,j) E ( i , j ) の漸化式を導け。また B ( i , j ) B(i,j) B ( i , j ) を、最終列が L L L 側のギャップではない場合の最大得点(空を含む)として、B B B の式を導け。
(3) 最終ギャップと環状伝播(7点) ¶ F ( i , j ) F(i,j) F ( i , j ) を最終ギャップの長さ k k k と B B B を用いて表せ。k k k を無制限に試す必要がないことを証明せよ。さらに、環状配列の j = 1 j=1 j = 1 から n n n への通常の1回走査だけでは正しい行が得られない反例を与えよ。
(4) 二回の走査による閉包(7点) ¶ V [ j ] = B ( i , j ) − g o V[j]=B(i,j)-g_{o} V [ j ] = B ( i , j ) − g o と初期化し、j = 1 , … , n j=1,\ldots ,n j = 1 , … , n の順に V [ j ] ← max ( V [ j ] , V [ p ( j ) ] − g e ) V[j]\gets \max(V[j],V[p(j)]-g_{e}) V [ j ] ← max ( V [ j ] , V [ p ( j )] − g e ) を2回走査する。この処理が必要な環状閉包を与えることを証明し、全行を O ( m n ) O(mn) O ( mn ) 時間で求める擬似コードを書け。
(5) 周回する具体例(5点) ¶ L = A A B A L=AABA L = AA B A 、C = B A C=BA C = B A 、同字得点4、異字得点-5、g o = 2 , g e = 1 g_{o}=2,g_{e}=1 g o = 2 , g e = 1 とする。i = 0 , … , 4 i=0,\ldots ,4 i = 0 , … , 4 の H ( i , 1 ) , H ( i , 2 ) H(i,1),H(i,2) H ( i , 1 ) , H ( i , 2 ) を求め、最高得点のアラインメントを一つ示せ。環状境界を越える場所も明記せよ。
(6) 循環ポインタを使わない復元(4点) ¶ 最高得点のアラインメントを復元する情報を設計せよ。2回の走査による同じ行の依存を、循環するポインタにせず保存する方法を説明し、得点のみと復元つきの場合の空間を評価せよ。
(1) 境界と空アラインメント
すべての j j j について H ( 0 , j ) = 0 H(0,j)=0 H ( 0 , j ) = 0 、E ( 0 , j ) = − ∞ E(0,j)=-\infty E ( 0 , j ) = − ∞ とする。L L L の文字がないのに最終列 ( L i , − ) (L_{i},-) ( L i , − ) は作れないため E E E は実現不能である。一方、局所問題はどの C C C の位置からも開始でき、空の候補があるので H H H は0となる。C C C 側の文字だけを並べる負得点アラインメントは、H H H を0より大きくしない。答えは max 0 ≤ i ≤ m , 1 ≤ j ≤ n H ( i , j ) \max_{0\le i\le m,1\le j\le n} H(i,j) max 0 ≤ i ≤ m , 1 ≤ j ≤ n H ( i , j ) 。
(2) 前行からの更新
E ( i , j ) = max { H ( i − 1 , j ) − g o − g e , E ( i − 1 , j ) − g e } E(i,j)=\max\{H(i-1,j)-g_{o}-g_{e}, E(i-1,j)-g_{e}\} E ( i , j ) = max { H ( i − 1 , j ) − g o − g e , E ( i − 1 , j ) − g e } 。最初の項は新しいギャップ区間、第二項は延長である。H H H に E E E が含まれていても、区間を不必要に開き直す候補は g o > 0 g_{o}>0 g o > 0 のため延長に劣る。
B ( i , j ) = max { 0 , H ( i − 1 , p ( j ) ) + S ( L i , C j ) , E ( i , j ) } B(i,j)=\max\{0, H(i-1,p(j))+S(L_{i},C_{j}), E(i,j)\} B ( i , j ) = max { 0 , H ( i − 1 , p ( j )) + S ( L i , C j ) , E ( i , j )} 。
最終列が文字対なら両側を1文字戻し、L L L の文字のみなら E E E を使う。最後に H ( i , j ) = max { B ( i , j ) , F ( i , j ) } H(i,j)=\max\{B(i,j),F(i,j)\} H ( i , j ) = max { B ( i , j ) , F ( i , j )} となる。
(3) 最終ギャップと環状伝播
F ( i , j ) = max k ≥ 1 { B ( i , p k ( j ) ) − g o − k g e } F(i,j)=\max_{k\ge 1}\{B(i,p^{k}(j))-g_{o}-k g_{e}\} F ( i , j ) = k ≥ 1 max { B ( i , p k ( j )) − g o − k g e } 。最終ギャップの直前は L L L 側のギャップでない列、または空なので B B B を使う。同じ始点と終点を持つ k k k と k + n k+n k + n では、後者の得点が n g e n g_{e} n g e だけ低い。したがって 1 ≤ k ≤ n 1\le k\le n 1 ≤ k ≤ n に制限できる。1回走査への反例は n = 4 n=4 n = 4 、B = ( 0 , 0 , 10 , 0 ) B=(0,0,10,0) B = ( 0 , 0 , 10 , 0 ) 、g o = g e = 1 g_{o}=g_{e}=1 g o = g e = 1 。第3位置の大きい得点が第4位置、第1位置、第2位置へ回る必要があるが、第1・第2位置はすでに走査済みである。
(4) 二回の走査による閉包
閉包の値は V [ j ] = max 0 ≤ k ≤ n − 1 { B ( i , p k ( j ) ) − g o − k g e } V[j]=\max_{0\le k\le n-1}\{B(i,p^{k}(j))-g_{o}-k g_{e}\} V [ j ] = max 0 ≤ k ≤ n − 1 { B ( i , p k ( j )) − g o − k g e } 。初期状態が k = 0 k=0 k = 0 の全出発点を含む。任意の長さ n − 1 n-1 n − 1 以下の正方向パスは、最初の走査と次の走査の間に全辺を順番に緩和できるので、その候補が伝播する。逆に更新値は実在するパスの得点であり、1周以上を含むパスは周回部分を取り除けば必ず改善する。よって2回で十分である。F ( i , j ) = V [ p ( j ) ] − g e F(i,j)=V[p(j)]-g_{e} F ( i , j ) = V [ p ( j )] − g e 。
H[:] = 0; E[:] = −∞; best = 0
for i = 1..m:
for j = 1..n:
nextE[j] = max(H[j]-gₒ-gₑ, E[j]-gₑ)
B[j] = max(0, H[p(j)]+S(Lᵢ,Cⱼ), nextE[j])
V[j] = B[j]-gₒ
repeat twice:
for j = 1..n: V[j] = max(V[j], V[p(j)]-gₑ)
for j = 1..n: nextH[j] = max(B[j], V[p(j)]-gₑ)
H,E = nextH,nextE
best = max(best, max(H))得点だけなら O ( n ) O(n) O ( n ) 補助空間、各行の処理 O ( n ) O(n) O ( n ) 、全体 O ( m n ) O(mn) O ( mn ) 。
(5) 周回する具体例
i i i 終端 B B B 終端 A A A 0 0 0 1 1 4 2 2 5 3 9 6 4 10 13 最高得点は13。たとえば L : A − A B A L: A - A B A L : A − A B A と C : A B A B A C: A B A B A C : A B A B A を対応させる。4回の一致で16、長さ1の L L L 側ギャップで -3、合計13。C C C の位置列は 2 , 1 , 2 , 1 , 2 2,1,2,1,2 2 , 1 , 2 , 1 , 2 であり、第1列→ \to → 第2列と第3列→ \to → 第4列で 2 → 1 2\to 1 2 → 1 の環状境界を越える。
(6) 循環ポインタを使わない復元
E E E では新規開始なら前行 H H H 、延長なら前行 E E E を記録する。B B B では空・文字対・E E E のどれかを記録する。V V V には値とともに「出発 B B B の位置 q q q 」と「進んだ長さ k k k 」を保存し、更新時に k k k を1増やす。同得点なら短い k k k を優先する。F F F を採用した場合はその情報からギャップ k + 1 k+1 k + 1 列を出力し、同じ行の B ( i , q ) B(i,q) B ( i , q ) へ一度に戻る。最良候補の周回は負なので循環ポインタは不要である。全行の情報は O ( m n ) O(mn) O ( mn ) 、復元は出力列数 ℓ \ell ℓ に対し O ( ℓ ) O(\ell ) O ( ℓ ) 。得点のみは O ( n ) O(n) O ( n ) 。
問題3 · 整列アルゴリズム(30点) ¶ 並列段数を制限した最適な隣接併合 ¶ k k k 本の連続区間 R 1 , … , R k R_{1},\ldots ,R_{k} R 1 , … , R k がそれぞれ非減少順に整列され、長さ r i ≥ 1 r_{i}\ge 1 r i ≥ 1 、N = ∑ r i N=\sum r_{i} N = ∑ r i が与えられる。操作は、現在隣接する二つの区間の安定併合だけであり、長さ a , b a,b a , b の費用を a + b a+b a + b と定める。さらに併合木の高さを整数 h ≥ 0 h\ge 0 h ≥ 0 以下に制限する。これは、一つの要素が参加する併合回数、または独立併合を同時に行う場合の併合段数の上限である。個々の併合そのものの並列深さは数えない。葉順は R 1 , … , R k R_{1},\ldots ,R_{k} R 1 , … , R k を保ち、高さ制約の下で総移動費用を最小化したい。実行可能な木がなければ ∞ \infty ∞ とする。
(1) 深さと隣接制約(5点) ¶ 葉 i i i の深さ d i d_{i} d i により総費用が ∑ r i d i \sum r_{i}d_{i} ∑ r i d i となることと、高さ制約がすべての d i ≤ h d_{i}\le h d i ≤ h であることを示せ。r = ( 1 , 100 , 1 ) , h = 2 r=(1,100,1),h=2 r = ( 1 , 100 , 1 ) , h = 2 で、隣接制約あり・なしの最小費用を比較せよ。
(2) 高さ制約付きの区間DP(7点) ¶ D ( i , j , h ) D(i,j,h) D ( i , j , h ) を R i , … , R j R_{i},\ldots ,R_{j} R i , … , R j を高さ h h h 以下で一つにする最小費用とする。h = 0 h=0 h = 0 と i = j i=j i = j の境界、最後の併合の分割による漸化式を導け。実現可能性が j − i + 1 ≤ 2 h j-i+1\le 2^h j − i + 1 ≤ 2 h と同値であることを証明せよ。
(3) 表の計算と木の復元(6点) ¶ 累積和を使い、高さごとの表 D D D と最適な分割を計算する擬似コードを書け。O ( k 3 h ) O(k^{3}h) O ( k 3 h ) 時間・O ( k 2 h ) O(k^{2}h) O ( k 2 h ) 空間の評価を示し、併合木の復元と実際の整列費用を区別せよ。h > k − 1 h>k-1 h > k − 1 の場合には表の高さを打ち切ってよい理由も述べよ。
(4) 高さと仕事量の具体例(5点) ¶ r = ( 1 , 1 , 1 , 10 ) r=(1,1,1,10) r = ( 1 , 1 , 1 , 10 ) について h = 2 h=2 h = 2 と h = 3 h=3 h = 3 の最適費用と併合木を求めよ。各高さで根の三つの分割を評価し、高さを1段増やすと仕事量を減らせることを確認せよ。
(5) エントロピーによる下界(7点) ¶ p i = r i / N p_{i}=r_{i}/N p i = r i / N 、H = ∑ p i l o g 2 ( 1 / p i ) H=\sum p_ilog_{2}(1/p_{i}) H = ∑ p i l o g 2 ( 1/ p i ) とする。葉深さの ∑ 2 − d i ≤ 1 \sum 2^{-d_{i}}\le 1 ∑ 2 − d i ≤ 1 から、実現可能な高さ制約付き木にも総費用≥ N H \ge NH ≥ N H が成り立つことを示せ。⌈ log 2 k ⌉ ≤ h \lceil \log_{2}k\rceil \le h ⌈ log 2 k ⌉ ≤ h のときの N ⌈ log 2 k ⌉ N\lceil \log_{2}k\rceil N ⌈ log 2 k ⌉ の上界と、実現不能な場合を比較せよ。
(1) 深さと隣接制約
要素は葉から根までの各併合で1回費用に寄与するので総費用は ∑ r i d i \sum r_{i}d_{i} ∑ r i d i 。高さは葉深さの最大なので d i ≤ h d_{i}\le h d i ≤ h が条件になる。( 1 , 100 , 1 ) (1,100,1) ( 1 , 100 , 1 ) の隣接併合は 101 + 102 = 203 101+102=203 101 + 102 = 203 。自由なら離れた長さ1を先に併合して 2 + 102 = 104 2+102=104 2 + 102 = 104 。両木とも高さ2だが、後者は葉順を保つ隣接併合として実行できない。高さ制約と隣接制約は独立に管理しなければならない。
(2) 高さ制約付きの区間DP
D ( i , i , h ) = 0 D(i,i,h)=0 D ( i , i , h ) = 0 (h ≥ 0 h\ge 0 h ≥ 0 )、D ( i , j , 0 ) = ∞ D(i,j,0)=\infty D ( i , j , 0 ) = ∞ (i < j i<j i < j )。h ≥ 1 , i < j h\ge 1,i<j h ≥ 1 , i < j なら
D ( i , j , h ) = W ( i , j ) + min i ≤ t < j { D ( i , t , h − 1 ) + D ( t + 1 , j , h − 1 ) } D(i,j,h)=W(i,j)+\min_{i\le t<j}\{D(i,t,h-1)+D(t+1,j,h-1)\} D ( i , j , h ) = W ( i , j ) + i ≤ t < j min { D ( i , t , h − 1 ) + D ( t + 1 , j , h − 1 )} 。根の直下で左右の高さ予算が1減るため、同じ h h h の表へ遷移してはならない。最後の併合が連続区間を二つに分けることから必要性、左右の最適手順を結合できることから十分性が得られる。高さ h h h の二分木は高々2 h 2^h 2 h 葉なので葉数条件は必要。葉数をほぼ均等に分割する木の高さは⌈ log 2 ( j − i + 1 ) ⌉ \lceil \log_{2}(j-i+1)\rceil ⌈ log 2 ( j − i + 1 )⌉ だから条件は十分でもある。
(3) 表の計算と木の復元
H m a x = min ( h , k − 1 ) Hmax=\min(h,k-1) H ma x = min ( h , k − 1 ) とし、W ( i , j ) W(i,j) W ( i , j ) を累積和で O ( 1 ) O(1) O ( 1 ) に得る。
全 D(i,j,0) を境界値で初期化
for z=1..Hmax:
D(i,i,z)=0
for i<j:
D(i,j,z)=∞
for t=i..j-1:
v=W(i,j)+D(i,t,z-1)+D(t+1,j,z-1)
最小 v と分割 t を保存
restore(i,j,z):
if i==j: return 葉i
t=split(i,j,z)
return node(restore(i,t,z-1),restore(t+1,j,z-1))計算 O ( k 3 ( H m a x + 1 ) ) O(k^{3}(Hmax+1)) O ( k 3 ( H ma x + 1 )) 、表 O ( k 2 ( H m a x + 1 ) ) O(k^{2}(Hmax+1)) O ( k 2 ( H ma x + 1 )) 。有限の答えの木復元は O ( k ) O(k) O ( k ) 、実際の安定併合は総費用 D ( 1 , k , H m a x ) D(1,k,Hmax) D ( 1 , k , H ma x ) に比例する。k k k 葉の1子頂点を持たない二分併合木の高さは最大k − 1 k-1 k − 1 なので、それより大きい制約は追加の木を許さない。h = 0 , k = 1 h=0,k=1 h = 0 , k = 1 の境界も処理できる。
(4) 高さと仕事量の具体例
W ( 1 , 4 ) = 13 W(1,4)=13 W ( 1 , 4 ) = 13 。高さ1の2葉費用は D ( 1 , 2 , 1 ) = 2 , D ( 2 , 3 , 1 ) = 2 , D ( 3 , 4 , 1 ) = 11 D(1,2,1)=2,D(2,3,1)=2,D(3,4,1)=11 D ( 1 , 2 , 1 ) = 2 , D ( 2 , 3 , 1 ) = 2 , D ( 3 , 4 , 1 ) = 11 、3葉以上は ∞ \infty ∞ 。h = 2 h=2 h = 2 の根候補は ( ∞ , 2 + 11 + 13 , ∞ ) = ( ∞ , 26 , ∞ ) (\infty ,2+11+13,\infty )=(\infty ,26,\infty ) ( ∞ , 2 + 11 + 13 , ∞ ) = ( ∞ , 26 , ∞ ) で、木 ( ( R 1 , R 2 ) , ( R 3 , R 4 ) ) ((R_{1},R_{2}),(R_{3},R_{4})) (( R 1 , R 2 ) , ( R 3 , R 4 )) が最適。高さ2の3葉費用は D ( 1 , 3 , 2 ) = 5 , D ( 2 , 4 , 2 ) = 14 D(1,3,2)=5,D(2,4,2)=14 D ( 1 , 3 , 2 ) = 5 , D ( 2 , 4 , 2 ) = 14 。h = 3 h=3 h = 3 の根候補は ( 0 + 14 + 13 , 2 + 11 + 13 , 5 + 0 + 13 ) = ( 27 , 26 , 18 ) (0+14+13,2+11+13,5+0+13)=(27,26,18) ( 0 + 14 + 13 , 2 + 11 + 13 , 5 + 0 + 13 ) = ( 27 , 26 , 18 ) 。最適は ( ( ( R 1 , R 2 ) , R 3 ) , R 4 ) (((R_{1},R_{2}),R_{3}),R_{4}) ((( R 1 , R 2 ) , R 3 ) , R 4 ) (または小さい三葉内の別同率木)で、費用2 + 3 + 13 = 18 2+3+13=18 2 + 3 + 13 = 18 。重い最終区間の深さを1にする代わりに、軽い区間の深さを増やす効果である。
(5) エントロピーによる下界
葉の経路語は相互に接頭語でなく、対応する二進区間は交わらないので ∑ 2 − d i ≤ 1 \sum 2^{-d_{i}}\le 1 ∑ 2 − d i ≤ 1 。q i = 2 − d i q_{i}=2^{-d_{i}} q i = 2 − d i とおき、対数の凹性により ∑ p i l o g 2 ( q i / p i ) ≤ log 2 ∑ q i ≤ 0 \sum p_ilog_{2}(q_{i}/p_{i})\le \log_{2}\sum q_{i}\le 0 ∑ p i l o g 2 ( q i / p i ) ≤ log 2 ∑ q i ≤ 0 。したがって H ≤ ∑ p i d i H\le \sum p_id_{i} H ≤ ∑ p i d i 、総費用≥ N H \ge NH ≥ N H 。高さ制約で候補木を減らしても下界は変わらず有効。h ≥ ⌈ log 2 k ⌉ h\ge \lceil \log_{2}k\rceil h ≥ ⌈ log 2 k ⌉ なら均等葉数の合法木で費用≤ N ⌈ log 2 k ⌉ \le N\lceil \log_{2}k\rceil ≤ N ⌈ log 2 k ⌉ 。それより小さい h h h なら k > 2 h k>2^h k > 2 h で実現不能となり、有限の上界を述べてはならない。