第5回 境界条件と計算モデル
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 180分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
全域木がBFS木になれる条件¶
単純連結無向グラフの全域木と根が与えられる。上の深さをとする。隣接頂点を調べる順序は頂点ごとに自由に選べる。がのBFS木として得られるかを調べたい。BFS木では各頂点の親はその頂点を初めて発見した頂点であり、単に最短距離の親を任意に選ぶ定義ではない。
(1) 深さと最短距離(6点)¶
がBFS木なら、すべての辺についてとなることを証明せよ。さらに、この条件が上の深さとのからの最短距離の一致を保証することを証明せよ。
(2) 辺条件だけでは不十分な反例(7点)¶
上の辺条件だけでは、標準的なFIFOキューを用いるBFSでを実現できるとは限らない。の子と、深さ2の頂点について、の親をとし、追加辺を入れた例で不可能性を示せ。
(3) 親と子ブロックの処理順序(8点)¶
各深さ層の頂点の処理順序を考える。深さの頂点の親が、同じ深さの他の隣接頂点より先に処理される必要がある。この条件が必要であることを示し、親の順序が次層の子のブロック順序を制約することを説明せよ。
(4) 正しい判定法と計算量(8点)¶
がBFS木として実現できるかの簡単で正しい判定法を設計せよ。効率より正しさを優先し、各頂点の隣接順序をすべて列挙してBFSを実行する方法でもよい。上界を各頂点の次数で表せ。成功時と失敗時に返す内容を定めよ。
(5) 訪問順と最短距離(6点)¶
BFSにおいて「深さが同じ頂点はどの順に処理しても親木は変わらない」が誤りである理由を述べよ。一方、訪問順が変わっても最短距離は変わらないことを証明せよ。
参考解答・採点の観点 — 問題1
(1) 深さと最短距離
木経路の長さがdepth。辺で深さ差≥2なら浅い端点への木経路とその辺で深い端点へ短縮できる。逆に辺ごとに深さ増加≤1なのでからへの任意経路長≥、木経路で等号。
(2) 辺条件だけでは不十分な反例
を先に処理するとを両方発見し、の親がとなる。を先に処理するとを両方発見し、の親がとなる。隣接列内で順序を変えても親は変えられない。
(3) 親と子ブロックの処理順序
より先の同層隣接頂点がを発見するため必要。FIFOではある親の未訪問の子をまとめてキュー末尾へ追加するので、同層の親順が次層の子ブロック順に伝播する。層ごとの独立な位相順序だけで十分と結論してはいけない。
(4) 正しい判定法と計算量
辺深さ条件を最初に検査。その後、全頂点の隣接順序の組を列挙し、各組で標準BFSを走らせ親配列を比較する。時間、列挙を逐次生成すれば補助空間。成功なら具体的な隣接順序、失敗なら「存在しない」。全可能性を尽くすので正しい。
(5) 訪問順と最短距離
(2)が親木の反例。BFSは深さ層順に処理し、距離の頂点から初めて発見された頂点は距離であり、それより短い経路があれば先の層で発見されるはず。隣接順序は同層内の発見者を変えるだけ。
問題2 · 動的計画法(35点)¶
曲がる回数を制限した格子経路¶
の格子の各セルに整数得点があり、一部は障害物である。左上(1,1)から右下()まで右または下へ移動する。訪問した各セルの得点を一度ずつ加える。連続する二移動の方向が異なるとき「曲がり」が1回あると数える。最初の移動は曲がりに数えない。曲がりがちょうど回の最大得点経路を求める。
(1) 状態と境界条件(6点)¶
最後の移動方向と曲がり回数を含む状態を定義し、初期値と障害物の扱いを示せ。の場合と、片方だけが1の場合を別に説明せよ。
(2) 方向別の漸化式(7点)¶
右移動で終わる状態と下移動で終わる状態の漸化式を導け。移動方向を記録しない二次元状態では不十分な理由を、同じセル・同じ曲がり回数の二つの接頭経路を用いて説明せよ。
(3) 正しさと到達不能状態(8点)¶
計算順序と正しさの証明を示し、時間・空間計算量をで評価せよ。到達不能状態を0で初期化すると誤る具体例を示せ。
(4) 具体例(8点)¶
障害物のない3×3格子の得点を、行ごとに
とする。とについて最適得点と経路を求めよ。
(5) 最適経路数と復元(6点)¶
最大得点を達成する経路の本数も同時に求める方法を設計せよ。方向別の状態を足し合わせる際の二重計数の有無を説明し、最適経路一つの復元方法も示せ。
参考解答・採点の観点 — 問題2
(1) 状態と境界条件
を右・下方向で到着した最大得点とする。障害物と不可能状態は。最初の右・下移動だけ、始点得点を含めで直接初期化する。1×1ではのみ始点得点、片側1なら唯一の直線経路ののみ可能。
(2) 方向別の漸化式
初回は別扱い。末尾方向が異なると次の右移動が曲がりか否か異なるので、得点だけ残すと合法性を失う。
(3) 正しさと到達不能状態
行列の左上から右下へ計算。最後の一歩で全候補を分け、取り除いた経路は対応する前状態。時間、全表空間同じ、得点のみ。負得点の格子で未到達0を残すと、途中から無料で開始する架空経路が生まれる。
(4) 具体例
| 曲がり回数 | 経路 | 得点 |
|---|---|---|
DDRR | ||
RRDD | 19 | |
DRRD | ||
RDDR |
の最適経路は DDRR。 の最適経路は RDDR, DRRD の2本。
(5) 最適経路数と復元
各状態に(score,count)を保持し、最大候補だけのcountを足す。初回1、実現不可能0。末尾方向が異なる経路は互いに別なので終端の同点時にも足せる。始点だけは別処理。前状態一つを保存しで復元。大きな整数のビット費用は別途必要。
問題3 · 整列アルゴリズム(30点)¶
双調整列の仕事量と並列深さ¶
個の値を、比較交換器からなるネットワークで整列する。比較交換器は二入力の小さい方と大きい方を指定された出力へ送る。互いに異なるワイヤを使う比較器は同時実行できる。双調列とは、循環シフト後に非減少区間と非増加区間の連結になる列であり、同値を許す。
(1) 双調併合の性質(5点)¶
長さの双調列について、距離の対を比較し小さい方を前半へ、大きい方を後半へ送る。前半・後半がそれぞれ双調で、前半の最大値が後半の最小値以下になることを証明せよ。0–1列の場合を先に示して一般値へ拡張してよい。
(2) 併合の仕事量と深さ(5点)¶
双調併合の比較器数と深さの再帰式を導いて解け。同じ段で個の比較器が並列に動くことと、仕事量を区別せよ。
(3) 整列全体の仕事量と深さ(7点)¶
任意の列の前半を昇順、後半を降順に再帰整列して双調併合する。全比較器数と深さの再帰式を解き、とのどちらが仕事量か明記せよ。
(4) 各比較段の具体例(7点)¶
双調列 について、最初の比較段の出力、前半と後半それぞれの次の比較段の出力、最終昇順列を示せ。
(5) 処理器数と深さの下界(6点)¶
各段を個の処理器で実行する場合の実行時間の上界を、仕事量と深さで示せ。さらに、各出力値が依存し得る入力数から、比較ネットワークの整列深さにの下界があることを説明せよ。
参考解答・採点の観点 — 問題3
(1) 双調併合の性質
0–1双調列では循環的に1の位置が一つの区間をなす。対のmin,maxは0/1の区間構造を保ち、前半に1と後半に0が同時に残ることはない。一般値で性質が破れれば、閾値で0/1化すると同じ比較交換順で違反が残る。双調性も閾値化で保たれる。
(2) 併合の仕事量と深さ
再帰する二半分は並列なので深さ式には係数2がない。
(3) 整列全体の仕事量と深さ
仕事量、深さ。
(4) 各比較段の具体例
| 比較段 | 出力 |
|---|---|
| 初段(距離4) | |
| 次段(距離2) | |
| 最終段(距離1) |
(5) 処理器数と深さの下界
各段の比較を個ずつ行えば。出力の最小値は全入力のいずれにも依存し得る。一比較段で依存集合のサイズは高々倍増し、深さなら高々、従って。双調整列が深さ下界そのものを達成するとは結論できない。