第13回 制約・近似・記憶階層
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 200分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
必須辺と禁止辺を持つ最小全域木¶
連結な単純無向グラフ に非負の辺重みが与えられている。辺集合 の各辺は必ず採用し、辺集合 の各辺は採用してはならない。この条件を満たす全域木のうち、総重みが最小のものを求める。条件を満たす木が存在しない場合には、その理由を証明する情報も出力したい。 は の部分集合であり、両者が重なる入力も許す。集合の指定は辺番号の列で与えられる。
(1) 実現可能性の必要条件(4点)¶
実現可能性のために と、 が閉路を含まないことが必要な理由を示せ。これら二条件だけでは十分でない具体例も一つ与えよ。
(2) 必須森の縮約(6点)¶
が森であるとする。 の各連結成分を一つの頂点に縮約し、 の辺と縮約後の自己ループを除く。得られる多重グラフの連結性が、実現可能性の必要十分条件であることを証明せよ。
(3) 重みと全域木の対応(6点)¶
縮約による最適化が重みを保存することを示せ。元の条件付き全域木と縮約後の全域木の対応を述べ、平行辺を残してよい理由を説明せよ。
(4) 制約付きMSTの具体例(7点)¶
辺と重みを 、、 とする。縮約後の頂点・辺を示し、条件付き最小全域木とその総重みを求めよ。
(5) 集合管理とKruskal法(7点)¶
互いに素な集合を根付き木で表し、小さい集合の根を大きい集合の根へ結ぶ方法を用いる。縮約グラフを明示的に作らず、必須辺を先に併合して残りを重み順に処理する擬似コードを書け。木の深さの上界を証明し、正しさと最悪時間を述べよ。
(6) 実現不能の証明書(5点)¶
実現不能を証明する証拠を、、 に閉路がある、残ったグラフが非連結、の三場合について示せ。証拠を受け取った第三者が 時間で検証できることも説明せよ。
参考解答・採点の観点 — 問題1
(1) 実現可能性の必要条件
同じ辺を必須かつ禁止にすることは不可能。全域木は閉路を含まないので 内の閉路も不可能。この二条件だけでは、禁止辺を除くと非連結になる場合を排除できない。例えば道 で とすれば、交差も必須閉路もないが頂点3を接続できない。
(2) 必須森の縮約
条件付き木を縮約すると、全ての縮約頂点をつなぐため連結となる。逆に縮約後が連結なら、その全域木の元の辺を選び、 と合わせる。 は各成分内をつなぐ森であり、縮約木は成分間を閉路なくつなぐので、元の全頂点をつなぐ閉路のない木を得る。自己ループは同じ必須成分内の追加辺であり、 と閉路を作るので使えない。
(3) 重みと全域木の対応
の辺数は 、 は必須森の成分数。条件付き全域木は成分間の 辺を持ち、それらは縮約後の全域木となる。逆対応も (2) の通り。重みは固定値 と縮約木の重みの和だから、縮約木を最小化すればよい。平行辺は異なる元の辺を表すので残して構わず、閉路判定で二本同時の選択を防げる。平行辺間で最小重みだけ残す最適化も可能だが必須ではない。
(4) 制約付きMSTの具体例
縮約頂点は 。禁止13を除くと、には23の2と24の5、には45の3、には25の6と15の7が残る。縮約最小木は 、重み5。元の解は 、総重み。
(5) 集合管理とKruskal法
if F∩B が非空: その辺を証拠として終了
全頂点を単独集合にする
for e=(u,v) in F:
if find(u)==find(v): 閉路を復元して終了
union(u,v); 答えにeを加える
for e=(u,v) in E∖(F∪B), 重み昇順:
if find(u)!=find(v):
union(u,v); 答えにeを加える
if 全頂点が同一集合でない: 非連結のカットを出力
else: 答えを出力必須成分を初期頂点とする Kruskal 法そのものなので (3) とカット性質から最適。集合の小さい根を大きい根へ結ぶ。ある頂点の深さが1増えるごとに、その所属集合の大きさは少なくとも2倍になるため、深さは 。find は親をたどり、union は根とサイズを更新するので1操作も 。時間は初期化 、整列 、集合操作 の和。閉路証拠のため採用した必須森も保持する。
(6) 実現不能の証明書
交差の場合は該当する辺番号1個。閉路の場合はに含まれる相異なる辺からなる閉路の列。非連結の場合は空でない真部分集合 で、禁止されていない辺が と の間に存在しないというカットを出す。辺集合の所属を印付けし、閉路列の接続を確認するか、全辺を走査してカット条件を検査すれば 。カットは全頂点の集合所属ビットで表せる。
問題2 · 動的計画法(35点)¶
価値を丸めるナップサック近似¶
個の品物に正の整数重量 と非負整数価値 があり、容量 以下で価値和を最大化したい。は非負整数であり、各品物は高々1回選べる。 の品物を除いた後の個数を改めて とし、、 と仮定する。それ以外は空集合を返せばよい。誤差係数は有理数 。、丸め価値 とする。有理数の演算・整数の加算比較を1操作とするモデルで評価せよ。
(1) 丸め価値と状態(5点)¶
が 以下であることを示せ。価値を状態とし、各状態で必要な最小重量を保持する動的計画法を、境界条件を含めて定義せよ。
(2) 丸めた目的関数の最適化(6点)¶
丸め価値の和が最大になる実現可能な集合 を得るアルゴリズムを書け。元の価値の和が最大になる集合を直接探すのではないことを明確にし、時間計算量を示せ。
(3) 加法誤差の証明(6点)¶
任意の集合 について と、 を示せ。この不等式と丸めた問題の最適性を用い、 を証明せよ。
(4) 相対保証と計算モデル(7点)¶
前処理後には が成立する理由を説明し、 を導け。実行時間が入力価値の大きさでなく と の多項式になることの意味も述べよ。
(5) 近似解の具体例(6点)¶
品物を 、、 とする。、 の列、丸め問題で選ばれる集合と元の価値を求め、厳密な最適集合・最適値と比較せよ。
(6) 一次元更新と復元(5点)¶
最小重量だけなら価値方向の1次元配列で更新できる。更新を降順にする理由を説明し、 の扱いも述べよ。選択集合を確実に復元するための記憶方法と、その空間・復元時間を示せ。
参考解答・採点の観点 — 問題2
(1) 丸め価値と状態
各 より 、従って 。 を先頭 品物だけで丸め価値の和をちょうど にする最小重量とする。、、負の は 。。重量が を超える状態を に置換しても構わない。
(2) 丸めた目的関数の最適化
、 の順に表を埋める。 を求め、その状態から品物を復元する。最適化する目的は丸め価値 であり、元の価値がわずかに低い集合が選ばれる場合がある。時間 。整数値が非常に大きくても、状態数 は で抑えられる。
(3) 加法誤差の証明
床関数より 。 を掛けて和を取れば二不等式が得られる。元の最適集合を とする。 は丸め問題で最適かつ も実現可能なので 。従って 。
(4) 相対保証と計算モデル
前処理後の各品物は単独で容量内に入り、最大価値の品物一つも実現可能なので 。従って 、。この近似方式は精度を で指定し、その逆数と品物数の多項式時間で相対保証を得る。演算1操作モデルの評価であり、実際のビット計算では重量・価値・ の符号長に依存する演算費用も加わる。
(5) 近似解の具体例
、。容量内で最大丸め価値は11で、品物1と4を選ぶ。重量7、元の価値21。一方、厳密な最適は品物2と3、重量7、価値22、丸め価値10である。単独品物は最大15、他の可能な二品物は価値などであり、三品物は最小重量9で実現不能。実際の比率は保証より良い。
(6) 一次元更新と復元
正の では を から まで降順に更新する。参照 は当該品物の更新前なので同じ品物を再利用しない。昇順だと複数回使用する誤りを起こす。 の品物は正重量を増やすだけで丸め価値を改善しないので捨ててよい。最適値だけなら空間 。確実な復元には二次元表か各 の採否を で保存し、を1ずつ減らして採用時に をだけ減らす。復元時間 、出力は高々品物。
問題3 · 整列アルゴリズム(30点)¶
ブロック転送を減らす多路併合¶
個のレコードを外部記憶で安定に整列する。1ブロックは 個のレコードを持ち、1回のブロック読み書きを と数える。内部にはデータ用バッファ 個分を置け、 とする。管理用 語も利用でき、全内部記憶は 。比較・移動の内部計算時間と I/O を区別せよ。各レコードには元の入力位置を付けられる。まず連続する高々 個ずつを内部で整列し、外部の整列済みランとして保存する。
(1) 初期ランとI/O(6点)¶
初期ランの数と生成時の I/O・内部比較回数を示せ。ランはブロック境界に保存し、最後のブロックは未使用部分を含んでもよい。 の場合も含めて式を示せ。
(2) バッファと多路併合(6点)¶
本のランを一度に併合する方法を、入力バッファ・出力バッファ・最小ヒープに分けて説明せよ。バッファが空または満杯になったときの処理と安定性も示せ。
(3) 併合段数と端数ブロック(7点)¶
とする。すべてのランを 本ずつ併合する段数を求め、整列全体の I/O の上界を で示せ。ラン末尾の不完全ブロックが追加する費用も無視せず評価せよ。
(4) I/Oの具体例(6点)¶
、、 とする。初期ラン数、、併合段数、全体の I/O を求めよ。この例では全ラン長が の倍数である。2本ずつの併合を繰り返す方式の I/O と比較せよ。
(5) 内部比較回数(5点)¶
多路併合の1段と全体の内部比較回数を評価せよ。比較回数のオーダーが通常の比較整列と変わらなくても、 を増やすことが外部記憶上で有利になる理由を説明せよ。
参考解答・採点の観点 — 問題3
(1) 初期ランとI/O
初期ラン数は 。各レコードを読み、その整列済みランを書き出すので、I/O は 。内部比較は 。 ならランは1本、内部で一度整列して出力する。入力・出力が別領域にあるため読み書きの両方を数える。
(2) バッファと多路併合
各入力ランに1ブロック、出力に1ブロックを確保する。各ランの現在の先頭レコードをヒープに置き、最小を出力バッファへ移す。入力バッファが尽きれば次ブロックを読む。ラン自体が尽きればヒープから除去する。出力バッファが満ちれば1ブロックを書き、最後の残りも書く。組 (キー,元の位置) を比較すれば同キーは入力順。 個のブロックが 内に収まり、ヒープの 語は管理領域を使う。
(3) 併合段数と端数ブロック
なら0段、一般に 段。各段は全レコードを高々定数回読み書きし、ランごとの端数ブロックに 段 が増える。各段のラン数は初期以下で なので、1段 。初期生成も含め 。 は別にとし、本問はを対象とする。
(4) I/Oの具体例
、、併合は2段。初期生成は256ブロックの読みと256ブロックの書きで。第1段は15ランの併合と残り1ランで合計(残りランもその段でコピーする実装)、第2段も、計1536。残り1ランをコピーせず参照だけ引き継ぐ実装なら第1段のを省け、1504となる。2本併合は4段で、全段コピーなら。この比較では同じ「各段で全てを書き直す」実装規則を用いている。
(5) 内部比較回数
ヒープの交換・削除に1レコード当たり 比較を使うので1段 、全体 。通常のパラメータ範囲では に収まる。 が大きいと1段の比較は増えるが、段数が減り、全データの読み書きを繰り返す回数を減らせる。I/O の削減と内部比較の評価は別の尺度である。