第12回 全解の構造と選択
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 200分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
すべての経路が通る辺¶
有向非巡回グラフ と、相異なる頂点 が与えられ、 から への有向道が少なくとも一つ存在する。辺の重複はない。すべての 道が通る頂点を必経頂点、すべての 道が使う辺を必経辺という。道の本数を数える際には、整数を厳密に保持するものとし、当初は任意精度整数の加算・乗算を1操作と数える。最後の小問ではビット計算量を別に評価する。
(1) 道数の漸化式(5点)¶
から までの道の本数を 、 から までの道の本数を とする。トポロジカル順序を用いる二つの漸化式と初期値を示し、到達不能な頂点の扱いを説明せよ。
(2) 辺の通過道数(5点)¶
辺 を使う 道の本数が となることを証明せよ。DAG であることが、前半と後半の道を連結する際にどこで必要になるかも述べよ。
(3) 必経辺と必経頂点(7点)¶
必経辺と必経頂点を道の本数の式で判定する方法を示せ。 とし、 の仮定を使って必要十分性を証明せよ。 を必経頂点に含めるかも明記せよ。
(4) 道数の具体例(6点)¶
頂点は 、辺は とする。全頂点の を表にし、必経頂点・必経辺をすべて求めよ。
(5) 最短道への限定(7点)¶
各辺に非負の長さが与えられた場合、すべての最短 道が通る辺を求めたい。 からの距離と までの距離を使って対象辺だけを残す方法を示し、その部分グラフで本問の計数法を適用できることを証明せよ。
(6) ビット計算量と辺削除法(5点)¶
道数のビット長の最大を とする。加算 、通常の整数乗算 としたビット計算量を示せ。さらに大整数を使わず、辺を1本ずつ削除して必経性を判定する方法と比較せよ。
参考解答・採点の観点 — 問題1
(1) 道数の漸化式
とし、他頂点を0で初期化する。トポロジカル順に各辺 で 。、他は0として逆トポロジカル順に 。 に入る辺や から出る辺があっても、DAGなのでそれらが初期値を増やす有効な道を作ることはない。到達不能な側の本数は0のままである。
(2) 辺の通過道数
の道と の道を任意に選び、間に を置く。もし両道が共通頂点 を持てば という有向閉路ができる。DAGではこれは不可能なので連結結果は道である。逆に を使う道は の直前・直後で一意に分解できる。従って組の数 と道数は一致する。
(3) 必経辺と必経頂点
辺 は のとき、かつそのときに限り必経辺。頂点 は のとき、かつそのときに限り必経頂点。同じ連結・一意分解の議論で、それぞれを含む道数が得られる。これらは全 道の部分集合を数えているので、本数が正の全道数 と一致することは全部を含むことと同値。 も必経頂点に含める。
(4) 道数の具体例
| 頂点 | |||
|---|---|---|---|
| 1 | 4 | 4 | |
| 1 | 2 | 2 | |
| 1 | 2 | 2 | |
| 2 | 1 | 2 | |
| 2 | 1 | 2 | |
| 4 | 1 | 4 | |
| 4 | 1 | 4 |
。必経頂点は 、必経辺は のみ。他の辺の通過道数は1または2なので4にはならない。
(5) 最短道への限定
距離 をDAGの動的計画法で求め、 とする。有限距離を持ち、 を満たす辺のみ残す。最短道の各辺はこの条件を満たす。逆に残した辺には が成立する。実際 と を併用すれば等号になる。従って残した 道では距離の差が望遠和となり、総長が となる。部分グラフもDAGなので計数法を適用できる。
(6) ビット計算量と辺削除法
トポロジカル整列は 。道数の加算には 、各辺・頂点の積の判定に を要し、全体は 。整数格納は ビット。辺削除法では ごとに から への到達性を探索し、到達不能なら必経辺とする。時間 、補助空間 。有限個の法による剰余だけの一致では、大きな道数の一致を一般には保証できない。
問題2 · 動的計画法(35点)¶
個数を指定した重み付き区間選択¶
個の半開区間 ) に重み が付いている。 であり、重みは負でもよい。互いに重ならない区間をちょうど 個選び、重みの和を最大化したい。 とする。区間は終了時刻の非減少順に並べ、同じ終了時刻では入力番号順とする。 は、 より前の区間のうち を満たす最大の番号であり、そのような区間がなければ0とする。実現不能な状態の値は とする。
(1) 適合する接頭辞の探索(5点)¶
を各区間について求める方法を書け。終了時刻の整列と二分探索を含めた計算量を示せ。半開区間であることが適合条件の等号にどう関係するかも説明せよ。
(2) 状態と漸化式(6点)¶
を先頭 区間からちょうど 個選ぶ最適値とする。境界と漸化式を定め、最後の区間 を選ぶ場合・選ばない場合に分けて正しさを証明せよ。
(3) 具体例と最適集合(7点)¶
区間と重みを順に とする。 の列、および 、 の 表を作れ。ちょうど2個・ちょうど3個の最適な集合をそれぞれ求めよ。
(4) 復元と個数制約(6点)¶
最適集合を復元する手順と必要な情報を示せ。また「高々 個」の問題に変更したときの答えを で表せ。負の重みがあるため、ちょうど と高々 が異なる例も作れ。
(5) 個数順の計算と空間削減(6点)¶
時間 の計算を擬似コードで示せ。最適値だけなら を外側のループにすることで 空間に削減できることを説明し、 を外側として単純に2行だけ保持する方法が不適切な理由も述べよ。
(6) 密なDAGとの比較(5点)¶
各区間を頂点とし、適合する に辺 を置くDAGによっても問題を表せる。個数を状態に加えた最長道の計算を説明し、全辺を明示すると遅くなり得る理由と による改善の意味を述べよ。
参考解答・採点の観点 — 問題2
(1) 適合する接頭辞の探索
終了時刻を で整列する。 ごとに配列 を二分探索して 以下の最後の位置を求めれば全体 。終了時刻の整列後は比較条件が単調である。半開区間は右端 を含まないため、 なら重ならず同時に選択できる。
(2) 状態と漸化式
、、負の添字 も 。 では 。 を選ばない解は先頭 の解。 を選ぶ解の残りは、終了時刻が 以下の先頭 に限られる。どちらも最適な部分解を使ってよく、逆に二候補から実現可能な解を構成できるので一致する。
(3) 具体例と最適集合
。
| 0 | 0 | |||
| 1 | 0 | 5 | ||
| 2 | 0 | 6 | ||
| 3 | 0 | 6 | 9 | |
| 4 | 0 | 7 | 13 | |
| 5 | 0 | 8 | 14 | 17 |
2個では 、値。3個では 、値17となる。
(4) 復元と個数制約
各状態で「を選ぶ/選ばない」を保存する。選ばないなら 、選ぶなら を出力して 。 は減り続けるので復元時間 、表と選択情報は 。高々 の答えは 。例えば区間が一つ、重み -5、 なら、ちょうど1個は -5、高々1個は空集合の0である。
(5) 個数順の計算と空間削減
個数ごとに長さ の配列を保持する。
prev[j] = 0 for j=0..n # r=0
for r = 1..q:
cur[0] = -∞
for j = 1..n:
cur[j] = max(cur[j-1], w[j]+prev[p[j]])
prev = cur
return prev[n]時間 、最適値だけなら空間 。 は直ちに0を返す。 の行を単純に捨てると、 が より大幅に小さい場合の が失われるため、方向の2行保持では足りない。
(6) 密なDAGとの比較
各頂点 の終端状態 を「で終わる 個の列の最大重み」として、、 とする。全頂点の最大値が答え。辺数は になり得るため を要する。 は適合する全頂点の終端最適値の最大を接頭辞の状態一つにまとめており、明示的な密グラフを作らず で計算できる。
問題3 · 整列アルゴリズム(30点)¶
必要な先頭だけを整列する¶
個のレコードから、キーが小さい順の先頭 個だけを昇順に出力したい。 とする。同じキーでは入力順を保つため、各レコードに元の位置 を付け、組 (キー,) を辞書式に比較する。これにより比較対象は全順序で相異なる。比較・移動は定数時間とする。全 個を整列する方法より、 が小さいときに有利な最悪計算量保証を目指す。
(1) 線形時間の選択法(6点)¶
5個ずつの群の中央値から再帰的に中央値を選ぶ選択法を記述せよ。選んだピボットで分割した際、少なくとも 個を片側から除外できる理由と、線形時間となる漸化式を示せ。
(2) 中央値と分割の具体例(5点)¶
キーの列を5個ずつ に分ける。各群の中央値、中央値の中央値、最初の分割結果を求めよ。第6小要素を求める際に次に探索する群も示せ。
(3) 選択後の部分整列(7点)¶
線形時間選択を利用し、先頭 個だけを安定に整列するアルゴリズムを書け。選択、抽出、残った要素の整列を区別し、最悪時間 と補助空間の上界を示せ。
(4) 比較回数の下界(6点)¶
キーがすべて異なる入力に制限しても、問題に必要な最悪比較回数が となることを証明せよ。最小値を必ず出力することと、個の未知の順序を区別することをそれぞれ使え。
(5) 最大ヒープとの比較(6点)¶
大きさ の最大ヒープを用いて先頭候補を保持する方法を示し、全整列・(3)の方法と比較せよ。、が小さい定数、 の各場合の時間の違いも説明せよ。
参考解答・採点の観点 — 問題3
(1) 線形時間の選択法
群の中央値は各5個を定数時間で整列して求める。群数 とし、その中央値を再帰的に選択する。ピボット以上・以下の中央値はそれぞれほぼ 個あり、完全な群では中央値の同じ側に3個ある。端の不完全群とピボット群を除いても各側に少なくとも 個残る。従って選択の再帰は 。十分大きい で再帰部分の係数和が1より小さいため、帰納法で が得られる。小さい入力は直接整列する。
(2) 中央値と分割の具体例
群の中央値は、ピボットは11。小群は入力順で 、等群は 、大群は 。小群の長さが7なので11は第8小要素。第6小要素は小群の第6小要素として再帰する。最終的な第6小キーは8である。
(3) 選択後の部分整列
組の第 小要素 を で選択し、入力を走査して 以下の組を抽出する。組が相異なるため抽出数はちょうど 。抽出したレコードを安定な併合整列で整列して出力する。抽出列を元の入力順に作り、キーと位置の全順序で出力するので、同キーは入力順となる。時間 。選択用作業配列 と抽出・併合領域 により、補助空間 で実装できる。
(4) 比較回数の下界
先頭 個のうち最初は全入力の最小値だから、その確定には最悪 比較が必要である。一方、残り 個を既知の大きな値に固定して、最小側 個の値の順序を任意にすると 通りの出力順序を区別する必要があり、決定木の高さは 。二つの下界の最大は和の半分以上なので 。 の対数項は定数であり と整合する。
(5) 最大ヒープとの比較
先頭 個で最大ヒープを作り、後続レコードが根より小さければ根と交換して下向き修復する。最後に保持した 個を組の順に整列する。時間 、空間 。全整列は 、選択後の部分整列は 。 と定数 ではヒープ法も選択法も 。 では両者とも 。中間の では選択法が 回の走査に対数を掛けない点で有利、ヒープ法は保持領域が小さく逐次入力にも適する。