第18回 同率の選択・資源の競合・確率の保証
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 210分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
最小全域木に必須の辺・選択可能な辺¶
連結単純無向グラフ に実数の辺重みが与えられる。各辺を「すべての最小全域木に含まれる」「一部には含まれるが一部には含まれない」「どの最小全域木にも含まれない」の3種類に分類したい。同じ重みの辺が多数あることを許す。重み の処理直前に、 より小さい辺だけで連結される頂点を縮約する。残った重み の辺から作る補助グラフは平行辺を持ち得る。入力が単純グラフでも、縮約後まで単純とは限らない。各辺には固有の辺番号があるものとする。
(1) 小さい重みによる縮約(5点)¶
重み の辺の両端点が、 より小さい辺だけですでに連結されている場合、その辺はどの最小全域木にも含まれないことを証明せよ。閉路上の最大辺に関する主張で、等重みの場合と混同しないこと。
(2) 補助グラフの橋と分類(7点)¶
縮約後の補助グラフで、橋となる辺はすべての最小全域木に必要であり、橋でない非ループ辺は一部に含まれ一部に含まれないことを証明せよ。補助グラフが非連結でも成分ごとに扱える理由を示せ。
(3) 同率辺と平行辺の反例(6点)¶
同じ重みの辺を1本ずつ追加し、そのたびに連結集合を更新して分類する方法が誤る例を示せ。また、補助グラフの DFS で親頂点への辺をすべて無視する実装が誤る平行辺の例を示し、正しい扱いを述べよ。
(4) 重みごとのバッチ処理(7点)¶
重み順のバッチ処理、連結集合の縮約、補助グラフでの橋検出を組み合わせた擬似コードを書け。各バッチの分類が完了してから集合を統合すること。全補助グラフのサイズ合計を用いて時間・空間を評価せよ。
(5) 辺分類の具体例(5点)¶
頂点 、重み1の辺 、重み2の辺 、重み3の辺 ag を考える。各辺を3種類に分類し、重み2の補助グラフを描くか、頂点・平行辺を明記せよ。
(6) 同時選択と一意性(5点)¶
「一部に含まれる」辺がすべて同時に含まれる最小全域木は存在するか。一般には存在しないことを示せ。また、すべての辺の分類結果から最小全域木の一意性を判定する必要十分条件を述べよ。
参考解答・採点の観点 — 問題1
(1) 小さい重みによる縮約
辺 の両端には、すべての重みが より小さいパスがある。もし最小全域木 が を含めば、 の切断をそのパスのどれかの辺 が渡る。 は全域木で 、したがって総重みが小さくなるという矛盾である。等重みのパスしかない場合、この厳密な改善は得られず、辺が選択可能である場合もある。
(2) 補助グラフの橋と分類
小さい辺の各連結成分は、どの最小全域木でも、その成分内のより小さい辺によって連結しておくことができ、重み のバッチでは補助グラフの各成分に全域木を選ぶことが必要かつ十分である。これは Kruskal の切断交換を等重みで行って確認できる。橋はその補助成分を連結する全域木すべてに入る。非橋 は閉路上にあり、 を含まない全域木がある。また を含む森 を拡張すれば を含む全域木もある。両方の選択は同数の重み 辺を用い、後の大きい重みで同様に拡張できるので、元の最小全域木の選択に対応する。
(3) 同率辺と平行辺の反例
等重みの三角形を1本ずつ統合すると、3本目は既に連結された端点を持つため「不可」と誤分類されるが、実際にはどの辺も三つの最小全域木の一部に入る。平行辺2本だけの補助グラフではどちらも橋でない。親頂点への全辺を無視すると、2本目の平行辺を後退辺として扱えず、最初の辺を橋と誤る。DFS では親への「辺番号」1本だけを除外し、他の平行辺は low の更新に使う。
(4) 重みごとのバッチ処理
重みで全辺を整列し、連結集合を単独頂点で初期化
for 同重みの辺集合 B:
H = 空の辺番号付き多重グラフ
for e=(u,v) in B:
a=find(u); b=find(v)
if a==b: label[e]=不可
else: H に辺 (a,b,e) を追加
H の各成分で辺番号を用いた DFS により橋を検出
H の橋を必須、他の辺を選択可能に分類
for (u,v) in B: union(u,v)各元の辺が補助グラフに現れるのは高々1回。使った頂点だけを各バッチで記録すれば頂点出現数も 。橋検出の総時間は 。大きさで統合する連結集合なら find は で、総時間 、補助空間 。連結グラフでは通常 と簡約できる。未使用の全 頂点を毎バッチ初期化しないこと。
(5) 辺分類の具体例
重み1を縮約すると 。重み2では に の平行辺、 に ef、 に cf、 に fg がある。必須は 。選択可能は 。不可は ag。重み1の三角形に橋はなく、de は橋。重み2では だけが橋で、 内は迂回できる。
(6) 同時選択と一意性
等重み三角形の3辺はすべて「一部に含まれる」が、全域木に3辺同時は含められない。したがって個別の選択可能性は同時選択可能性を意味しない。最小全域木が一意である必要十分条件は、選択可能な辺が1本もないこと。2種類の木があれば対称差の辺が選択可能となる。逆に選択可能辺がなければ各辺の所属はすべて必須か不可に固定され、最小木の辺集合は一つに定まる。
問題2 · 動的計画法(35点)¶
二つの予算と辞書順の最適解¶
個の品物について、二資源の消費量 は非負整数で 、価値 は正整数である。各品物は高々1回選べる。資源の上限は で、価値和を最大化する。価値が等しい解では選択ビット列 を辞書順最小にする。ただし とし、選ばないことを0、選ぶことを1とする。これは選んだ品物番号の列の辞書順とは別の規則である。資源を使い切る必要はない。資源量と価値が異なる状態を、十分な根拠なく一つにまとめないこと。
(1) 二資源の状態と漸化式(5点)¶
を最初の 品物から消費量がちょうど となる最大価値として、境界と漸化式を導け。最後の答えに必要な最大値の範囲も述べよ。
(2) その場更新の順序(6点)¶
1枚の二次元表で価値だけを求める更新順を示せ。 または の場合も同じ品物を再利用しないことを証明せよ。両方を昇順に更新すると失敗する具体例を与えよ。
(3) 辞書順最小の復元(6点)¶
前向き DP で等価値のとき常に「現在の品物を選ばない」候補を優先すると、要求した辞書順になるとは限らない。2品物の反例を示せ。後ろ向きの最適価値表を使い、最初のビットから正しく決める条件を導け。
(4) 支配関係と辞書順(6点)¶
同じ処理段階の状態 が (′,′,′) に対し ′,′,′ なら、価値のみの最大化には後者を削除できることを証明せよ。 の小ささと価値だけで比較する誤りを反例で示し、辞書順の同率処理には追加情報が必要なことも述べよ。
(5) 二予算の具体例(7点)¶
上限 、品物が順に のとき、最適価値と辞書順最小ビット列を求めよ。最適な選択が他にある場合はそれも挙げ、最適性を説明せよ。
(6) 完全な復元と計算量(5点)¶
辞書順最小解を復元する完全な擬似コードを書け。価値だけの場合と、全後ろ向き表を保存して復元する場合の時間・空間を評価せよ。上限の数字ではなく入力のビット長に対して、擬多項式である理由を説明せよ。
参考解答・採点の観点 — 問題2
(1) 二資源の状態と漸化式
、それ以外は 。
で、範囲外の第二候補は除外する。答えは のすべての の最大。 だけでは、使い切らない最適解を見落とす。
(2) その場更新の順序
各品物について 、各 で と降順に走査する。 なら参照元はより小さい の、まだ今回更新していない行。 なら で、参照元は同じ行のより小さい の未更新セル。 でも によって安全である。 が必要。昇順では品物1個 、上限 に対して を更新した直後に へ再利用して価値10を作ってしまう。
(3) 辞書順最小の復元
同じ品物2個 、上限 を考える。品物2で等価値なら不採用を優先する前向き法は10を残すが、要求する最小列は01。 を品物 から残容量以内で得る最大価値とする。残容量 、必要価値 の時、 なら とできるので必ず0を選ぶ。等しくない場合に限り1を選び、容量と必要価値を減らす。最初に異なるビットをできるだけ0にするため、帰納的に辞書順最小となる。
(4) 支配関係と辞書順
残りの品物は同じなので、後者の状態に追加可能な任意の選択は前者にも追加でき、最終価値も下がらない。誤った総消費量比較の例は状態 と 、上限 、残品物 。総消費は同じ5で後者の価値が高いが、前者からだけ価値108を得られる。辞書順も最適化する場合、同価値で資源を節約する状態の選択済み接頭辞が大きいことがあるので、価値の支配だけでは同率解を安全に消せない。価値が厳密に大きい場合の削除と、同率接頭辞の比較を区別する。
(5) 二予算の具体例
最適価値12。品物 はビット列10100、 は01100で、双方とも消費 。辞書順では01100を選ぶ。品物1と2の同時選択は第1資源4で不可。3と4と5は第2資源5で不可。1または2と4と5も第2資源4で不可。他の実現可能な2品物は価値10以下か9以下で、3品物以上で12を超える組合せもこの資源検査で排除できる。
(6) 完全な復元と計算量
S[n+1][a][b]=0 for 全容量
for i=n..1:
for a=0..A, b=0..B:
S[i][a][b]=S[i+1][a][b]
if a>=aᵢ and b>=bᵢ:
S[i][a][b]=max(S[i][a][b], S[i+1][a-aᵢ][b-bᵢ]+vᵢ)
a=A; b=B; V=S[1][A][B]
for i=1..n:
if S[i+1][a][b]==V: xᵢ=0
else: xᵢ=1; a-=aᵢ; b-=bᵢ; V-=vᵢ計算は 。価値のみなら2行または降順更新で 空間、復元表は 空間、復元 。 が二進で入力されると桁数は なので、この時間は一般に入力ビット長の多項式ではない。
問題3 · 整列アルゴリズム(30点)¶
ランダムなクイックソートは何を保証するか¶
互いに異なるキーを持つ 個の要素をクイックソートする。サイズ の部分配列では、その 要素から独立に一様ランダムなピボットを選び、残りの 個を各1回比較して左右に分ける。入力は乱数を引く前に固定され、乱数を見てから値を変更する相手はいない。比較回数を 、最大分割深さを とする。平均の保証、最悪の保証、高確率の保証を区別したい。ln は自然対数、 とする。必要なら二項分布について を使ってよい。
(1) 二要素の比較確率(6点)¶
キーを順位で表す。順位 の二要素が比較される確率が となる理由を示せ。区間内で最初に選ばれるピボットを使い、区間外のピボットがこの議論を妨げないことを説明せよ。
(2) 期待比較数と最悪値(8点)¶
(1)から を導け。最悪値 が生じるピボット列とその確率も求め、期待値 が最悪 を意味しないことを説明せよ。
(3) 良いピボットの確率(5点)¶
サイズ の分割で両側のサイズが高々なら、そのピボットを良いと呼ぶ。良い確率が少なくともであり、ある要素の経路上で 回の良い分割があれば経路が終了することを示せ。
(4) 深さの高確率保証(6点)¶
とする。各要素の経路上の良い分割数を二項分布で下から評価し、 を導け。その結果から高確率で比較回数が になることを示せ。定数64の最適化は不要である。
(5) スタックと最悪比較数(5点)¶
常に小さい側を再帰処理し、大きい側はループで続ければ、どのピボット列でも呼出しスタックが になることを証明せよ。この工夫が比較回数の最悪値も改善するか。また、ピボット位置を知ってから相手がキーを決められるモデルで、上の確率保証が使えない理由を述べよ。
参考解答・採点の観点 — 問題3
(1) 二要素の比較確率
順位 の中で最初にピボットになる要素が または の場合だけ、両者は同じ部分配列に残ったまま一方がピボットとなり比較される。内部の順位が先なら左右に分かれ、以後比較されない。区間外のピボットは両者を同じ側へ送るだけで、区間内の要素の相対的な最初の一様選択は変わらない。 個のうち端点は2個なので確率は。
(2) 期待比較数と最悪値
指示変数を足して 。 と置くと 。毎回最小または最大をピボットにするとサイズが1ずつ減り、。サイズ で端を選ぶ確率はなので、この事象の確率は 。小さくても正であり、期待値の保証だけから最悪値を変更できない。
(3) 良いピボットの確率
良い順位の数は少なくとも なので、現在までの乱数を条件としても良い確率。良い分割のたびに、固定した要素が残る部分配列は高々倍になる。 回ならサイズ。 では1以下で、比較する分割は終了する。良くない分割でサイズが小さくなることは、さらに早い終了にしか働かない。
(4) 深さの高確率保証
固定要素のまだ終了していない経路では、各段の良い確率は条件付きでも。独立一様乱数との結合で、良い数は を確率的に下回らないようにできる。()なので、深さが を超えるには良い数が 未満でなければならない。確率。要素に和の上界を使うと 。各深さで扱う部分配列は互いに素で総サイズ、または各要素が高々回参加すると考えれば 。よって確率以上で 。
(5) スタックと最悪比較数
新しい再帰呼出しは現在サイズの半分以下の側だけに対して行うので、スタック上でサイズは少なくとも半分ずつ減り、高さは 。大きい側へ進むときは同じフレームを再利用する。ただし端ピボット列の比較和はそのまま で、改善するのはスタックである。入力をピボット位置に応じて後から決める相手なら、常にその位置を最小キーにできるため「固定順位の中から一様に選ぶ」という確率計算の前提が壊れる。