第20回 総合設計:故障・予算・適応性の証明 グラフ理論・動的計画法・整列アルゴリズム
← 备考目录
問題 分野 テーマ 配点 問題1 グラフ理論 全単一辺故障に対する最短路の証明書 35点 問題2 動的計画法 予算を守りながら最悪区間を最小化する 35点 問題3 整列アルゴリズム 区間構造と重複構造のよい方を使う安定整列 30点
問題1 · グラフ理論(35点) ¶ 全単一辺故障に対する最短路の証明書 ¶ 連結単純無向グラフ G G G の辺重みはすべて厳密に正である。異なる s , t s,t s , t に対し、各辺 e e e を1本削除したグラフでの s − t s-t s − t 最短距離 D e D_{e} D e をすべて求めたい。到達不能なら ∞ \infty ∞ とする。元の最短パス P = ( p 0 = s , p 1 , … , p k = t ) P=(p_{0}=s,p_{1},\ldots ,p_{k}=t) P = ( p 0 = s , p 1 , … , p k = t ) 、その長さ D D D 、全頂点への距離 d s , d t d_{s},d_{t} d s , d t を考える。P P P を含む s s s 根の最短路木 T s T_{s} T s と、逆向きの P P P を含む t t t 根の最短路木 T t T_{t} T t を選ぶ。頂点 u u u の T s T_{s} T s 上の最も近い P P P 祖先を p a ( u ) p_{a(u)} p a ( u ) 、T t T_{t} T t 上の最も近い P P P 祖先を p b ( u ) p_{b(u)} p b ( u ) とする。未知の高度なアルゴリズムを引用せず、区間への最小値更新から設計せよ。
(1) 非パス辺の故障と最短路木(5点) ¶ e ∉ P e\notin P e ∈ / P なら D e = D D_{e}=D D e = D であることを示せ。各 P P P 辺について最短路を再計算する素朴な方法の時間を評価せよ。また、T s , T t T_{s},T_{t} T s , T t がそれぞれ P P P を含むように親を選べる理由と、正の重みを仮定する意義を説明せよ。
(2) 二つの木のラベル(6点) ¶ L j = d s ( p j ) L_{j}=d_{s}(p_{j}) L j = d s ( p j ) とする。u u u までの両最短路木の P P P 外部分の長さを使い、a ( u ) ≤ b ( u ) a(u)\le b(u) a ( u ) ≤ b ( u ) を証明せよ。両木は別々なので「同じ部品に属するはず」と説明するだけでは十分でない。
(3) 故障辺を避ける歩道(7点) ¶ 非 P P P 辺 { u , v } \{u,v\} { u , v } を向き u → v u\to v u → v で考え、z = d s ( u ) + w ( u , v ) + d t ( v ) z=d_{s}(u)+w(u,v)+d_{t}(v) z = d s ( u ) + w ( u , v ) + d t ( v ) とする。故障 e i = { p i − 1 , p i } e_{i}=\{p_{i-1},p_{i}\} e i = { p i − 1 , p i } に対し a ( u ) < i ≤ b ( v ) a(u)<i\le b(v) a ( u ) < i ≤ b ( v ) なら、z z z の長さの s − t s-t s − t 歩道が e i e_{i} e i を避けることを示せ。閉路が含まれても距離の上界に使える理由を述べよ。
(4) 最適回避パスと区間候補(8点) ¶ 各非 P P P 辺を両方向に考えると、D e i D_{ei} D e i が「i i i を区間 [ a ( u ) + 1 , b ( v ) ] [a(u)+1,b(v)] [ a ( u ) + 1 , b ( v )] に含む候補 z z z の最小値」に等しいことを証明せよ。下からの不等式だけでなく、任意の最適な故障回避パス上で候補を見つけること。P P P の辺を候補に入れない理由も示せ。
(5) 区間木と全体の計算量(5点) ¶ 長さ k k k の配列を ∞ \infty ∞ で初期化する。各候補の区間に z z z との最小値更新を行う処理を、二分された区間木の各節点への最小タグとして O ( log ( k + 1 ) ) O(\log(k+1)) O ( log ( k + 1 )) 時間で行う方法を説明せよ。距離計算・木のラベル・最終展開を含む全擬似コードと計算量を示せ。
(6) 全故障距離の具体例(4点) ¶ P = s − a − b − t P=s-a-b-t P = s − a − b − t の辺重みは順に1 , 2 , 1 1,2,1 1 , 2 , 1 。非 P P P 辺は s − x : 2 , x − b : 2 , a − y : 3 , y − t : 2 , x − y : 2 s-x:2,x-b:2,a-y:3,y-t:2,x-y:2 s − x : 2 , x − b : 2 , a − y : 3 , y − t : 2 , x − y : 2 。T s T_{s} T s では y y y の P P P 祖先を a a a 、T t T_{t} T t では x x x の P P P 祖先を b b b と選ぶ。a ( x ) , b ( x ) , a ( y ) , b ( y ) a(x),b(x),a(y),b(y) a ( x ) , b ( x ) , a ( y ) , b ( y ) と P P P の3辺の故障距離を求めよ。
(1) 非パス辺の故障と最短路木
P P P がそのまま残るため D e ≤ D D_{e}\le D D e ≤ D 。辺の削除で元より短いパスは生まれないので D e ≥ D D_{e}\ge D D e ≥ D 。P P P 上の k k k 辺について二分ヒープ版 Dijkstra を行えば O ( k ( n + m ) log n ) O(k(n+m)\log n) O ( k ( n + m ) log n ) 時間で、最初の元距離計算を加えても同じオーダー。最短パスの各接頭辞・接尾辞も最短なので、T s T_{s} T s では p j p_{j} p j の親を p j − 1 p_{j-1} p j − 1 、T t T_{t} T t では p j p_{j} p j の親を p j + 1 p_{j+1} p j + 1 と固定できる。他頂点は距離を達成する親を選ぶ。正の重みで親の距離が厳密に減るため循環せず、木になる。P P P の L j L_{j} L j も厳密に増える。
(2) 二つの木のラベル
a = a ( u ) , b = b ( u ) a=a(u),b=b(u) a = a ( u ) , b = b ( u ) 、T s T_{s} T s の p a → u p_{a}\to u p a → u の長さを A A A 、T t T_{t} T t の p b → u p_{b}\to u p b → u の長さを B B B とする。d s ( u ) = L a + A d_{s}(u)=L_{a}+A d s ( u ) = L a + A 、d t ( u ) = D − L b + B d_{t}(u)=D-L_{b}+B d t ( u ) = D − L b + B 。T t T_{t} T t の後半を s s s から P P P 経由で使う別経路と比較すると L a + A ≤ L b + B L_{a}+A\le L_{b}+B L a + A ≤ L b + B 。逆に T s T_{s} T s の後半を t t t 側から使うと D − L b + B ≤ D − L a + A D-L_{b}+B\le D-L_{a}+A D − L b + B ≤ D − L a + A 。合わせて L a − L b ≤ B − A L_{a}-L_{b}\le B-A L a − L b ≤ B − A と L a − L b ≤ A − B L_{a}-L_{b}\le A-B L a − L b ≤ A − B 、したがって 2 ( L a − L b ) ≤ 0 2(L_{a}-L_{b})\le 0 2 ( L a − L b ) ≤ 0 。L L L が厳密増加なので a ≤ b a\le b a ≤ b 。無向性によって木の後半を逆向きに使えることも必要である。
(3) 故障辺を避ける歩道
T s T_{s} T s の s → u s\to u s → u は P P P の p 0 → p a p_{0}\to p_{a} p 0 → p a の後に P P P 外の枝へ進むため、a < i a<i a < i なら e i e_{i} e i を含まない。T t T_{t} T t の v → t v\to t v → t は P P P 外の枝から p b → p k p_{b}\to p_{k} p b → p k へ進むため、b ≥ i b\ge i b ≥ i なら e i e_{i} e i を含まない。真ん中の辺は非 P P P なので故障辺でもない。三部分を連結した歩道の長さは z z z 。重複頂点を持つ場合は閉路を取り除けば e i e_{i} e i を使わない単純パスとなり、正の重みで長さが増えない。よって D e i ≤ z D_{ei}\le z D e i ≤ z 。
(4) 最適回避パスと区間候補
各候補は実現可能な歩道なので min z ≥ D e i \min z\ge D_{ei} min z ≥ D e i 。有限の最適回避パス Q Q Q を考え、集合 S i = { u : a ( u ) < i } S_{i}=\{u:a(u)<i\} S i = { u : a ( u ) < i } から初めて出る辺 u → v u\to v u → v を選ぶ。s s s は S i S_{i} S i 内、t t t は外だからその辺がある。a ( u ) < i a(u)<i a ( u ) < i 、a ( v ) ≥ i a(v)\ge i a ( v ) ≥ i かつ(2)より b ( v ) ≥ a ( v ) ≥ i b(v)\ge a(v)\ge i b ( v ) ≥ a ( v ) ≥ i なので区間候補となる。この辺が P P P の辺なら S i S_{i} S i の境界を渡る P P P 辺は e i e_{i} e i 自体だけであり、Q Q Q は使えないため非 P P P 辺である。元の最短距離は Q Q Q の対応する前半・後半長以下なので z ≤ length ( Q ) = D e i z\le \operatorname{length}(Q)=D_{ei} z ≤ length ( Q ) = D e i 。両不等式から一致。Q Q Q がなければ有限候補も実現可能性から存在しない。P P P 辺を入れると e i e_{i} e i 自身が元の長さD D D を候補にしてしまい、故障を避けた証明書にならない。
(5) 区間木と全体の計算量
区間木の節点は [ 1 , k ] [1,k] [ 1 , k ] の連続区間を二分する。更新対象を互いに素な O ( log ( k + 1 ) ) O(\log(k+1)) O ( log ( k + 1 )) 個の節点区間に分け、各節点の tag を min ( t a g , z ) \min(tag,z) min ( t a g , z ) とするだけでよい。最後に根から子へ最小タグを伝播し、各葉 i i i の値を読む。
dₛ,Tₛ,P と dₜ,Tₜ を Dijkstra で作り、P の親を固定
両木の DFS で、P 頂点の番号を枝へ引き継ぎ a,b を求める
全タグを ∞ にする
for 非 P 辺 {u,v}:
for (r,h) in [(u,v),(v,u)]:
if a(r)+1<=b(h):
rangeMin(a(r)+1,b(h),dₛ(r)+w(r,h)+dₜ(h))
葉値を展開し P 辺の答えにする
その他の辺の答えは DO ( ( n + m ) log n + m log ( k + 1 ) + n + k ) = O ( ( n + m ) log n ) O((n+m)\log n+m \log(k+1)+n+k)=O((n+m)\log n) O (( n + m ) log n + m log ( k + 1 ) + n + k ) = O (( n + m ) log n ) 時間、隣接リスト・両木・区間木を含め O ( n + m ) O(n+m) O ( n + m ) 空間。候補辺番号もタグと一緒に保存すれば修復歩道の証明書となる。
(6) 全故障距離の具体例
d s ( x ) = 2 , d t ( x ) = 3 d_{s}(x)=2,d_{t}(x)=3 d s ( x ) = 2 , d t ( x ) = 3 、d s ( y ) = 4 , d t ( y ) = 2 d_{s}(y)=4,d_{t}(y)=2 d s ( y ) = 4 , d t ( y ) = 2 。ラベルは a ( x ) = 0 , b ( x ) = 2 , a ( y ) = 1 , b ( y ) = 3 a(x)=0,b(x)=2,a(y)=1,b(y)=3 a ( x ) = 0 , b ( x ) = 2 , a ( y ) = 1 , b ( y ) = 3 。s − x s-x s − x と x − b x-b x − b の前向き候補はいずれも5で区間 [ 1 , 2 ] [1,2] [ 1 , 2 ] 、a − y a-y a − y と y − t y-t y − t は6で [ 2 , 3 ] [2,3] [ 2 , 3 ] 、x − y x-y x − y は6で [ 1 , 3 ] [1,3] [ 1 , 3 ] 。したがって故障距離は順に ( 5 , 5 , 6 ) (5,5,6) ( 5 , 5 , 6 ) 。前二つの回避パスは s − x − b − t s-x-b-t s − x − b − t 、最後は s − a − y − t s-a-y-t s − a − y − t 。非 P P P 辺の故障距離は元の4。
問題2 · 動的計画法(35点) ¶ 予算を守りながら最悪区間を最小化する ¶ 長さ n n n の列を、空でない連続区間 K K K 個(1 ≤ K ≤ n 1\le K\le n 1 ≤ K ≤ n )に分割する。区間 [ i , j ] [i,j] [ i , j ] の費用 c ( i , j ) c(i,j) c ( i , j ) と悪さ d ( i , j ) d(i,j) d ( i , j ) は非負整数で、全 O ( n 2 ) O(n^{2}) O ( n 2 ) 個の値が表で与えられる。予算B B B は非負整数とし、費用和はB B B 以下とする。区間の悪さの最大値を最小化したい。同じ最大値なら費用和が小さい分割を選ぶ。c , d c,d c , d の長さに関する単調性や加法性は仮定しない。最大値という非加法的な目的と、費用和という制約を混同せず、状態を増やす方法と判定問題へ変える方法の両方から考えよ。実現可能な分割がなければ不可能と答える。
(1) 予算軸の完全DP(5点) ¶ D ( i , k , b ) D(i,k,b) D ( i , k , b ) を先頭 i i i 要素を k k k 区間へ分割し、費用和がちょうど b b b のときの最小の悪さの最大値とする。境界値と最後の区間を用いた漸化式を導け。空の分割の最大値を0とすること。
(2) 状態の競合と支配(6点) ¶ 同じ ( i , k ) (i,k) ( i , k ) について「悪さの最大値が最小の状態」だけを残すと失敗する理由を、費用・悪さの組で示せ。予算を使う後続区間との組合せも考え、二つの状態の正しい支配関係を定義せよ。
(3) 閾値ごとの最小費用(6点) ¶ 閾値 λ \lambda λ を固定して悪さ d ( i , j ) ≤ λ d(i,j)\le \lambda d ( i , j ) ≤ λ の区間だけを許す。C λ ( i , k ) C_{\lambda}(i,k) C λ ( i , k ) をその条件での最小費用とし、予算を状態に持たない漸化式を導け。C λ ( n , K ) ≤ B C_{\lambda}(n,K)\le B C λ ( n , K ) ≤ B の真偽が λ \lambda λ に対して単調になることを証明せよ。
(4) 二分探索と復元(7点) ¶ 最適な λ \lambda λ が区間悪さ表のいずれかの値であることを示せ。異なる値の整列と二分探索によって解く擬似コード、時間・空間・復元方法を示せ。予算 B B B が非常に大きい場合、(1)より有利となる理由を述べよ。
(5) 重み和では選べない解(6点) ¶ n = 4 , K = 2 n=4,K=2 n = 4 , K = 2 の各切断位置 t = 1 , 2 , 3 t=1,2,3 t = 1 , 2 , 3 に対し、二つの区間の費用和と悪さ最大が順に ( 1 , 9 ) , ( 5 , 6 ) , ( 6 , 1 ) (1,9),(5,6),(6,1) ( 1 , 9 ) , ( 5 , 6 ) , ( 6 , 1 ) になる入力を構成せよ。B = 5 B=5 B = 5 の答えを求め、費用+ α × +\alpha \times + α × 悪さ(α ≥ 0 \alpha \ge 0 α ≥ 0 )だけの最小化ではこの答えを得られないことを証明せよ。
(6) 二方法と最小費用の保証(5点) ¶ (1)の完全 DP と(4)の判定法を比較せよ。最適な最大値に加えて最小費用の分割を返すために、二分探索終了後の最後の DP で何を保存すべきかを説明せよ。区間の悪さが一般整数でも同じ方法が使えるか。
(1) 予算軸の完全DP
D ( 0 , 0 , 0 ) = 0 D(0,0,0)=0 D ( 0 , 0 , 0 ) = 0 、それ以外の不可能状態は ∞ \infty ∞ 。i , k ≥ 1 i,k\ge 1 i , k ≥ 1 なら
D ( i , k , b ) = min k − 1 ≤ h < i , c ( h + 1 , i ) ≤ b max { D ( h , k − 1 , b − c ( h + 1 , i ) ) , d ( h + 1 , i ) } D(i,k,b)=\min_{k-1\le h<i,c(h+1,i)\le b} \max\{D(h,k-1,b-c(h+1,i)),d(h+1,i)\} D ( i , k , b ) = k − 1 ≤ h < i , c ( h + 1 , i ) ≤ b min max { D ( h , k − 1 , b − c ( h + 1 , i )) , d ( h + 1 , i )} 。h h h を選ぶことで最後の区間を [ h + 1 , i ] [h+1,i] [ h + 1 , i ] に固定する。非負の悪さだから空の最大値0は最初の区間の値に影響しない。答えは b ≤ B b\le B b ≤ B の D ( n , K , b ) D(n,K,b) D ( n , K , b ) の最小で、同率なら最小 b b b を選ぶ。計算 O ( K n 2 ( B + 1 ) ) O(Kn^{2}(B+1)) O ( K n 2 ( B + 1 )) 、表 O ( K n ( B + 1 ) ) O(Kn(B+1)) O ( K n ( B + 1 )) 。
(2) 状態の競合と支配
状態 (費用5,悪さ6) と (費用6,悪さ1) では後者の悪さが小さいが、予算が5なら後者は使えない。後続区間に費用2が必要で全予算7でも前者だけが使える。目的の悪さが小さいだけでは前者を捨てられない。同じ ( i , k ) (i,k) ( i , k ) で ( c , d ) (c,d) ( c , d ) が (c c c ′,d d d ′) を支配する条件は c ≤ c c\le c c ≤ c ′,d ≤ d d\le d d ≤ d ′。後続区間を同じように追加しても費用は少なく、max による悪さは大きくならないため、最適値と最小費用について後者を削除できる。
(3) 閾値ごとの最小費用
C λ ( 0 , 0 ) = 0 C_{\lambda}(0,0)=0 C λ ( 0 , 0 ) = 0 、不可能状態は ∞ \infty ∞ 。
C λ ( i , k ) = min k − 1 ≤ h < i , d ( h + 1 , i ) ≤ λ { C λ ( h , k − 1 ) + c ( h + 1 , i ) } C_{\lambda}(i,k)=\min_{k-1\le h<i,d(h+1,i)\le \lambda }\{C_{\lambda}(h,k-1)+c(h+1,i)\} C λ ( i , k ) = k − 1 ≤ h < i , d ( h + 1 , i ) ≤ λ min { C λ ( h , k − 1 ) + c ( h + 1 , i )} 。1回 O ( K n 2 ) O(Kn^{2}) O ( K n 2 ) 時間、表 O ( K n ) O(Kn) O ( K n ) 。λ \lambda λ が増えると許される区間が増えるだけなので最小費用は非増加。したがって予算内であるという判定は偽から真へ変化するのみ。この DP には予算の数字の大きさは状態数として入らない。
(4) 二分探索と復元
有限の分割の最大値は、その分割の区間のどれかの d d d に等しいので、候補は表の異なる値だけでよい。
values=sorted(unique(d(i,j)))
if feasibility(values[-1]) が偽: return 不可能
二分探索で Cλ(n,K)<=B となる最初の λ* を探す
λ* で C と、各状態の最良の最後の切断 h を再計算
(n,K) から h をたどって K 区間を出力候補数 O ( n 2 ) O(n^{2}) O ( n 2 ) 、整列 O ( n 2 log ( n + 1 ) ) O(n^{2} \log(n+1)) O ( n 2 log ( n + 1 )) 、各判定 O ( K n 2 ) O(Kn^{2}) O ( K n 2 ) 、回数 O ( log ( n + 1 ) ) O(\log(n+1)) O ( log ( n + 1 )) 。合計 O ( K n 2 log ( n + 1 ) ) O(Kn^{2} \log(n+1)) O ( K n 2 log ( n + 1 )) (log ( n + 1 ) \log(n+1) log ( n + 1 ) を使えば n = 1 n=1 n = 1 も含む)、表と入力 O ( K n + n 2 ) O(Kn+n^{2}) O ( K n + n 2 ) 空間、復元 O ( K ) O(K) O ( K ) 。B B B のビット長に対して、(1)の B B B 個の状態を持つ方法は擬多項式だが、この方法は B B B を比較するだけなのでその依存を避ける。
(5) 重み和では選べない解
c ( 1 , 1 ) = c ( 1 , 2 ) = c ( 1 , 3 ) = 0 c(1,1)=c(1,2)=c(1,3)=0 c ( 1 , 1 ) = c ( 1 , 2 ) = c ( 1 , 3 ) = 0 、c ( 2 , 4 ) = 1 , c ( 3 , 4 ) = 5 , c ( 4 , 4 ) = 6 c(2,4)=1,c(3,4)=5,c(4,4)=6 c ( 2 , 4 ) = 1 , c ( 3 , 4 ) = 5 , c ( 4 , 4 ) = 6 。d ( 1 , 1 ) = d ( 1 , 2 ) = d ( 1 , 3 ) = 0 d(1,1)=d(1,2)=d(1,3)=0 d ( 1 , 1 ) = d ( 1 , 2 ) = d ( 1 , 3 ) = 0 、d ( 2 , 4 ) = 9 , d ( 3 , 4 ) = 6 , d ( 4 , 4 ) = 1 d(2,4)=9,d(3,4)=6,d(4,4)=1 d ( 2 , 4 ) = 9 , d ( 3 , 4 ) = 6 , d ( 4 , 4 ) = 1 。残りの表値は任意の非負値でよい。K = 2 K=2 K = 2 では三つの切断だけなので指定された点が得られる。B = 5 B=5 B = 5 の答えは切断2、悪さ6、費用5。これを重み和で最小にするには 5 + 6 α ≤ 1 + 9 α 5+6\alpha \le 1+9\alpha 5 + 6 α ≤ 1 + 9 α から α ≥ 4 / 3 \alpha \ge 4/3 α ≥ 4/3 、同時に 5 + 6 α ≤ 6 + α 5+6\alpha \le 6+\alpha 5 + 6 α ≤ 6 + α から α ≤ 1 / 5 \alpha \le 1/5 α ≤ 1/5 が必要で、両立しない。予算制約の最適な点が、重み和では選べない場合がある。
(6) 二方法と最小費用の保証
予算 DP は全費用ごとに最良最大値を持つため、目的・制約の競合を直接保存するが O ( K n 2 ( B + 1 ) ) O(Kn^{2}(B+1)) O ( K n 2 ( B + 1 )) 。閾値法は目的の最大値を固定し、加法的費用だけを最適化するため B B B に比例した表を不要にする。最後の λ ∗ \lambda * λ ∗ で C λ C_{\lambda} C λ を最小化し、その最小候補 h h h を保存すれば、最適最大値の下で最小費用も自動的に実現する。悪さが負も含む一般整数なら空最大値を − ∞ -\infty − ∞ に変えれば、閾値法はそのまま使える。費用の非負条件を変えても有限区間数 K K K の DP 自体は可能だが、予算軸 DP の0 … B 0\ldots B 0 … B という範囲は別途見直す必要がある。
問題3 · 整列アルゴリズム(30点) ¶ 区間構造と重複構造のよい方を使う安定整列 ¶ N ≥ 2 N\ge 2 N ≥ 2 個のレコードにはキーと元の位置がある。相異なるキーの個数を d d d 、昇順のキー群の出現数を f 1 , … , f d f_{1},\ldots ,f_d f 1 , … , f d とし、H k e y = ∑ ( f i / N ) log 2 ( N / f i ) H_{\mathrm{key}}=\sum (f_{i}/N)\log_{2}(N/f_{i}) H key = ∑ ( f i / N ) log 2 ( N / f i ) とする。別に、非減少区間と厳密な減少区間を左から最大まで取り出し、減少区間だけを反転して得る k k k 区間の長さを r i r_{i} r i 、H r u n = ∑ ( r i / N ) log 2 ( N / r i ) H_{\mathrm{run}}=\sum (r_{i}/N)\log_{2}(N/r_{i}) H run = ∑ ( r i / N ) log 2 ( N / r i ) とする。正しい安定整列と、期待時間 O ( N ( 1 + min ( H k e y , H r u n ) ) ) O(N(1+\min(H_{\mathrm{key}},H_{\mathrm{run}}))) O ( N ( 1 + min ( H key , H run ))) の両立を目指す。キーは比較だけで扱い、入力の値は乱数を引く前に固定される。作業配列 O ( N ) O(N) O ( N ) は使用してよい。 最後の改良では、サイズ s s s のキー列の正確な中央値を O ( s ) O(s) O ( s ) 時間で求める決定的な選択手続きを使えるものとする。元レコードを並べ替えず、キーの作業コピーで選択してよい。
(1) 安定三分割と比較確率(5点) ¶ 一様に選んだレコードをピボットとし、ピボット自身以外の全レコードを小・同・大へ順序を保って分け、小・大だけを再帰整列する。安定性を証明せよ。異なるキー群 i < j i<j i < j の特定2レコードが比較される確率を、F i j = ∑ h = i j f h F_{ij}=\sum _{h=i}^j f_h F ij = ∑ h = i j f h を用いて求めよ。
(2) 期待時間とキー頻度(6点) ¶ (1)から期待比較数が N − d + 2 ∑ i < j f i f j / F i j N-d+2\sum _{i<j}f_{i}f_{j}/F_{ij} N − d + 2 ∑ i < j f i f j / F ij となることを導け。x / ( a + x ) ≤ ln ( ( a + x ) / a ) x/(a+x)\le \ln((a+x)/a) x / ( a + x ) ≤ ln (( a + x ) / a ) を使い、これを N + 2 N ln 2 ⋅ H k e y N+2N \ln2\cdot H_{\mathrm{key}} N + 2 N ln 2 ⋅ H key 以下に抑え、分割・コピーの総期待時間も O ( N ( 1 + H k e y ) ) O(N(1+H_{\mathrm{key}})) O ( N ( 1 + H key )) と示せ。
(3) 区間長に適応する併合木(5点) ¶ 区間長 r i r_{i} r i に対する葉順を保つ併合木を構成し、費用 O ( N ( 1 + H r u n ) ) O(N(1+H_{\mathrm{run}})) O ( N ( 1 + H run )) を達成せよ。各区間の重み幅 r i / N r_{i}/N r i / N の中点を含む二進区間と、長さ ⌈ log 2 ( N / r i ) ⌉ + 1 \lceil \log_{2}(N/r_{i})\rceil +1 ⌈ log 2 ( N / r i )⌉ + 1 の接頭語を用いてよい。初期区間抽出と木構築も費用に含めること。
(4) 二方法の交互実行(4点) ¶ 「まず平衡探索木で d d d と頻度をすべて調べ、それから速い方を選ぶ」方法が目標を満たさない例を示せ。代わりに、入力の二つのコピーで(1)と(3)を1演算ずつ交互に進め、先に完成した出力を採用する方法の期待時間・安定性・空間を証明せよ。
(5) 頻度だけの情報量下界(4点) ¶ 頻度 f i f_{i} f i だけを約束し、入力の並びを任意とする場合の比較決定木の下界を示せ。その下界が Ω ( N ( 1 + H k e y ) ) \Omega (N(1+H_{\mathrm{key}})) Ω ( N ( 1 + H key )) となる総時間の評価と、Hrun が小さい特定入力への高速性が矛盾しないことを説明せよ。
(6) 期待保証と決定的な改良(6点) ¶ (4)のランダム実行の期待時間を最悪保証と読み替えられないことを、q ≥ 2 , N = q 2 q\ge 2,N=q^{2} q ≥ 2 , N = q 2 、0がN − q N-q N − q 個、1 , … , q 1,\ldots ,q 1 , … , q が各1個の区間分断入力で示せ。次に、与えられた正確な中央値選択を使い、各キー群の処理回数を評価して決定的 O ( N ( 1 + H k e y ) ) O(N(1+H_{\mathrm{key}})) O ( N ( 1 + H key )) を証明せよ。区間法との交互実行で最終的にどの保証を得るか。
(1) 安定三分割と比較確率
安定な3分割は各キー群内の到着順を保ち、同キーは同じ側に進む。ピボットと同キーの群をそこで確定し、小・大を帰納的に安定整列すれば全出力は安定。群 i , … , j i,\ldots ,j i , … , j の最初のピボットが、指定した2レコードのどちらかの場合だけ両者が直接比較される。内部キーのピボットは両群を分離し、同じ端点群の別レコードのピボットは指定端点レコードを同キー群に入れて再帰から除く。したがって確率2 / F i j 2/F_{ij} 2/ F ij 。同キー群の特定対の直接比較確率は2 / f i 2/f_{i} 2/ f i 。
(2) 期待時間とキー頻度
同群の対の期待比較総数は ∑ ( f i 2 ) ⋅ 2 / f i = ∑ ( f i − 1 ) = N − d \sum \binom{f_{i}}{2}\cdot 2/f_{i}=\sum (f_{i}-1)=N-d ∑ ( 2 f i ) ⋅ 2/ f i = ∑ ( f i − 1 ) = N − d 。異群は各群対に f i f j f_{i}f_{j} f i f j 個のレコード対があるので式を得る。固定 i i i について ∑ j > i f j / F i j ≤ ∑ j > i ln ( F i j / F i , j − 1 ) = ln ( F i , d / f i ) ≤ ln ( N / f i ) \sum _{j>i}f_{j}/F_{ij}\le \sum _{j>i}\ln(F_{ij}/F_{i},_{j-1})=\ln(F_{i},d/f_{i})\le \ln(N/f_{i}) ∑ j > i f j / F ij ≤ ∑ j > i ln ( F ij / F i , j − 1 ) = ln ( F i , d / f i ) ≤ ln ( N / f i ) 。よって交差項≤ 2 ∑ f i ln ( N / f i ) = 2 N ln 2 ⋅ H k e y \le 2\sum f_{i}\ln(N/f_{i})=2N \ln2\cdot H_{\mathrm{key}} ≤ 2 ∑ f i ln ( N / f i ) = 2 N ln 2 ⋅ H key 。サイズ s ≥ 2 s\ge 2 s ≥ 2 の分割の比較数 s − 1 s-1 s − 1 とコピー・走査 O ( s ) O(s) O ( s ) は定数倍の関係にあり、単独要素の出力を含め期待時間 O ( N ( 1 + H k e y ) ) O(N(1+H_{\mathrm{key}})) O ( N ( 1 + H key )) 。
(3) 区間長に適応する併合木
区間抽出と厳密な下降の反転は O ( N ) O(N) O ( N ) 、同キーの順序は壊さない。重み p i = r i / N p_{i}=r_{i}/N p i = r i / N の区間中点に対して幅 2 − ℓ i ≤ p i / 2 2^{-\ell _{i}}\le p_{i}/2 2 − ℓ i ≤ p i /2 の二進区間を取り、その語のトライの1子頂点を縮約する。葉順を保ち、深さ d i ≤ ℓ i < log 2 ( 1 / p i ) + 2 d_{i}\le \ell _{i}<\log_{2}(1/p_{i})+2 d i ≤ ℓ i < log 2 ( 1/ p i ) + 2 なので併合費用< N ( H r u n + 2 ) <N(H_{\mathrm{run}}+2) < N ( H run + 2 ) 。語構築は O ( k log N ) O(k \log N) O ( k log N ) で、N H r u n ≥ ( k − 1 ) log 2 N NH_{\mathrm{run}}\ge (k-1)\log_{2}N N H run ≥ ( k − 1 ) log 2 N より O ( N ( 1 + H r u n ) ) O(N(1+H_{\mathrm{run}})) O ( N ( 1 + H run )) に収まる。併合で同キーは左区間から取れば安定であり、語順の隣接共通接頭辞をスタックで管理して圧縮トライを直接作れば木も O ( k ) O(k) O ( k ) 空間で、作業配列を含め O ( N ) O(N) O ( N ) に収まる。
(4) 二方法の交互実行
すでに昇順で相異なる N N N キーなら H r u n = 0 H_{\mathrm{run}}=0 H run = 0 、望む時間は O ( N ) O(N) O ( N ) 。それでも平衡木で全キーを挿入する前処理は Θ ( N log N ) \Theta (N \log N) Θ ( N log N ) を要するので、後で区間法を選んでも遅い。交互実行なら、二つの単独所要演算数を T k e y , T r u n T_{\mathrm{key}},T_{\mathrm{run}} T key , T run として総演算≤ 2 m i n ( T k e y , T r u n ) + O ( N ) \le 2min(T_{\mathrm{key}},T_{\mathrm{run}})+O(N) ≤ 2 min ( T key , T run ) + O ( N ) 。Trun は決定的なので
E [ min ( T k e y , T r u n ) ] ≤ min ( E [ T k e y ] , T r u n ) E[\min(T_{\mathrm{key}},T_{\mathrm{run}})]\le \min(E[T_{\mathrm{key}}],T_{\mathrm{run}}) E [ min ( T key , T run )] ≤ min ( E [ T key ] , T run ) 。よって目標期待時間を得る。両出力が安定なため先に完成する方を採用してよく、コピー・作業配列は定数枚 O ( N ) O(N) O ( N ) 。頻度を事前に求める必要はない。
(5) 頻度だけの情報量下界
キー群の割当順は M = N ! / ∏ f i ! M=N!/\prod f_{i}! M = N ! / ∏ f i ! 通りで、安定出力は各群内の元位置順に固定される。等号もある3結果比較の決定木では、最悪比較数は log 3 M = ( ln 2 / ln 3 ) log 2 M \log_{3}M=(\ln2/\ln3)\log_{2}M log 3 M = ( ln 2/ ln 3 ) log 2 M 以上。階乗の評価から、これは ( ln 2 / ln 3 ) ( N H k e y − N l o g 2 e ) (\ln2/\ln3)(NH_{\mathrm{key}}-Nlog_{2}e) ( ln 2/ ln 3 ) ( N H key − Nl o g 2 e ) 以上となる。出力時間 Ω ( N ) \Omega (N) Ω ( N ) と合わせ、Hkey が定数の範囲とそれより大きい範囲を分ければ最悪総時間 Ω ( N ( 1 + H k e y ) ) \Omega (N(1+H_{\mathrm{key}})) Ω ( N ( 1 + H key )) 。これは頻度だけを約束した入力集合全体の最悪下界である。その集合中の整列済み入力は区間構造を検出して O ( N ) O(N) O ( N ) で処理でき、最悪下界とは矛盾しない。個別入力すべてに同じ下界を当てはめてはならない。
(6) 期待保証と決定的な改良
ランダム法だけでは期待値と最悪値は別である。N = q 2 N=q^{2} N = q 2 、0がN − q N-q N − q 個、1 , … , q 1,\ldots ,q 1 , … , q が各1個なら H k e y = O ( ( log q ) / q ) H_{\mathrm{key}}=O((\log q)/q) H key = O (( log q ) / q ) 、目標はΘ ( N ) \Theta (N) Θ ( N ) 。0をq q q 個のほぼ同じ区間に分け、間に単発キーを置くと H r u n = Θ ( log q ) H_{\mathrm{run}}=\Theta (\log q) H run = Θ ( log q ) 。単発キーを最大から次々ピボットにして最後まで0群を選ばない列は正の確率で起こり、ランダム側はΘ ( N q ) \Theta (Nq) Θ ( Nq ) 、区間側が先に終わってもΘ ( N log q ) \Theta (N \log q) Θ ( N log q ) となり得る。
修正は各部分列で正確な中央値を使うことである。選択手続きはキーの作業コピーへ適用し、元レコードの到着順を保って3分割する。中央値の小・大側はどちらも高々s / 2 s/2 s /2 なので、キー群i i i が残る部分列は深さh h h で高々N / 2 h N/2^h N / 2 h 。その部分列にはまだ群の全f i f_{i} f i 個があるため、処理される回数は高々1 + log 2 ( N / f i ) 1+\log_{2}(N/f_{i}) 1 + log 2 ( N / f i ) 。選択・安定分割・コピーはサイズに比例し、総時間は O ( ∑ f i ( 1 + log 2 ( N / f i ) ) ) = O ( N ( 1 + H k e y ) ) O(\sum f_{i}(1+\log_{2}(N/f_{i})))=O(N(1+H_{\mathrm{key}})) O ( ∑ f i ( 1 + log 2 ( N / f i ))) = O ( N ( 1 + H key )) 、決定的な最悪保証となる。O ( N ) O(N) O ( N ) キー作業配列を使い、スタックは O ( log N ) O(\log N) O ( log N ) 。
この決定的なキー法と区間法を交互実行すれば、先に完成する方までの費用は定数倍だから、安定性と O ( N ) O(N) O ( N ) 作業空間を保って、決定的最悪時間 O ( N ( 1 + min ( H k e y , H r u n ) ) ) O(N(1+\min(H_{\mathrm{key}},H_{\mathrm{run}}))) O ( N ( 1 + min ( H key , H run ))) を得る。中央値選択の線形保証は問題文で与えた前提であり、最初のランダム法の期待値から導いたわけではない。