貪欲法

同義語:貪欲アルゴリズムgreedy algorithm欲張り法

概要

貪欲法(greedy algorithm)とは、解を要素 1 つずつの選択で組み立て、各段でその時点の評価が最もよい要素を選び、選んだものを取り消さない方法である。区間を終わりの早い順に選ぶ方法、仕事を処理時間と重みの比の順に並べる方法、額が整除の連鎖をなす硬貨の両替では最適解を出し、交換論法と先行し続ける議論で証明できる。最適でない問題でも、単調な劣モジュラ関数を $k$ 個で最大化するときは最適値の $1-1/e$ 倍以上を保証する。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 組合せ最適化, 数学的帰納法

貪欲法(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 つの型がよく使われる。

  1. 先行し続ける議論:貪欲法の $r$ 番目までの部分解が、どの最適解の $r$ 番目までと比べても「少なくとも同じだけ進んでいる」ことを $r$ についての帰納法で示し、最後に個数や値を比べる(prf-gr-interval)。
  2. 交換論法:任意の最適解を、値を悪くせずに 1 か所ずつ貪欲法の解に近づけられることを示す。隣り合う 2 つの入れ替えで済むことが多い(prf-gr-smith)。
    どちらも「貪欲法の最初の選択を含む最適解がある」ことと「残りの問題が同じ形の小さい問題になる」ことを使っている。この 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$ の小さい順に並べ、順に見て、すでに選んだ区間と交わらなければ選ぶ。選んだ区間の終わりはこの順に増えるので、「交わらない」は「始まりが最後に選んだ区間の終わり以上」と同じである。

終わりの早い順の貪欲法は最適

終わりの早い順の貪欲法が選ぶ区間の個数は、互いに交わらない部分族の個数の最大値に等しい。

$r$ 番目の終わりを比べる

貪欲法が選んだ区間を $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$ となる順は最適でない。

隣り合う 2 つを入れ替える

隣り合う $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\subset T$ なら $f(S)\le f(T)$ のとき、$f$ は 単調 であるという。
  2. $S\subset T\subset E$、$e\in E\setminus T$ なら $\Delta(e\mid S)\ge\Delta(e\mid T)$ のとき、$f$ は 劣モジュラ であるという(劣モジュラ関数)。

劣モジュラ性は「すでに多く持っているほど、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$


被覆関数 は代表的な例である。$E=\{1,\dots,M\}$ の各 $i$ に有限集合 $A_i$ を対応させ、$f(S):=\left\lvert\bigcup_{i\in S}A_i\right\rvert$ とおく。$\Delta(i\mid S)=\left\lvert A_i\setminus\bigcup_{j\in S}A_j\right\rvert$ で、$S\subset T$ なら引く集合が大きくなるので $\Delta(i\mid S)\ge\Delta(i\mid T)$ である。単調性も明らかである。$k$ 個の集合で最も多くの要素を覆う問題を 最大被覆問題 という。
$k\ge1$ を固定し、$\lvert E\rvert\ge k$ とする。増分最大の貪欲法 は、$S_0:=\emptyset$ から始め、$t=0,1,\dots,k-1$ について $e\notin S_t$ のうち $\Delta(e\mid S_t)$ が最大の $e_{t+1}$ を選び、$S_{t+1}:=S_t\cup\{e_{t+1}\}$ とする。

増分最大の貪欲法の保証

$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$ である。

残りの差が毎回 $1-1/k$ 倍以下に縮む

$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. 部分解と評価を決める:何を 1 つずつ選ぶか(区間、仕事、硬貨、集合)と、選ぶ基準(終わり、比、額、増分)を決める。
  2. 小さい反例を探す:要素 3〜4 個の入力で、貪欲法の出力と総当たりの最適値を比べる。反例が見つかれば、規則を替えるか、近似の保証を調べる段へ進む。
  3. 最初の選択を含む最適解があることを示す:交換論法(prf-gr-smith)か先行し続ける議論(prf-gr-interval)で示す。
  4. 残りが同じ形の問題になることを確かめる:最初の選択を固定した残りの問題が、もとの問題と同じ型で、帰納法が回ることを確かめる。
  5. 計算量を数える:固定順の貪欲法は並べ替えの $O(n\log n)$ と 1 回の走査で済む。適応的な貪欲法は各段の評価の更新に手間がかかり、優先度付きキューなどを使う。
    3 と 4 が示せないときは、動的計画法 が使えるか、または thm-gr-submod のような近似の保証があるかを調べる。

例

会議室の予約

区間 $[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$ になる。

硬貨の 3 つの体系
  1. 日本の硬貨で 2786 円を払うと、貪欲法は 500 円 5 枚、100 円 2 枚、50 円 1 枚、10 円 3 枚、5 円 1 枚、1 円 1 枚の 13 枚で、thm-gr-coins により最小である。
  2. 額 $1,3,4$ で 6 を払うと、貪欲法は $4+1+1$ の 3 枚、最小は $3+3$ の 2 枚である。
  3. 額 $1,2,5$ は整除の連鎖でない($2$ は $5$ を割り切らない)が、貪欲法はどの金額でも枚数最小である。
    証明を開く

    枚数最小の払い方 $(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$ で 63 枚で最小の 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$ とする。

  1. $0< \varepsilon< \frac12$ とし、$f(\emptyset)=0$、$f(\{a\})=\varepsilon$、$f(\{b\})=f(\{c\})=0$、$f(\{a,b\})=f(\{a,c\})=\varepsilon$、$f(\{b,c\})=f(E)=1$ とおく。$f$ は単調だが、$\Delta(c\mid\{b\})=1>0=\Delta(c\mid\emptyset)$ なので劣モジュラでない。貪欲法は最初に増分 $\varepsilon$ の $a$ を選び、次の増分はどれも $0$ なので $f(S_2)=\varepsilon$ で、最大は $f(\{b,c\})=1$ である。
  2. $g(\emptyset)=0$、$g(\{a\})=2$、$g(\{b\})=g(\{c\})=\frac32$、$g(\{a,b\})=g(\{a,c\})=2$、$g(\{b,c\})=3$、$g(E)=2$ とおく。増分は $a$ について $2,\frac12,\frac12,-1$、$b$ について $\frac32,0,\frac32,0$($c$ も同様)と、集合が大きくなると増えないので劣モジュラだが、$g(E)< g(\{b,c\})$ なので単調でない。貪欲法は $a$ を選んだあと増分 $0$ の元しかなく、$g(S_2)=2$、最大は $3$ である。
    1 は劣モジュラ性だけを、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 つの関数はこの記事で組み立てた。

関連項目

参考文献

[1]
David P. Williamson, David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, 頁は著者公開の電子版(2011)のもの:§2.5 Lemma 2.15・Theorem 2.16・Lemma 2.17(pp. 47–49)、Exercise 2.10(p. 60)、第 2 章の Chapter Notes(p. 63)
[2]
Jeff Erickson, Algorithms, 1st paperback edition, Independently published, 2019, 第 4 章 Greedy Algorithms:§4.1 Lemma 4.2(p. 161)、§4.2 Lemma 4.3(p. 163)・Theorem 4.4(p. 164)、§4.3 General Pattern(pp. 164–165)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する