アルゴリズムと計算量の問題

難易度 3期末試験の応用レベル証明問題大学数学アルゴリズムと計算量

$n$ を正の整数とし、 $i = 1, \dots, n$ に対して実数 $l_{i} \leq r_{i}$ と閉区間 $I_{i} = [l_{i}, r_{i}]$ が与えられている（区間の長さ $r_{i} - l_{i}$ は区間ごとに異なってよい）。実数の有限集合 $S$ が、すべての $i$ について $S \cap I_{i} \neq = \emptyset$ を満たすとき、 $S$ を「刺し集合」と呼ぶ。刺し集合の要素の個数の最小値を $OPT$ とする。

次の貪欲アルゴリズムを考える。
- $U = {1, 2, \dots, n}$ , $S = \emptyset$ , $k = 0$ とする。
- $U \neq = \emptyset$ である間、次を繰り返す： $k$ を $1$ 増やし、 $U$ の中で $r_{i}$ が最小となる添字 $i$ を 1 つ選んで $j_{k}$ とし（最小となる添字が複数あるときはそのうち最小の添字とする）、 $p_{k} = r_{j_{k}}$ として $S$ に $p_{k}$ を加え、 $U$ から $l_{i} \leq p_{k} \leq r_{i}$ を満たす添字 $i$ をすべて取り除く。
- $U = \emptyset$ となったときの $k$ の値を $g$ として、 $S = {p_{1}, \dots, p_{g}}$ を出力する。

このアルゴリズムは必ず停止し、出力 $S$ は刺し集合であり、 $S$ の要素の個数は $g$ で、 $g = OPT$ が成り立つことを証明せよ。

この問題で使うもの

区間スケジューリングの貪欲法（説明と入口の問題）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

「停止すること」「出力が刺し集合であること（ $OPT \leq g$ ）」「どの刺し集合も $g$ 個以上の点を使うこと（ $OPT \geq g$ ）」に分けて示しましょう。下界には、どの 2 つも交わらない区間を $g$ 個見つける方法が使えます。

ヒント 2

貪欲法が各回に選んだ区間 $I_{j_{1}}, \dots, I_{j_{g}}$ に注目します。 $j_{k + 1}$ が $k$ 回目に取り除かれなかったことと、 $r_{j_{k}}$ の最小性から、 $l_{j_{k + 1}}$ と $p_{k}$ の大小関係を導きましょう。

ヒント 3

$r_{j_{k + 1}} \geq p_{k}$ と「 $p_{k} \in I_{j_{k + 1}}$ ではない」ことから $l_{j_{k + 1}} > p_{k}$ が得られます。ここから $p_{1} < p_{2} < \dots < p_{g}$ と、 $k < m$ のとき $r_{j_{k}} < l_{j_{m}}$ が成り立つことを確かめましょう。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

各回に選ばれた $j_{k}$ 自身が取り除かれることから、繰り返しが高々 $n$ 回で停止することを示している（1 点）
添字が取り除かれるのは $p_{k} \in I_{i}$ のときだけで、停止時に $U$ が空であることから、出力が刺し集合であることを示している（2 点）
$j_{k + 1}$ が $k$ 回目に $U$ に残っていたことと $r_{j_{k}}$ の最小性から $l_{j_{k + 1}} > p_{k}$ を導き、 $p_{k}$ が真に増加すること（したがって $∣ S ∣ = g$ ）を示している（3 点）
$k < m$ のとき $r_{j_{k}} < l_{j_{m}}$ となることから、区間 $I_{j_{1}}, \dots, I_{j_{g}}$ がどの 2 つも交わらないことを示している（2 点）
任意の刺し集合が交わらない $g$ 個の区間それぞれに異なる点をもつことから $OPT \geq g$ を示し、 $g = OPT$ と結論している（2 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

停止性、出力が刺し集合であること、 $p_{1} < p_{2} < \dots < p_{g}$ であること、どの刺し集合も $g$ 個以上の要素をもつこと、を順に示す。

(1) 停止性. $k$ 回目の繰り返しで選んだ $j_{k}$ について、 $l_{j_{k}} \leq r_{j_{k}} = p_{k} \leq r_{j_{k}}$ が成り立つので、 $j_{k}$ 自身はこの回に $U$ から取り除かれる。よって各回で $U$ の要素の個数は少なくとも $1$ 減る。 $U$ ははじめ $n$ 個の要素をもつので、繰り返しは高々 $n$ 回で終わり、アルゴリズムは停止する。 $g$ は $1 \leq g \leq n$ の整数である（ $n \geq 1$ より少なくとも 1 回は繰り返す）。

(2) 出力は刺し集合である. 添字 $i$ が $U$ から取り除かれるのは、ある $k$ について $l_{i} \leq p_{k} \leq r_{i}$ 、すなわち $p_{k} \in I_{i}$ となるときだけである。停止したとき $U = \emptyset$ なので、すべての $i$ がいずれかの回で取り除かれており、各 $I_{i}$ は $S$ の要素を含む。よって $S$ は刺し集合である。

(3) $l_{j_{k + 1}} > p_{k}$ と $p_{k} < p_{k + 1}$ . $1 \leq k \leq g - 1$ とする。 $j_{k + 1}$ は $k + 1$ 回目の開始時に $U$ に残っているので、 $k$ 回目の開始時にも $U$ に入っていた。 $k$ 回目の $j_{k}$ は、そのときの $U$ の中で $r_{i}$ が最小の添字なので $r_{j_{k + 1}} \geq r_{j_{k}} = p_{k}$ である。また $j_{k + 1}$ は $k$ 回目に取り除かれなかったので、 $l_{j_{k + 1}} \leq p_{k} \leq r_{j_{k + 1}}$ は成り立たない。 $p_{k} \leq r_{j_{k + 1}}$ は成り立つので、 $l_{j_{k + 1}} > p_{k}$ でなければならない。したがって
$p_{k + 1} = r_{j_{k + 1}} \geq l_{j_{k + 1}} > p_{k}$
である。これより $p_{1} < p_{2} < \dots < p_{g}$ となり、 $p_{1}, \dots, p_{g}$ は相異なるので $S$ の要素の個数はちょうど $g$ である。特に (2) と合わせて $OPT \leq g$ が成り立つ。

(4) $OPT \geq g$ . まず、区間 $I_{j_{1}}, \dots, I_{j_{g}}$ がどの 2 つも共通部分をもたないことを示す。 $1 \leq k < m \leq g$ とする。(3) より $p$ は増加列なので $p_{k} \leq p_{m - 1}$ であり、また (3) を $k$ の代わりに $m - 1$ に用いて $l_{j_{m}} > p_{m - 1}$ である。よって
$r_{j_{k}} = p_{k} \leq p_{m - 1} < l_{j_{m}}$
となり、 $I_{j_{k}}$ のどの点も $I_{j_{m}}$ のどの点より小さい。したがって $I_{j_{k}} \cap I_{j_{m}} = \emptyset$ である。

任意の刺し集合 $T$ をとる。各 $k = 1, \dots, g$ について $T \cap I_{j_{k}} \neq = \emptyset$ なので、 $I_{j_{k}}$ に含まれる $T$ の要素を 1 つ選び $t_{k}$ とする。 $k \neq = m$ ならば $t_{k} \in I_{j_{k}}$ , $t_{m} \in I_{j_{m}}$ で、 $I_{j_{k}}$ と $I_{j_{m}}$ は共通部分をもたないから $t_{k} \neq = t_{m}$ である。よって $t_{1}, \dots, t_{g}$ は $T$ の相異なる $g$ 個の要素であり、 $∣ T ∣ \geq g$ が成り立つ。 $T$ は任意なので $OPT \geq g$ である。

結論. アルゴリズムは停止し、出力 $S$ は要素数 $g$ の刺し集合であり、(3), (4) より $g = OPT$ が成り立つ。 $■$

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる