第11回 変化に耐えるアルゴリズム
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 200分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
単一辺の変更と最小全域木¶
連結な単純無向グラフ の各辺には正の重みがあり、すべての重みは相異なる。最小全域木を とする。1回の問い合わせでは、1本の辺 の重みだけを新しい正の値 に変更する。変更後も全辺の重みは相異なるものとする。問い合わせ同士は独立であり、毎回元の から開始する。隣接リストを利用し、重みの比較・加算は定数時間で行える。以下では、変更された重みで評価した最小全域木を求めたい。
(1) 非木辺の減少(4点)¶
の重みを減少させる場合を考える。 上の の両端点を結ぶ道と、そこに含まれる最大重みの辺 を用いて、 を変更する必要がある条件と、変更後の木を述べよ。
(2) 交換の正しさ(7点)¶
(1)の判定と辺交換が正しいことを証明せよ。単に「閉路性質より」と述べるだけでなく、任意の競合する全域木から、同じ重み以下の候補木を作れることを説明せよ。
(3) 木辺の増加と他の変更(6点)¶
の重みを増加させる場合を考える。 の二つの連結成分を結ぶ辺の集合から、代替辺を選ぶ方法を示せ。また、 の減少と の増加で が変わらない理由も述べよ。
(4) 独立問い合わせの具体例(7点)¶
頂点を 、辺と重みを とする。元の と総重みを求めよ。次に、辺25を1に減少させる場合と、辺34を9に増加させる場合の新しい最小全域木を、それぞれ独立に求めよ。
(5) 線形時間の処理(6点)¶
前処理を行わず、どの種類の単一辺変更にも 時間で答えるアルゴリズムを書け。木上の道の探索、削除後の成分の識別、代替辺の走査を区別し、補助空間も示せ。
(6) 祖先表と最大辺(5点)¶
の減少だけが繰り返し問い合わせられるとする。根付き木の祖先を2のべき乗だけたどる表と、対応する道の最大辺を保持する表を設計せよ。前処理、記憶量、1問い合わせの計算量を示せ。
参考解答・採点の観点 — 問題1
(1) 非木辺の減少
に を加えると閉路が一つできる。その閉路から を除けば元の 、 を除けば となる。新しい重み が より小さいときは 、それ以外は を採用する。重みが相異なるという仮定により等号は生じない。
(2) 交換の正しさ
変更後の任意の全域木 を考える。 なら重みが変化した辺を含まないので、元の最適性から である。 なら は二つの成分に分かれる。 上の両端点間の道には、その成分間を横切る辺 がある。 は元のグラフの全域木なので、その元の重みは 以上である。従って変更後の 。 と の小さい方がこの下界を達成する。
(3) 木辺の増加と他の変更
が定めるカットを横切る 以外の最小重み辺を とする。 がなければ は橋であり必ず残る。 があれば では 、 では を使う。 を含まない任意の木 にはこのカットの辺 があり、 は元の木なので 。 を含む木の変更後の重みは元の重みとの差が同一だから が最小。木辺の減少は の優位を強め、非木辺の増加は の重みを変えず競合木の重みを減らさない。
(4) 独立問い合わせの具体例
元の 、総重みは14。辺25の道は 、最大辺は34の5である。25を1にすると ′、総重み10。辺34を9にするとカットは と 。代替候補は25の8、15の10なので、′、総重み17となる。問い合わせを連続適用した結果ではない。
(5) 線形時間の処理
非木辺の減少では木をDFSして両端点の道を復元し、その最大辺と を比較する。木辺の増加では木からその辺を除いて一方の成分をDFSで印付けし、元の全辺を走査して印の異なる端点を持つ辺の最小値を探す。他の二場合は元の木を返す。DFSは 、全辺走査は 。親・訪問印・探索スタックの補助空間は 。木自体を入力と別に構築するなら 辺の格納も必要である。
(6) 祖先表と最大辺
を の 代上の祖先、 をその区間の最大重み辺とする。 は親と親辺で初期化し、上位の表は二つの半区間から作る。問い合わせでは深さを合わせ、両頂点を同時に上げて最小共通祖先までの最大辺を集める。 の前処理と記憶量は 、1問い合わせは 。返す交換辺の番号も mx に保存する。独立問い合わせなので表は更新しない。
問題2 · 動的計画法(35点)¶
帯領域を通る編集列¶
文字列 と を考える。挿入と削除の費用は各1、異なる文字への置換は3、同じ文字の対応は0である。編集列を、格子上の から への道として表す。削除、挿入、対応はそれぞれ の移動に対応する。本問では、道のすべての頂点が を満たすという制約を課す。 は非負整数であり、制約を満たす道が存在しない場合の最適費用を とする。
(1) 状態と帯領域の境界(5点)¶
を帯領域内の から までの最小費用とする。境界条件と漸化式を示せ。帯領域の外の値をどのように扱うべきかも明記せよ。
(2) 編集列の具体例(6点)¶
、、 の の表を、帯領域外を として完成させよ。最小費用と、それを達成する編集列を一つ示せ。
(3) 正しさと制約なしとの比較(6点)¶
漸化式の正しさを最後の移動による場合分けで証明せよ。また、帯制約付きの値が制約なしの編集距離の下界・上界のどちらになるか述べ、厳しい不等号になる例を作れ。
(4) 帯内の計算と空間(6点)¶
帯領域にある格子点だけを列挙する擬似コードを書け。その格子点数を とした時間計算量を示し、費用のみを求める場合に隣接2行だけを保持してよい理由と必要空間を説明せよ。
(5) 復元と終点の判定(6点)¶
最適な編集列を復元する方法を示せ。複数の最適な前状態がある場合の規則を一つ定め、記憶量と復元時間を示せ。さらに の場合を計算前に判定できる理由を述べよ。
(6) 閾値判定の帯幅(6点)¶
制約なしの最小費用が整数 以下かだけを判定したいとする。帯幅を として計算してよいことを証明せよ。計算量を で評価し、 の場合にも適用できる式を示せ。
参考解答・採点の観点 — 問題2
(1) 状態と帯領域の境界
、帯領域外と負添字は 。帯領域内では 、。 に対し
、 は文字が等しければ0、異なれば3。境界をこの漸化式で計算しても同じ値を得る。
(2) 編集列の具体例
| の接頭辞長 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | ||
| 1 | 1 | 0 | 1 | |
| 2 | 1 | 2 | 3 | |
| 3 | 1 | 2 | ||
| 4 | 1 |
最適費用は1。を対応させ、を削除し、を対応させる道 が達成する。
(3) 正しさと制約なしとの比較
最適道の最後は三種類の移動のいずれかであり、直前までの道が最適でなければ置換して改善できる。逆に各候補の最適道に最後の移動を足せば実現可能な道になるので、最小値は一致する。帯制約は候補を減らすため値は制約なしの距離の上界。例として では2回の置換が必要で費用6だが、制約なしではを削除し末尾にを挿入して費用2にできる。
(4) 帯内の計算と空間
各行 で を から まで昇順に処理する。行外の参照は にする。
for i = 0..m:
current を ∞ で初期化
for j = max(0,i-b)..min(n,i+b):
境界または三候補の最小値で current[j] を計算
previous = current1点あたり定数時間なので 。前行と現行以外を参照しないため、空間は 。行ごとに配列の添字オフセットを保持する。空行が生じる入力は事前に棄却できる。
(5) 復元と終点の判定
各点で選んだ移動を保存する。等費用では対応、削除、挿入の順に選ぶ等の固定規則でよい。終点から保存した移動の逆向きに進み、得た操作を反転する。各移動は を1以上減らすので復元は 、前状態の記憶は 。終点自体が帯の外なら道は存在しないので なら直ちに を返す。
(6) 閾値判定の帯幅
費用 以下の道では挿入・削除の合計回数が 以下である。どの途中点でも は、それまでの挿入・削除の回数以下だから を超えない。従って費用 以下の道は必ず帯幅 に入る。帯内の最小費用が 以下なら制約なしでも可、その逆も上の議論から成立する。時間は 、対称に向きを選べば 。粗い表現では 、空間 。 なら対角だけを走査する。
問題3 · 整列アルゴリズム(30点)¶
キーの種類数に適応する安定整列¶
個のレコードがあり、各レコードは比較可能なキーと付随データを持つ。同じキーのレコードは元の入力順に出力する必要がある。入力に現れる相異なるキーの数を とするが、 は事前には与えられない。比較・レコードの移動は定数時間とし、入力は読み取り専用、出力用配列は別に確保できる。本問では、 が よりはるかに小さい場合の整列を考える。ハッシュの平均計算量には頼らず、最悪計算量を保証せよ。
(1) 平衡木と待ち行列(5点)¶
平衡二分探索木の各節点に同じキーのレコードの待ち行列を持たせる。入力を順に登録し、木を中順走査して出力する方法の正しさ、安定性、最悪時間と補助空間を示せ。
(2) 安定な中央値分割(6点)¶
別の方法として、長さ の列から中央値を 時間で選択できると仮定する。中央値のキーより小さい・等しい・大きいの三群へ安定に分割し、外側二群だけを再帰的に整列する方法を書け。安定性を証明せよ。
(3) キー頻度と時間計算量(6点)¶
(2)の時間が となることを証明せよ。各キーの出現回数を とし、そのキーが処理される深さを と関連付けて評価せよ。
(4) 比較回数の下界(7点)¶
、 とし、各キーがちょうど 回現れる入力を考える。キーの配置の可能性の数を数え、三通りの比較結果を持つ決定木から の最悪比較回数の下界を導け。
(5) 計数整列との比較(6点)¶
キーが整数 の場合の安定な計数整列を示し、上の比較法と比較せよ。さらに入力 の安定な出力を求め、 ならどの方式を選ぶか根拠を述べよ。
参考解答・採点の観点 — 問題3
(1) 平衡木と待ち行列
各レコードをキーの節点へ検索し、初出なら節点を挿入、既出ならその節点の列の末尾へ加える。平衡木の検索・挿入は 。中順走査はキー昇順であり、節点内は登録順なので安定。時間 、節点とレコード参照の待ち行列に の補助空間を使う。出力領域はこの評価に含めない。
(2) 安定な中央値分割
中央値のキー を選び、入力を左から走査して の三つの列の末尾に追加する。 を順に連結する。空列またはキーが1種類なら直ちにその列を返す。各群への追加は元の順序を保ち、同じキーは同じ群に入り続ける。帰納法により再帰結果も安定であり、群間ではキーが厳密に異なるため連結しても安定性を損なわない。
(3) キー頻度と時間計算量
中央値を取るので両外側群の長さは元の長さの高々半分である。キー を含む群には 個以上の要素があるため、そのキーが選ばれるまでの分割回数は高々 。各節点の選択・分割費用 をその 個の要素に分配すると、総費用は 。 として より 。分割領域を処理後に解放し、深さ優先で再帰すれば補助空間 で実装できる。
(4) 比較回数の下界
配置数は 。各入力レコードの付随データを識別可能にすると、異なるキー配置は異なる必要出力の並べ替えを要求する。高さ の三分岐決定木には高々葉しかないので 。これが であることは階乗の評価から従う。例えば が偶数ならキーを二等分し、それぞれの部分を再帰的に二等分することで、各段の二群への配置数の積として を表せる。各ほぼ二等分の二項係数は、その部分の長さに比例する対数を持ち、 段で となる。奇数 も床・天井の二分で同じ評価となる。
(5) 計数整列との比較
各キーの個数を数え、累積個数から出力区間を決める。入力を左から走査して各キーの次の出力位置を進めれば安定に出力できる。時間 、補助空間 (出力配列を除く)。具体例の出力は 。提示された大きな では計数配列の初期化と記憶が重く、平衡木または安定中央値分割を選ぶ。比較法は 程度で に適応し、 個の領域を要しない。