第14回 幅と制約を状態にする
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 200分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
幅2のグラフで求める最小カット¶
2行 列の階梯グラフを考える。列の頂点は 、縦辺 の重みは 。横辺 の重みはそれぞれ 。、、 とする。頂点を側0と側1に分け、を0、を1へ置く。異なる側を結ぶ辺の重み和をカット値と呼ぶ。最小 カットを、汎用の最大流アルゴリズムを使わず、左から列を処理して求めたい。
(1) 頂点分割と分離辺集合(5点)¶
異なる側を結ぶ辺を削除すれば が分離することを示せ。逆に任意の 分離辺集合から、それ以下の重みを持つ頂点分割のカットが得られることを証明せよ。
(2) 列の状態と遷移(6点)¶
第 列の側を とし、最初の 列内の辺だけを数える最適値 を定義する。 の初期値、列間の遷移式、最終解の式を示せ。
(3) 四状態の具体例(6点)¶
、縦辺の重みが 、上横辺が 、下横辺が の場合、各列の四状態の値を表にせよ。最小カット値と削除する辺を一つの解として求めよ。
(4) 状態の十分性と復元(7点)¶
各列の側だけを保持すれば十分であることを、未処理部分への接続に注目して証明せよ。擬似コード、時間、最小値だけの場合の空間、カットの復元に必要な空間と時間を示せ。
(5) 一状態だけ残す貪欲法(5点)¶
「各列で、それまでの最小値を持つ一状態だけ残す」という貪欲法が誤ることを、(3)の数値を用いて示せ。将来の辺の費用が捨てた状態を有利にする仕組みを説明せよ。
(6) 幅wへの拡張(6点)¶
各列に 個の頂点があり、辺は同じ列内または隣接する列の間にのみ存在するグラフへ拡張せよ。各列対に高々 辺があるとして、状態数・遷移数・単純な実装の時間計算量を示せ。
参考解答・採点の観点 — 問題1
(1) 頂点分割と分離辺集合
側から側へ進む道は必ず側が変わる辺を通るため、カット辺の削除で分離する。任意の分離集合 を削除した後、から到達できる頂点集合を とする。であり、と補集合を結ぶ元の辺は全てに含まれる。重みが正なので の重みは 以下。従って頂点分割による最小値と辺削除による最小値は一致する。
(2) 列の状態と遷移
()、なら。では
。角括弧は条件が真なら1、偽なら0。最終値は 。既処理列内の縦辺と横辺はこの式でちょうど1回ずつ加えられる。
(3) 四状態の具体例
| 列 | 00 | 01 | 10 | 11 |
|---|---|---|---|---|
| 1 | 0 | 4 | ||
| 2 | 0 | 3 | 4 | 5 |
| 3 | 0 | 7 | 8 | 5 |
第3列の は側1なので答えは 。第1列を00、第2・3列を11とする。カット辺は と 、重み。
(4) 状態の十分性と復元
未処理部分につながる既処理頂点は現在の列だけである。同じ現在列の側を持つ二つの部分解は、将来に付け加える辺の費用が同じなので、安い方だけ残せる。
D = 第1列の四状態
for i = 2..n:
四つの新状態それぞれについて四つの旧状態を試す
最小値と、それを与える旧状態を保存
return 最終列でa側=1の最小値各列16候補なので時間 、値だけなら空間 。復元用の旧状態は四状態列で 、逆向きに 列をたどり全辺を走査してカットを列挙する時間も 。
(5) 一状態だけ残す貪欲法
第2列で最小値だけ残すと00の値0を選ぶ。そこから最終列10へは上横辺5と縦辺4で値9、11へは上5と下3で値8、従って最終結果8。正しい解は第2列11の値5を残し、第3列も11にして追加0、合計5。第2列で支払った切断費用が、その後の大きな横辺の切断を避ける。
(6) 幅wへの拡張
列の各頂点の側を ビットで表すので状態数。旧状態と新状態の組は通り。各組について列内と列間の高々 辺の費用を直接数えると、時間 、値の配列は 。復元情報は 。指定された端点の側と矛盾する状態をにする。同じ幅を固定した範囲では に線形だが、には指数的である。
問題2 · 動的計画法(35点)¶
長すぎるギャップを禁止する局所アラインメント¶
文字列 の長さを とし、任意の連続部分文字列間で局所アラインメントを行う。空のアラインメントはスコア0。文字対応のスコアは 、同じ側に連続する長さ の最大ギャップ区間は 、。ただし各最大ギャップ区間の長さは 以下でなければならない。。両側ギャップの列は禁止し、異なる側のギャップが隣接することは許す。状態は消費済み接頭辞の長さ で終わるものとし、局所的な開始位置は任意とする。
(1) 末尾状態と境界(5点)¶
最後が文字同士の対応である状態 、の文字対のギャップである 、のギャップ対の文字である 、および を定義する。境界を定め、 の漸化式と全体の答えを示せ。
(2) 長さ上限付きのギャップ(7点)¶
を新しく始める直前の状態は であってはならない。、 を用い、最終ギャップ長 を明示した の式を導け。 から同じ側のギャップを「開き直す」式では、長さ上限を破る理由を説明せよ。
(3) 単調両端キュー(6点)¶
の式を の形に変形し、 の有効範囲を示せ。 についても同様に変形し、各最大値を単調両端キューで更新する方法を説明せよ。
(4) 行列の処理と補助空間(6点)¶
行を上から下へ、各行を左から右へ処理する擬似コードを書け。各列の縦キューと現行の横キューを区別し、全体 時間となる理由と、値だけを求める補助空間の上界を述べよ。
(5) ギャップ長の具体例(6点)¶
、、一致スコア4、不一致-6、 とする。 の 表を作り最適値を求めよ。 ではより良いアラインメントが得られることを、具体的な列とスコアで示せ。
(6) 最適アラインメントの復元(5点)¶
最適アラインメントを復元するため、各状態に保存する情報を述べよ。ギャップの先頭位置と直前の状態を使う復元手順を示し、記憶量・復元時間を評価せよ。
参考解答・採点の観点 — 問題2
(1) 末尾状態と境界
境界 。文字対応が不可能な境界の は。、。一方 (正の添字)は局所的に1文字のギャップだけを開始できるため としてよいが、では0に負ける。内部では 。答えは全 の の最大値であり、全て非正なら空の0。
(2) 長さ上限付きのギャップ
、。
、
。境界 。最終区間の前に同じ側のギャップを認めると、実際には一つの長い最大区間を複数回の開区間に分け、各部分長だけを以下として通せてしまう。はこれを除外し、反対側のギャップからの開始は合法として残す。
(3) 単調両端キュー
。は を固定して、。キューには位置と候補値を格納し、値が非増加となるよう末尾から劣る候補を除く。有効範囲を外れた先頭を除き、先頭の値が最大。各候補は一度入り一度出るので、総更新は線形。復元用には最大候補の位置も保持する。
(4) 行列の処理と補助空間
各列の縦キューを で初期化する。
for i=1..m:
横キューを B(i,0)=0 で初期化
for j=1..n:
M = 前行H[j-1] + S(L[i],R[j])
縦キューの範囲外を除き E を計算
横キューの範囲外を除き F を計算
H = max(0,M,E,F)
A=max(0,M,F) を列jの縦キューへ追加
B=max(0,M,E) を横キューへ追加各候補は定数回操作されるので 。縦キューは各列高々 要素、横は高々 。前行・現行も含め、空間 。上限付きでは一般に縦キューが必要で、単純な 空間のアフィンギャップの漸化式とは異なる。
(5) ギャップ長の具体例
の表は次の通り。
| 0 | 0 | 0 | 0 |
| 0 | 4 | 2 | |
| 0 | 2 | 0 | |
| 0 | 0 | 0 | |
| 0 | 0 | 4 |
最適値は4で、同士または同士だけを合わせる。なら 、 が合法で、一致2回の8から長さ2区間の費用3を引き、5を得る。表の最大値も5。長さ2を二つの長さ1区間として扱うことは、両者が同じ側で連続するので認められない。
(6) 最適アラインメントの復元
では最大を与える終端状態と、0で打ち切ることを保存する。は前の対角へ進む。では最大候補の位置 、ギャップ長、直前の または の実状態(、)を保存する。逆にギャップ列を必要数出力してその直前へ跳ぶ。各遷移は少なくとも1文字を消費するため終わる。状態・前情報の保存は 、出力列数 に対する復元は 、。
問題3 · 整列アルゴリズム(30点)¶
整列済みの鎖が与える情報¶
相異なるキーを持つ 個のレコードが、 本の整列済み配列(鎖)に分かれている。鎖 の長さは 、。各鎖内の順序だけが既知で、鎖間の大小関係は未知である。全体を併合する際の比較回数とレコード移動回数を区別して考える。後半では2本の鎖に絞り、短い鎖の中央値で長い鎖を分割する方法を考える。比較回数を鎖の長さの不均等さに適応させたい。
(1) 併合順序の数(5点)¶
各鎖の内部順序を保つ全体の順序の数が となることを証明せよ。同じ長さの鎖も、鎖番号によって区別するものとする。
(2) 情報量による下界(6点)¶
比較決定木による最悪比較回数の下界を、(1)の式で表せ。 の均等な場合に となることを述べ、 も別に扱え。
(3) 一本だけ短い場合(6点)¶
、長さが と1のとき、下界とそれを達成する比較回数の方法を示せ。その場合にも出力を別配列へ作る移動時間は となることを説明せよ。
(4) 短い鎖の中央値による併合(7点)¶
2本の鎖の長さをとしとする。の中央要素をピボットとし、現在の区間で順位を二分探索して左右を再帰的に併合する方法を書け。再帰中もの役割は交換しない。ピボットと左右の出力区間、および空列の処理を明記せよ。
(5) 不均等な鎖への適応(6点)¶
(4)の比較回数が となり、情報量下界に一致することを示せ。各深さの区間の長さの和と対数の凹性を使え。 の各要素の出力位置も求め、移動回数を評価せよ。
参考解答・採点の観点 — 問題3
(1) 併合順序の数
全体の並びの各位置に、そのレコードの鎖番号を書く。鎖は 回現れる。この番号列を指定すれば、各鎖のレコードは内部順に埋まるので全体順序が一意に定まる。逆に全ての順序からこの番号列が得られる。番号を 個ずつ持つ多重集合の順列数は である。
(2) 情報量による下界
相異なるキーの比較は二分岐なので、高さ には高々葉。従って 。均等長の場合、ほぼ二等分した鎖集合を繰り返し分割して数えるか階乗評価を用いると、 で が得られる。 では既に整列しており、可能性は1、追加比較は0である。
(3) 一本だけ短い場合
可能性は 、下界は。単独のキーの挿入位置を長い鎖で二分探索すれば 比較で確定する。位置が分かった後に別配列へ全レコードを出力するには 回の書き込みが必要で、移動時間は 。したがって のヒープ併合は、この極端に不均等な場合の比較回数には最適とはいえない。
(4) 短い鎖の中央値による併合
の中央添字、ピボットを選び、内の未満の個数を二分探索する。出力区間の先頭がbaseならの位置は。左問題はとを先頭区間へ、右問題はとをの次の区間へ出力する。常に元の側の中央を使う。片側が空なら残りをその出力区間へコピーする。キーが相異なるのでピボットの全体順位が一意に決まり、左右も順序関係が分離するため、帰納法で正しく併合できる。コピー・ピボット書き込みの出力区間は重ならない。
(5) 不均等な鎖への適応
深さの問題数は高々、区間長の和は以下。対数の凹性から、その深さの探索費用は 。はほぼ半分ずつ減るので深さは。底側からを数え直して幾何級数を足すと となる。一方、併合順数は二項係数 。積表示から 、また であり、よりその対数は 。従って比較回数は最悪オーダーで最適。例の要素の0始まり位置は、出力は 。全レコードを一度ずつ書くため移動はで、総実行時間にはこの項も必要。