第2回 数える・復元する・順序を測る
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 180分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
最短経路の本数と必須頂点¶
単純無向グラフに異なる頂点が与えられ、からへの経路が存在する。辺の長さはすべて1。最短経路の本数を数え、すべての最短経路が通る頂点を調べたい。本数は指数的に大きくなり得るが、本問では正確な整数の加算・乗算・比較をとする算術演算回数を評価する。
(1) 最短経路に含まれる条件(6点)¶
とからのBFSにより距離を求める。頂点がいずれかの最短経路に含まれる必要十分条件を示せ。最短経路に含まれる向き付き辺の条件も導け。
(2) 最短経路DAGと経路数(7点)¶
最短経路上の辺をからの距離が増える向きに向ける。この有向グラフが非巡回であることを証明し、から各頂点への経路数を数える漸化式と計算順序を示せ。
(3) 必須頂点の判定(8点)¶
各頂点からへの経路数も計算する。すべての最短経路がを通ることをで判定せよ。二つの経路を連結したときに頂点の重複が生じない理由を証明せよ。
(4) 具体例と必須辺(8点)¶
について、距離表、、最短経路数、必須頂点を求めよ。必須辺もすべて求めよ。
(5) 全体の計算量と剰余の反例(6点)¶
アルゴリズム全体の擬似コードと算術演算回数を示せ。「経路数を大きな整数で割った余りだけで比較すれば、必須頂点を常に正確に判定できる」という主張を否定せよ。
参考解答・採点の観点 — 問題1
(1) 最短経路に含まれる条件
として。向きの条件はである。最短経路を分割して必要性が得られ、距離条件を満たす最短接頭・接尾経路の連結から十分性が得られる。
(2) 最短経路DAGと経路数
各有向辺でが1増えるので閉路はない。、他は0から開始し、距離昇順にへ各先行のを加える。BFS順を利用できる。
(3) 必須頂点の判定
として逆順に計算。を通る本数は。必須条件は。接頭側は距離≤、接尾側は距離≥、等号の層ではしか共有しない。
(4) 具体例と必須辺
頂点順は 。
| 頂点 | ||||
|---|---|---|---|---|
| 0 | 3 | 1 | 3 | |
| 1 | 2 | 1 | 2 | |
| 1 | 2 | 1 | 1 | |
| 2 | 1 | 2 | 1 | |
| 2 | 1 | 1 | 1 | |
| 3 | 0 | 3 | 1 |
最短経路は3本。必須頂点は のみで必須辺はない。
(5) 全体の計算量と剰余の反例
BFS二回、最短DAG構築、正逆DP、全頂点・辺判定で、補助空間も。余り一致は整数の一致を意味しない。≥2について、との間に長さ2の内部頂点を共有しない経路を本作る。各内部頂点を通る経路数は1、全経路数はであり、どちらもを法として1となる。は必須でないのに必須と誤判定される。
問題2 · 動的計画法(35点)¶
ちょうどr品を選ぶナップサック¶
個の品物があり、品物の正整数重量を、整数価値をとする。価値は負でもよい。各品物は高々1回選べる。総重量以下、選ぶ個数がちょうどという制約の下で価値を最大化する。は非負整数、。実現不可能な場合はその旨を返す。
(1) 状態と初期値(6点)¶
接頭品物数、重量上限、選択個数を用いて状態を定義し、負の価値と実現不可能性を正しく扱う初期値と漸化式を示せ。
(2) 正しさと擬多項式時間(7点)¶
漸化式の正しさを最後の品物を選ぶ場合と選ばない場合に分けて証明せよ。表の大きさと時間計算量を示し、この計算量が入力のビット長に対して多項式とは限らない理由を説明せよ。
(3) その場更新と走査順序(8点)¶
の次元を取り除き、二次元表をその場で更新する擬似コードを書け。個数と容量の走査順序を示せ。個数を昇順に走査すると同じ品物を複数回選ぶ可能性があることを具体例で示せ。
(4) 具体例と復元(8点)¶
()が順に(2,5),(3,6),(4,8),(1,−1)、とする。最適価値と選ぶ品物を求めよ。の場合も答えよ。表から最適な品物集合を復元する手順を示せ。
(5) 状態の支配条件(6点)¶
容量が以下の状態を、重量と価値の組で保持する方法を考える。選択個数が同じ状態についての安全な支配条件を示せ。選択個数の異なる状態にも同じ支配規則を適用できない反例を示せ。
参考解答・採点の観点 — 問題2
(1) 状態と初期値
は個からちょうど品を選び重量の最大価値。、は。
後者はのときだけ候補。
(2) 正しさと擬多項式時間
品物の有無で集合を互いに重ならない二場合に分ける。接頭解をよりよいものに置換できるため最適部分構造が成立。時間、全表も同じ。が二進表記ならビットなのでに比例する時間は擬多項式。
(3) その場更新と走査順序
各品物についてをから1へ、をからへ下げ、。降順により前個数行は今回の品物で未更新。両方昇順なら1品(1,1)、で値2を誤って作る。補助空間。
(4) 具体例と復元
品物1と2で重量5、価値11が最適。品物3と4は価値7、その他を確認する。は不可能。全表でが不採用側と等しいならを飛ばせる。それ以外はを採用しを減らす。で復元。
(5) 状態の支配条件
同じで重量、価値なら()を捨てられる。残り品物への拡張で容量と個数条件が同じだからである。異なるでは残り必要数が異なる。例えば処理済み品物が(1,5),(1,−1)、残り品物なし、とする。の(重量1,価値5)はの(重量2,価値4)より軽く高価値だが、前者は終端の個数制約を満たさない。後者を捨てれば唯一の合法解を失う。
問題3 · 整列アルゴリズム(30点)¶
転倒数から最小隣接交換回数へ¶
個の互いに異なるキーからなる配列について、かつとなる対()を転倒と呼ぶ。転倒数をとする。隣接する二要素の交換だけを用いて配列を昇順に整列したい。後半では同値キーも許し、同値対を転倒には数えない。
(1) 隣接交換と転倒数(5点)¶
一度の隣接交換によって転倒数がどのように変化するかを証明し、昇順整列に必要な隣接交換回数の下界を示せ。
(2) 挿入整列の交換回数(5点)¶
挿入整列がちょうど回の隣接交換で整列できることを示せ。その比較回数と移動回数をで評価し、整列済み入力と逆順入力を比較せよ。
(3) 併合による転倒数の計算(7点)¶
併合整列を用いてを時間で求める擬似コードを書け。右半分の要素を先に出すときに加算する数を示し、分割・併合の正しさを証明せよ。
(4) 具体例と同値キー(7点)¶
の転倒数と最小隣接交換回数を求めよ。同値キーを許す場合、併合時の比較をどのように変更すれば、厳密な転倒数を数えながら安定性も保てるか説明せよ。
(5) 二つの順列の順序差(6点)¶
同じ個の識別子をそれぞれ一度含む二つの順列の順序の相違を、からへ変える最小隣接交換回数で測る。の順位を用いて一つの転倒数問題へ帰着し、時間計算量を示せ。
参考解答・採点の観点 — 問題3
(1) 隣接交換と転倒数
交換対以外の相対順序は変わらない。異なるキーなら当該対が転倒から非転倒または逆へ変わるため。終端の転倒数0へ行くには少なくとも回。
(2) 挿入整列の交換回数
挿入時に左側の大きい要素とだけ交換し、1回ごとに転倒を1減らす。ゆえに回で下界達成。比較、移動(通常の実装)。整列済み、逆順。
(3) 併合による転倒数の計算
左右の内部転倒数を再帰計算。左の位置と右の位置を比較し、なら左を出す。そうでなければ右を出し、残り左要素数を0始まり添字で加える。左残りはすべてその右要素より大きい。
(4) 具体例と同値キー
5に関する4対、4に関する2対で計6。最小交換数6。同値では左を先に選ぶ≤比較を用い、右を出すのは厳密な<の場合だけにする。等しい対を加算せず安定。
(5) 二つの順列の順序差
を作り、配列とする。識別子の相対順序の不一致はの転倒と一致。辞書構築を仮定すれば全体、補助空間。比較辞書の場合でもに収まる。