第3回 局所選択が正しい条件
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 180分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
最小全域木と同じ重みの落とし穴¶
連結単純無向グラフの各辺に実数重みがある。全域木の重みは辺重みの和であり、最小全域木をMSTと略す。同じ重みの辺は許す。部分集合、をまたぐ辺をカット辺という。利用する最小辺の性質は証明してから用いること。
(1) カットの最軽量辺(6点)¶
あるカットの最軽量辺が、少なくとも一つのMSTに含まれることを交換法で証明せよ。がカットの唯一の最軽量辺なら、すべてのMSTに含まれることも証明せよ。
(2) 閉路の最重量辺(7点)¶
閉路上の唯一の最重量辺は、どのMSTにも含まれないことを証明せよ。「閉路上の最重量辺は、同重みがあってもすべてMSTから除外できる」を反例で否定せよ。
(3) MSTの列挙と辺の分類(8点)¶
、辺の重みを次のようにする。
| 辺 | ||||||
|---|---|---|---|---|---|---|
| 重み | 1 | 2 | 2 | 3 | 3 | 6 |
すべてのMSTを列挙し、どのMSTにも含まれる辺、少なくとも一つに含まれる辺、どれにも含まれない辺を分類せよ。
(4) 辺の採用と成分管理(8点)¶
辺を重み順に整列し、閉路を作らない辺を順に加える方法を示せ。連結成分を管理する素朴なラベル更新法でもよい。その正しさを示し、整列部分と成分管理部分の計算量を分けて評価せよ。
(5) 最適性条件と一意性(6点)¶
ある全域木について、すべての非木辺の重みが上の経路の最大辺重み以上なら、がMSTであることを証明せよ。全辺の重みが異なる場合、MSTの一意性を導け。
参考解答・採点の観点 — 問題1
(1) カットの最軽量辺
を含まないMST へを加えると閉路ができ、その閉路には同じカットをまたぐ別辺がある。なので交換後もMST。唯一最小なら不等号は厳密であり、を含まない最適木の存在に矛盾。
(2) 閉路の最重量辺
最重量辺を含む木からを除いてカットを作る。閉路にはカットをまたぐ軽い別辺があるので交換で改善。三角形の全辺重み1なら任意の辺はMSTに入れる。特定の一辺を除外するMSTは存在するが、すべてのMSTから除外されるわけではない。
(3) MSTの列挙と辺の分類
すべてのMSTは を必ず含み、 または の一辺、 または の一辺を選ぶ4通り。重みはいずれも6。
| 分類 | 辺 |
|---|---|
| 必須 | |
| 選択可能 | |
| 除外 |
(4) 辺の採用と成分管理
整列後、端点ラベルが異なるときだけ辺を採用し片方の成分ラベルを更新。採用辺は成分カットの最軽量候補なので交換法で拡張可能。辺整列、ラベル更新は高々回各、全体。より高度な集合管理なら改善可能だが本問では不要。
(5) 最適性条件と一意性
の任意の辺を除くカットを考える。そのカットをまたぐ非木辺の経路はを含むので。よっての各辺はその基本カットの最軽量辺である。任意の別木を基本カット交換でへ近づけ、重みは増やさずへ至るためは最小。相異なる重みなら各カット最小辺は唯一となりの全辺が必須。
問題2 · 動的計画法(35点)¶
重み付き共通部分列と辞書式復元¶
は長さの文字列で、文字集合には全順序がある。文字を一つ選ぶ得点を正整数とする。共通部分列の得点は各文字得点の和。まず最大得点を求め、さらに最大得点の共通部分列のうち辞書式で最小の文字列を出力する。辞書順では一方が他方の接頭辞なら短い方を小さいとする。
(1) 接尾辞DPと漸化式(6点)¶
接尾辞の最大得点をとする。境界条件と漸化式を導け。同じ文字の場合にも、不採用側の候補を残してよいことを説明せよ。
(2) 正しさと得点の比較(7点)¶
漸化式の正しさを証明し、最大得点だけを求める時間・空間計算量を示せ。「長い共通部分列ほど高得点である」という主張を反例で否定せよ。
(3) 辞書式最小の貪欲復元(8点)¶
各位置以降で文字が最初に現れる位置をとして前計算する。残り得点を保ちながら辞書式最小の最適解を貪欲に復元する方法を示し、その選択が安全であることを証明せよ。
(4) 具体例(8点)¶
、、とする。最大得点と辞書式最小の最適共通部分列を求めよ。すべての文字得点を1にした場合の答えも求めよ。
(5) 計算量と非正得点(6点)¶
前計算と復元を含む時間・補助空間計算量を,出力長で示せ。得点0で復元を停止できる理由を説明せよ。文字得点が0または負でもよい場合、同じ停止規則と貪欲復元が正しいかを検討し、正しいなら理由、誤るなら反例を示せ。
参考解答・採点の観点 — 問題2
(1) 接尾辞DPと漸化式
境界は 。
不採用候補を残せば全選択肢を含む。値は接尾辞の包含関係に従い単調。
(2) 正しさと得点の比較
最初の採用位置の構造から最後の候補、または片方の先頭を飛ばす二候補に分かれる。時間、得点のみなら空間。重みなら一文字の得点10はAAの得点2より高い。文字列で両候補が可能。
(3) 辞書式最小の貪欲復元
文字を昇順に試し、が存在してならを採用。最も早いは他の採用位置より大きな接尾領域を残す。もし最適解がから始まるなら、この早い位置でも得点を達成できる。最小文字を確定して同じ議論を再帰する。
(4) 具体例
| 条件 | 最適得点 | 辞書式最小の最適共通部分列 |
|---|---|---|
| 重み付き | BAC | |
| 単位重み | 3 | AAC |
単位重みでは AAC と BAC が可能で辞書式最小は AAC。
(5) 計算量と非正得点
表、next前計算、復元。保存量も。正得点ではなら空しか最適にならない。0または負の得点を許しても、この復元は正しい。なら空は最適であり、非空文字列より辞書式で小さいので停止してよい。では実現可能な最初の文字を最小に選ぶ証明がそのまま成立する。負得点の文字は最適解に含めると、それを除くことで得点が改善するため採用されない。0得点の文字は辞書順を改善し得るので、のときは候補から除かない。
問題3 · 整列アルゴリズム(30点)¶
重複キーに強い三分割クイックソート¶
配列には同じキーが複数現れてよい。部分配列からピボットを一つ選び、キーがより小さい区間、等しい区間、大きい区間へその場で三分割する。等しい区間は再帰的に整列しない。比較と交換は。後半の期待値分析では各再帰部分配列の要素位置を一様に選ぶ。
(1) 三分割と不変条件(5点)¶
三分割の擬似コードを書き、走査中の三つの確定区間と未分類区間を表す不変条件を示せ。走査時間と補助空間を評価せよ。
(2) 全キーが等しい場合(5点)¶
すべてのキーが同じ場合の三分割法の計算量を示せ。等しいキーをすべて片側へ送る二分割法との違いを、再帰式を用いて説明せよ。
(3) 期待比較回数(7点)¶
キーがすべて異なる場合、順位の二要素が直接比較される確率を求め、それを用いて期待比較回数を導け。再帰木を平均的に釣り合うと仮定するだけの説明では不十分である。
(4) 具体例と安定性(7点)¶
をピボット3で三分割した結果の各区間の多重集合を示せ。この整列法が一般に安定でない具体例を示し、元の位置を比較キーに付加する安定化が「重複キーに強い」という性質へ与える影響を論じよ。
(5) 最悪時間と再帰空間(6点)¶
常に先頭要素をピボットにする場合の最悪入力を示せ。ランダム化でも最悪時間が残る理由と、再帰の深さを抑えるため小さい区間だけを再帰し大きい区間をループで処理する方法の空間上界を説明せよ。
参考解答・採点の観点 — 問題3
(1) 三分割と不変条件
lo,mid,hiを用いる。ならswap(lo,mid),lo++,mid++。=ならmid++。>ならswap(mid,hi),hi--でmidは進めない。区間は<、は=、は>、は未分類。各回未分類が一つ減り,補助。
(2) 全キーが等しい場合
三分割なら一度の走査で再帰なし。二分割で等号を片側へ送るなら
(3) 期待比較回数
順位区間[]内で最初のピボットが端点またはのときだけ比較される。
期待数は
(4) 具体例と安定性
小さい区間{1,1,2}、等しい区間{3,3,3}、大きい区間は空。たとえば識別子付きでピボット1なら最初の交換でとなり同値順が逆転。(key,元位置)で全順序にすれば安定な最終出力だが同キーも比較上相異なり、一括処理する利点を失う。
(5) 最悪時間と再帰空間
相異なる降順入力なら先頭が毎回最大となる。この三分割では小さい値が順に左へ移り、左区間は降順を保って長さとなるため最悪。相異なる昇順入力は分割で右区間の順序が変わるので、同じ説明をそのまま使わない。乱数でも同じ極端なピボット列が正の確率で起こるので最悪は二次。小さい側の再帰サイズは高々半分なので積み重なる再帰深さ。大きい側を末尾ループ処理すれば最悪補助空間。