貪欲法(greedy algorithm)とは、解を要素 1 つずつの選択で組み立て、各段でその時点の評価が最もよい要素を選び、選んだものを取り消さない方法である。区間を終わりの早い順に選ぶ方法、仕事を処理時間と重みの比の順に並べる方法、額が整除の連鎖をなす硬貨の両替では最適解を出し、交換論法と先行し続ける議論で証明できる。最適でない問題でも、単調な劣モジュラ関数を $k$ 個で最大化するときは最適値の $1-1/e$ 倍以上を保証する。
貪欲法(greedy algorithm)は、解を 1 つずつの要素の選択で組み立て、各段でその時点で最もよく見える要素を選び、一度選んだものを取り消さない方法である。将来の選択への影響を考えないので、手順は短く速い。その代わり、最適解を出すかどうかは問題の構造しだいで、出さない問題も多い。
たとえば 1 円・3 円・4 円の硬貨で 6 円を払うとき、いちばん大きい硬貨から使うと $4+1+1$ の 3 枚になるが、$3+3$ なら 2 枚で済む。一方、1・5・10・50・100・500 円の硬貨なら、大きい硬貨から使う払い方がいつも枚数最小になる(thm-gr-coins)。違いは硬貨の額の並び方にある。
貪欲法の数学は、どんな構造のもとで局所的な選択が全体の最適につながるかを調べることである。この記事では、枠組みを定義し、正しさを示す 2 つの型(先行し続ける議論と交換論法)を区間の選択(thm-gr-interval)と重み付き完了時刻(thm-gr-smith)で示し、硬貨の両替が最適になる十分条件(thm-gr-coins)を証明する。最適でない場合の保証として、単調な劣モジュラ関数の最大化で最適値の $1-1/e$ 倍以上が得られること(thm-gr-submod)を証明する。重みつきの独立系で貪欲法がいつも最適になる構造が マトロイド に限ることは Rado–Edmondsの定理 の主題で、この記事では主張だけを述べる。
有限集合 $E$ と、$E$ の部分集合の族 $\mathcal F$ を考える。$\mathcal F$ の元を 実行可能な部分解 と呼び、$\emptyset\in\mathcal F$ とする。目的は $\mathcal F$ の元のうち評価の最もよいものを求めることである。
$S\subset E$ と $e\in E\setminus S$ に実数の 評価 $\mathrm{key}(e\mid S)$ が与えられているとする。次の手順を 貪欲法 という。
$S:=\emptyset$ から始め、$S\cup\{e\}\in\mathcal F$ となる $e\in E\setminus S$ があるあいだ、その中で $\mathrm{key}(e\mid S)$ が最大の $e$ を 1 つ選び(同点は固定した規則で決める)、$S:=S\cup\{e\}$ とする。そのような $e$ がなくなるか、決めた回数に達したら $S$ を出力する。
評価が $S$ によらない $\mathrm{key}(e)$ のとき 固定順の貪欲法 という。このときは $E$ を評価の大きい順に一度並べ、順に見て $S\cup\{e\}\in\mathcal F$ なら加える、という 1 回の走査と同じである。評価が $S$ に依存するときは 適応的な貪欲法 という。
固定順の例は 最小全域木 の Kruskal 法(辺を軽い順に見て閉路を作らなければ加える)で、Rado–Edmondsの定理 の定義「貪欲法」もこの形である。適応的な例は、まだ覆っていない要素を最も多く覆う集合を選ぶ集合被覆の貪欲法(近似アルゴリズム)や、確定した頂点からの距離を毎回更新する Dijkstra法 である。
貪欲法の正しさを示すときは、次の 2 つの型がよく使われる。
| 問題 | 貪欲法の規則 | 結果 | 根拠 |
|---|---|---|---|
| 区間の最大の交わらない部分族 | 終わりの早い順 | 最適 | thm-gr-interval |
| 1 台の機械の重み付き完了時刻の和 | $p_j/w_j$ の小さい順 | 最適 | thm-gr-smith |
| 硬貨の両替(額が整除の連鎖) | 大きい硬貨から | 枚数最小 | thm-gr-coins |
| 硬貨の両替(1・3・4 円) | 大きい硬貨から | 最小でない | ex-gr-coins |
| 独立系の最大重みの独立集合 | 重い順 | すべての非負の重みで最適 $\iff$ マトロイド | Rado–Edmondsの定理 |
| 最小全域木 | Kruskal 法・Prim 法 | 最適 | 最小全域木 |
| 非負の長さの最短路 | Dijkstra 法 | 最適 | Dijkstra法 |
| 接頭符号の平均の長さ | 最も小さい 2 つを併合 | 最適 | Huffman符号 |
| 分割してよいナップサック | 価値と大きさの比の大きい順 | 最適 | ナップサック問題 |
| 集合被覆 | 新しく覆う個数の最大 | 最適値の $H_n$ 倍以下 | 近似アルゴリズム |
| 単調劣モジュラ関数の $k$ 個の最大化 | 増分の最大 | 最適値の $1-(1-1/k)^k$ 倍以上 | thm-gr-submod |
| 頂点の彩色 | 順に、使える最小の色 | 色数 $\le\Delta+1$、順序しだいで多すぎる | 彩色数 |
$H_n=1+\frac12+\dots+\frac1n$、$\Delta$ はグラフの最大次数である。表の「最適」は、どの入力でも最適解を出すという意味である。
$n$ 個の半開区間 $I_j=[s_j,f_j)$($s_j< f_j$、$j=1,\dots,n$)が与えられ、互いに交わらない区間をできるだけ多く選びたいとする。会議室の予約で、使える時間帯の申し込みを最も多く受ける問題である。半開区間にしたので、$f_i=s_j$ の 2 つは交わらない。
終わりの早い順の貪欲法:区間を $f_j$ の小さい順に並べ、順に見て、すでに選んだ区間と交わらなければ選ぶ。選んだ区間の終わりはこの順に増えるので、「交わらない」は「始まりが最後に選んだ区間の終わり以上」と同じである。
終わりの早い順の貪欲法が選ぶ区間の個数は、互いに交わらない部分族の個数の最大値に等しい。
貪欲法が選んだ区間を $g_1,\dots,g_k$、互いに交わらない最大の部分族を $o_1,\dots,o_m$ とし、どちらも終わりの小さい順に並べる。区間 $I$ の始まりと終わりを $s(I)$、$f(I)$ と書く。
まず、交わらない 2 区間 $[a,b)$、$[c,d)$ で $b\le d$ なら $b\le c$ である。実際、交わらないので $b\le c$ か $d\le a$ であり、$d\le a$ なら $b\le d\le a< b$ となって矛盾する。したがって $f(o_r)\le s(o_{r+1})$ である。
次に、$r\le\min(k,m)$ について $f(g_r)\le f(o_r)$ を $r$ の帰納法で示す。$r=1$ では、$g_1$ はすべての区間の中で終わりが最小なので成り立つ。$r$ で成り立つとすると
$$
f(g_r)\le f(o_r)\le s(o_{r+1})
$$
である。貪欲法が $g_r$ を選んだあと選べる区間は、始まりが $f(g_r)$ 以上の区間である。そのような区間 $J$ は $f(J)>s(J)\ge f(g_r)$ をみたすので、並べた順で $g_r$ より後にある。貪欲法はその中で最初のもの、つまり終わりが最小のものを $g_{r+1}$ に選ぶ。$o_{r+1}$ はこの候補に入るから、$r+1\le k$ なら $f(g_{r+1})\le f(o_{r+1})$ である。
最後に $k\ge m$ を示す。$k< m$ と仮定すると、上の不等式から $f(g_k)\le f(o_k)\le s(o_{k+1})$ なので、$o_{k+1}$ は $g_k$ のあとでも選べる区間であり、貪欲法は $k$ 個で止まらない。これは矛盾である。$m$ は最大値なので $k\le m$ でもあり、$k=m$ である。$\square$
同じ区間の問題でも、規則を「長さの短い順」や「始まりの早い順」に替えると最適でなくなる(「使える条件と反例」の表)。証明で使ったのは、終わりが早いほど後に残る選択肢が多いという性質だけである。
1 台の機械で仕事 $1,\dots,n$ を 1 つずつ処理する。仕事 $j$ の処理時間を $p_j>0$、重みを $w_j>0$ とする。処理の順 $\sigma$ を決めると、仕事 $j$ の完了時刻 $C_j$ はそれ以前の仕事と $j$ 自身の処理時間の和である。$\sum_jw_jC_j$ を最小にしたい。たとえば $w_j$ を顧客の人数とすれば、全員の待ち時間の和である。
比の順の貪欲法:$p_j/w_j$ の小さい順に処理する。
$p_j/w_j$ の小さい順(同じ比の仕事の順は任意)に処理すると、$\sum_jw_jC_j$ は最小になる。逆に、隣り合う 2 つの仕事 $a$、$b$($a$ が先)で $p_a/w_a>p_b/w_b$ となる順は最適でない。
隣り合う $a$、$b$($a$ が先)を入れ替えると、ほかの仕事の完了時刻は変わらない。$a$ の完了時刻は $p_b$ だけ増え、$b$ の完了時刻は $p_a$ だけ減るので、目的関数の変化は
$$
w_ap_b-w_bp_a
$$
である。$p_a/w_a>p_b/w_b$ なら $p_aw_b>p_bw_a$ なので変化は負で、入れ替えると真に改善する。これで後半が示された。
処理の順は有限個なので、最小値を与える順 $\sigma^*$ がある。後半により、$\sigma^*$ では隣り合うどの 2 つも比が小さい順(等しくてもよい)に並んでいる。隣り合う順で比が減らないので、$\sigma^*$ 全体で比は小さい順に並ぶ。
比の小さい順に並ぶ 2 つの順 $\sigma,\tau$ は、比の等しい仕事の塊の中の並べ替えだけが違う。塊の中の並べ替えは隣り合う 2 つの入れ替えの繰り返しで実現でき、比が等しい $a,b$ では $w_ap_b-w_bp_a=0$ なので、入れ替えで値は変わらない。したがって比の小さい順に並ぶ順はどれも $\sigma^*$ と同じ値で、最適である。$\square$
$w_j$ がすべて等しいときは処理時間の短い順になる。ex-gr-smith に数値の例がある。
額 $1=d_1< d_2< \dots< d_m$ の硬貨がそれぞれいくらでも使えるとし、金額 $N\ge0$ をできるだけ少ない枚数で払いたい。払い方は非負整数の組 $(c_1,\dots,c_m)$ で $\sum_ic_id_i=N$ をみたすもの、枚数は $\sum_ic_i$ である。大きい硬貨からの貪欲法 は、$c_m:=\lfloor N/d_m\rfloor$ とし、残り $N-c_md_m$ に同じことを $d_{m-1},\dots,d_1$ の順に繰り返す。
各 $i< m$ で $d_i$ が $d_{i+1}$ を割り切るとする。このとき、枚数最小の払い方はただ 1 つで、大きい硬貨からの貪欲法の払い方に一致する。
$(c_1,\dots,c_m)$ を枚数最小の払い方とし、$q_i:=d_{i+1}/d_i$($i< m$)とおく。$q_i$ は 2 以上の整数である。
段 1:$i< m$ について $c_i\le q_i-1$ である。実際、$c_i\ge q_i$ なら、額 $d_i$ の硬貨 $q_i$ 枚を額 $d_{i+1}$ の硬貨 1 枚に替えても金額は同じで、枚数は $q_i-1\ge1$ 枚減る。これは最小性に反する。
段 2:$1\le j\le m$ について、額 $d_j$ より小さい硬貨の合計額は
$$
\sum_{i< j}c_id_i\le\sum_{i< j}(q_i-1)d_i=\sum_{i< j}(d_{i+1}-d_i)=d_j-d_1=d_j-1
$$
である(和は $d_{i+1}-d_i$ の項が打ち消し合う)。
段 3:$N_j:=\sum_{i\le j}c_id_i$ とおくと $N_m=N$ で、$N_j=c_jd_j+N_{j-1}$、段 2 より $0\le N_{j-1}\le d_j-1$ である。これは $N_j$ を $d_j$ で割った商が $c_j$、余りが $N_{j-1}$ であることを意味する。よって上から順に
$$
c_m=\lfloor N/d_m\rfloor,\quad N_{m-1}=N-c_md_m,\quad c_{m-1}=\lfloor N_{m-1}/d_{m-1}\rfloor,\ \dots
$$
と決まり、これは貪欲法の払い方そのものである。枚数最小の払い方は存在する(枚数は非負整数)ので、それはただ 1 つで貪欲法の払い方に等しい。$\square$
日本の硬貨 $1,5,10,50,100,500$ は整除の連鎖なので、定理が当てはまる。整除の連鎖は十分条件で、必要条件ではない(ex-gr-coins の $1,2,5$)。連鎖でない $1,3,4$ では貪欲法が最小でない。
貪欲法が最適解を出さない問題でも、最適値の一定の割合を保証できることがある。その代表が、収穫逓減の性質をもつ集合関数の最大化である。
有限集合 $E$ 上の関数 $f\colon2^E\to\mathbb{R}$ で $f(\emptyset)=0$ のものを考え、$e\notin S$ について 増分 を $\Delta(e\mid S):=f(S\cup\{e\})-f(S)$ とおく。
劣モジュラ性は「すでに多く持っているほど、1 つ足したときの増え方は小さい」という性質である。これは、すべての $S,T\subset E$ で $f(S)+f(T)\ge f(S\cup T)+f(S\cap T)$ が成り立つことと同値である。マトロイド の階数関数はこの形の不等式をみたす。
不等式から増分の形へ:$S\subset T$、$e\notin T$ のとき、不等式を $S\cup\{e\}$ と $T$ に当てると、和集合は $T\cup\{e\}$、共通部分は $S$ なので $f(S\cup\{e\})+f(T)\ge f(T\cup\{e\})+f(S)$ となり、移項すれば $\Delta(e\mid S)\ge\Delta(e\mid T)$ である。
増分の形から不等式へ:$T\setminus S=\{t_1,\dots,t_r\}$ とし、$U_j:=\{t_1,\dots,t_{j-1}\}$ とおく。$(S\cap T)\cup U_j\subset S\cup U_j$ なので、$f(S\cup T)-f(S)=\sum_{j=1}^r\Delta(t_j\mid S\cup U_j)\le\sum_{j=1}^r\Delta\bigl(t_j\mid(S\cap T)\cup U_j\bigr)=f(T)-f(S\cap T)$ である。最後の等号は $(S\cap T)\cup(T\setminus S)=T$ による。$\square$
$f$ が単調かつ劣モジュラで $f(\emptyset)=0$ なら、$\mathrm{OPT}:=\max\{f(O)\mid\lvert O\rvert\le k\}$ について
$$
f(S_k)\ge\left(1-\left(1-\frac1k\right)^k\right)\mathrm{OPT}\ge\left(1-\frac1e\right)\mathrm{OPT}
$$
が成り立つ。$1-1/e=0.6321\ldots$ である。
$O$ を $\lvert O\rvert\le k$ で $f(O)=\mathrm{OPT}$ となる集合とし、$0\le t< k$ を固定する。$O\setminus S_t=\{o_1,\dots,o_p\}$ とおくと $p\le k$ である。
単調性から $\mathrm{OPT}=f(O)\le f(O\cup S_t)$ である。右辺を 1 つずつ足していく和に分けると
$$
f(O\cup S_t)=f(S_t)+\sum_{j=1}^p\Delta\bigl(o_j\mid S_t\cup\{o_1,\dots,o_{j-1}\}\bigr)\le f(S_t)+\sum_{j=1}^p\Delta(o_j\mid S_t)
$$
となる。不等号は劣モジュラ性($S_t\subset S_t\cup\{o_1,\dots,o_{j-1}\}$)による。貪欲法の選び方から各 $j$ で $\Delta(o_j\mid S_t)\le\Delta(e_{t+1}\mid S_t)$ であり、単調性から $\Delta(e_{t+1}\mid S_t)\ge0$ なので、
$$
\mathrm{OPT}\le f(S_t)+p\,\Delta(e_{t+1}\mid S_t)\le f(S_t)+k\bigl(f(S_{t+1})-f(S_t)\bigr)
$$
である。$a_t:=\mathrm{OPT}-f(S_t)$ とおくと、これは $a_t\le k(a_t-a_{t+1})$、つまり
$$
a_{t+1}\le\left(1-\frac1k\right)a_t
$$
を意味する。$a_0=\mathrm{OPT}-f(\emptyset)=\mathrm{OPT}$ なので、$k$ 回くり返して $a_k\le(1-1/k)^k\,\mathrm{OPT}$、すなわち最初の不等式を得る。$\mathrm{OPT}\ge0$(単調性と $f(\emptyset)=0$)と、$1-x\le e^{-x}$ を $x=1/k$ に使った $(1-1/k)^k\le e^{-1}$ から、2 つ目の不等式が出る。$\square$
$k=1$ では係数は $1$ で、貪欲法は最適である。$k=2$ では $3/4$、$k=3$ では $19/27=0.7037\ldots$ で、$k$ とともに $1-1/e$ に減っていく。この型の保証は Nemhauser–Wolsey–Fisher による(WS11 の第 2 章の注、p. 63)。証明の骨組みは WS11 §2.5 の Theorem 2.16(p. 48)の議論と同じで、そこでは被覆関数に近い特別な関数を扱い、一般の単調劣モジュラ関数への拡張は Exercise 2.10(p. 60)に回されている。上の証明はその拡張を書き下した形である。
単調性と劣モジュラ性のどちらを外しても、保証は成り立たなくなる(ex-gr-submod-counter)。
新しい問題に貪欲法を当てるときは、次の順で考える。
区間 $[1,4)$、$[3,5)$、$[0,6)$、$[5,7)$、$[3,9)$、$[5,9)$、$[6,10)$、$[8,11)$、$[8,12)$、$[2,14)$、$[12,16)$ から互いに交わらないものを選ぶ。終わりの早い順に見ると、$[1,4)$ を選び、始まりが $4$ 以上で終わりの最も早い $[5,7)$、続いて $[8,11)$、$[12,16)$ を選ぶ。4 個で、thm-gr-interval によりこれが最大である。
仕事 A, B, C, D の(処理時間, 重み)を $(3,1)$、$(1,2)$、$(2,1)$、$(4,3)$ とする。比 $p_j/w_j$ は $3$、$0.5$、$2$、$1.33\ldots$ なので、thm-gr-smith の順は B, D, C, A で、完了時刻は $1,5,7,10$、目的関数は $2\cdot1+3\cdot5+1\cdot7+1\cdot10=34$ である。重みを無視して処理時間の短い順 B, C, A, D にすると、完了時刻は $1,3,6,10$ で $2\cdot1+1\cdot3+1\cdot6+3\cdot10=41$ になる。
枚数最小の払い方 $(c_1,c_2,c_5)$ をとる。1 円が 2 枚あれば 2 円 1 枚に、2 円が 3 枚あれば 5 円と 1 円の 2 枚に替えて枚数が減るので、$c_1\le1$、$c_2\le2$ である。さらに $c_1=1$、$c_2=2$ なら $1+2+2=5$ を 5 円 1 枚に替えて枚数が減るので、この組は起こらない。よって 1 円と 2 円の合計額は $4$ 以下で、prf-gr-coins の段 3 と同じ議論で $c_5=\lfloor N/5\rfloor$ である。残り $R\le4$ を $c_1\le1$ で払うので $c_2=\lfloor R/2\rfloor$、$c_1=R-2c_2$ となり、貪欲法の払い方に一致する。$\square$
$A_1=\{1,2,3,4\}$、$A_2=\{5,6,7,8\}$、$A_3=\{1,2,5,6,9\}$ から 2 個を選んで覆う要素を最大にする。貪欲法は最も大きい $A_3$(5 個)を選び、次にどちらを足しても 2 個増えるので合計 7 個になる。最大は $A_1\cup A_2$ の 8 個である。比は $7/8$ で、thm-gr-submod の $k=2$ の下界 $3/4$ 以上である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 区間を終わりの早い順に見る(長さの短い順にする) | $[0,4)$、$[3,5)$、$[4,8)$ | 短い $[3,5)$ が両側と交わり 1 個、最大は 2 個(thm-gr-interval) |
| 区間を終わりの早い順に見る(始まりの早い順にする) | $[0,10)$、$[1,2)$、$[3,4)$ | 1 個しか選べず、最大は 2 個(thm-gr-interval) |
| 重みで割った比の順 | ex-gr-smith で処理時間の短い順 | 41 で最小の 34 より大きい(thm-gr-smith) |
| 額が整除の連鎖 | 額 $1,3,4$ で 6 | 3 枚で最小の 2 枚より多い(thm-gr-coins) |
| 劣モジュラ性 | ex-gr-submod-counter の 1 | 比 $\varepsilon$ で、$1-1/e$ 倍の保証が成り立たない(thm-gr-submod) |
| 単調性 | ex-gr-submod-counter の 2 | 比 $2/3$ で、$k=2$ の保証 $3/4$ を下回る(thm-gr-submod) |
どちらも $E=\{a,b,c\}$、$k=2$ とする。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 局所的に最もよい選択を重ねれば最適になる | 問題の構造による。最適でない例は多い | ex-gr-coins の 2 |
| 小さい例で合えば正しい | 交換論法などの証明が要る | 反例の表の区間の規則 |
| 区間は短い順か始まりの早い順でよい | 終わりの早い順でなければ最適でない | thm-gr-interval |
| 硬貨の額が整除の連鎖でなければ貪欲法は失敗する | 連鎖は十分条件にすぎない | ex-gr-coins の 3 |
| $1-1/e$ の保証はどの集合関数でも成り立つ | 単調性と劣モジュラ性の両方が要る | ex-gr-submod-counter |
$\mathcal F$ が部分集合で閉じた族(独立系)で、目的が要素の重みの和の最大のとき、固定順の貪欲法がすべての非負の重みで最適解を出すことと、$\mathcal F$ が マトロイド であることは同値である。これが Rado–Edmondsの定理 で、最小全域木 の Kruskal 法の正しさはその特別な場合である。区間の選択や硬貨の両替のように、族がマトロイドでなくても特定の重みや規則で貪欲法が最適になる問題はあり、上の定理はそうした場合を個別に扱っている。
交換論法の型と、区間の選択の交換論法による証明(Lemma 4.3・Theorem 4.4)、重み付きの並べ方(Lemma 4.2)は Eri19 第 4 章(§4.1–4.3、pp. 159–165)にある。prf-gr-interval の先行し続ける議論による証明、thm-gr-coins の証明と ex-gr-submod-counter の 2 つの関数はこの記事で組み立てた。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する