マトロイドと貪欲法 | 離散数学 II

1 独立集合系と重み

定義 1.1. 有限集合 $E$ と $\mathcal I\subseteq 2^{E}$ の組 $(E,\mathcal I)$ が有限独立集合系 (finite independence system) であるとは、次の二条件を満たすことをいう。

(I1) $\emptyset\in\mathcal I$ 。
(I2) $A\in\mathcal I$ かつ $B\subseteq A$ ならば $B\in\mathcal I$ 。

有限独立集合系においても、包含に関して極大な $\mathcal I$ の元を基底 (basis) とよぶ。

有限独立集合系とは、§E13.15 定義 1.1の三条件のうち増大公理§E13.15 定義 1.1 条件 (c)を要求しないものである。したがってマトロイドはつねに有限独立集合系である。一般の有限独立集合系では、基底の濃度は一つに定まらない。濃度が一つに定まることは§E13.15 命題 2.3が保証する性質であり、そこでは増大公理を用いている。

定義 1.2. 有限集合 $E$ 上の関数 $w:E\to[0,\infty)$ を非負重み (nonnegative weight) という。 $A\subseteq E$ に対し $w(A)=\sum_{x\in A}w(x)$ を $A$ の重み (weight) という。空集合の重みは $0$ と定める。

2 貪欲アルゴリズム

定義 2.1. 有限独立集合系 $(E,\mathcal I)$ と非負重み $w:E\to[0,\infty)$ を入力とする。 $n=\lvert E\rvert$ と置き、 $E$ の元の並べ方 $e_1,e_2,\dots,e_n$ であって $w(e_1)\ge w(e_2)\ge\dots\ge w(e_n)$ を満たすものを一つ選ぶ。同じ重みをもつ元の間の順序は任意であり、この選び方を処理順 (processing order) という。次の手続きを貪欲アルゴリズム (greedy algorithm) という。

$I_0\leftarrow\emptyset;\qquad i\leftarrow1;$ $\textbf{while }i\le n\textbf{ do }\Bigl(\ I_i\leftarrow I_{i-1}\cup\{e_i\}\ \text{（}I_{i-1}\cup\{e_i\}\in\mathcal I\text{ のとき）},\quad I_i\leftarrow I_{i-1}\ \text{（それ以外）};\quad i\leftarrow i+1\ \Bigr);$ $\textbf{return }I_n.$

出力 $I_n$ を、この処理順に対する貪欲解 (greedy solution) という。独立性の判定 $I_{i-1}\cup\{e_i\}\in\mathcal I$ は一回の基本操作として数える。

命題 2.2.定義 2.1の貪欲アルゴリズムは、任意の有限独立集合系と任意の非負重みに対して有限回の反復で停止し、出力 $I_n$ は $(E,\mathcal I)$ の基底である。

証明. 停止性. 変量 $V=n+1-i$ を取る。 $i\le n$ のとき本体を実行すると $i$ が $1$ 増えるから $V$ は狭義に減少し、 $i\le n$ のあいだ $V\ge1\ge0$ である。§D2.8 命題 1.4より手続きは有限回で停止し、停止時には $i=n+1$ である。

不変条件. 述語 $P$ を「 $I_i\in\mathcal I$ が成り立つ」と定める。初期化では $I_0=\emptyset$ であり定義 1.1 条件 (a)より $P$ が成り立つ。維持では、 $I_i=I_{i-1}\cup\{e_i\}$ と更新する場合は条件 $I_{i-1}\cup\{e_i\}\in\mathcal I$ が成り立つときに限られ、 $I_i=I_{i-1}$ と更新する場合は帰納法の仮定から $I_i\in\mathcal I$ が従う。ゆえに $P$ は§D2.8 定義 1.1の意味でのループ不変条件であり、§D2.8 定理 1.2より停止時に $I_n\in\mathcal I$ が成り立つ。

極大性. $I_n$ が包含に関して極大でないと仮定する。 $x\in E\setminus I_n$ が存在して $I_n\cup\{x\}\in\mathcal I$ となる。 $x=e_i$ と書く。手続きは $I_0\subseteq I_1\subseteq\dots\subseteq I_n$ を満たすから $I_{i-1}\subseteq I_n$ であり、 $I_{i-1}\cup\{e_i\}\subseteq I_n\cup\{x\}\in\mathcal I$ であるから定義 1.1 条件 (b)より $I_{i-1}\cup\{e_i\}\in\mathcal I$ である。ゆえに第 $i$ 反復で $e_i$ が採用され $e_i\in I_i\subseteq I_n$ となるが、 $x=e_i\notin I_n$ に反する。ゆえに $I_n$ は極大であり、基底である。▨

3 貪欲アルゴリズムの最適性

3.1 証明方針

貪欲解 $G$ の元を採用した順に $g_1,g_2,\dots,g_r$ と並べる。処理順が重みについて単調非増加であるから、この並びも重みについて単調非増加である。比較の相手となる独立集合 $A$ の元も重みの降順に $a_1,\dots,a_s$ と並べる。

示すべき中間目標は、各添字 $j$ について $w(g_j)\ge w(a_j)$ が成り立つことである。これが得られれば、 $s\le r$ と重みの非負性から $w(A)\le w(G)$ が従う。

中間目標は背理法で示す。 $w(g_j)<w(a_j)$ を満たす $j$ が存在したとする。貪欲解の最初の $j-1$ 個からなる集合 $\{g_1,\dots,g_{j-1}\}$ と、 $A$ の最初の $j$ 個からなる集合 $\{a_1,\dots,a_j\}$ は、いずれも独立であり濃度が $j-1$ と $j$ である。ここで増大公理§E13.15 定義 1.1 条件 (c)を適用すると、後者の元 $x$ であって前者に加えても独立性が保たれるものが得られる。この $x$ の重みは $w(a_j)$ 以上であるから $w(g_j)$ より真に大きく、したがって $x$ は処理順で $g_j$ より前に現れる。 $x$ を走査した時点での部分解は $\{g_1,\dots,g_{j-1}\}$ に含まれるので、遺伝性により $x$ は採用されていたはずである。ところが $x$ は $\{g_1,\dots,g_{j-1}\}$ に属さないので矛盾する。増大公理を適用する位置と、重みの大小から処理順の前後を導く位置が、この証明の二つの要点である。

補題 3.1. $M=(E,\mathcal I)$ をマトロイド、 $w:E\to[0,\infty)$ を定義 1.2の意味の非負重みとし、処理順を一つ固定する。貪欲解 $G$ の元を採用した順に $g_1,\dots,g_r$ と書く。 $A\in\mathcal I$ を任意に取り、その元を重みの降順に $a_1,\dots,a_s$ と並べる。このとき $s\le r$ であり、 $1\le j\le s$ を満たす任意の $j$ に対し $w(g_j)\ge w(a_j)$ が成り立つ。

証明. まず $w(g_1)\ge w(g_2)\ge\dots\ge w(g_r)$ が成り立つ。実際、 $g_j$ は処理順における添字が $g_{j+1}$ より小さい位置で採用されるから、処理順の重みが単調非増加であることより $w(g_j)\ge w(g_{j+1})$ である。

$s\le r$ を示す。命題 2.2より $G$ は基底であり、§E13.15 系 2.4より任意の独立集合の濃度は基底の濃度以下であるから $s=\lvert A\rvert\le\lvert G\rvert=r$ である。

$w(g_j)<w(a_j)$ を満たす $j\in\{1,\dots,s\}$ が存在したとする。 $P=\{g_1,\dots,g_{j-1}\}$ 、 $Q=\{a_1,\dots,a_j\}$ と置く。 $P\subseteq G\in\mathcal I$ かつ $Q\subseteq A\in\mathcal I$ であるから、定義 1.1 条件 (b)より $P,Q\in\mathcal I$ であり、 $\lvert P\rvert=j-1<j=\lvert Q\rvert$ である。

§E13.15 定義 1.1 条件 (c)より $x\in Q\setminus P$ が存在して $P\cup\{x\}\in\mathcal I$ となる。 $x\in Q$ であり $a_1,\dots,a_j$ は重みの降順に並んでいるから $w(x)\ge w(a_j)>w(g_j)$ である。

処理順を $e_1,\dots,e_n$ と書き、 $x=e_p$ 、 $g_j=e_q$ とする。 $w(e_p)>w(e_q)$ であり処理順の重みは単調非増加であるから $p<q$ である。第 $p$ 反復の直前の部分解を $I_{p-1}$ と書くと、 $I_{p-1}$ は第 $p$ 反復より前に採用された元だけからなり、 $p<q$ であるから、それらはすべて第 $q$ 反復より前に採用された元である。貪欲解の元を採用順に並べた列が $g_1,\dots,g_r$ であり $g_j=e_q$ であるから、第 $q$ 反復より前に採用された元は $g_1,\dots,g_{j-1}$ に限られる。ゆえに $I_{p-1}\subseteq P$ である。

したがって $I_{p-1}\cup\{x\}\subseteq P\cup\{x\}\in\mathcal I$ であり、定義 1.1 条件 (b)より $I_{p-1}\cup\{x\}\in\mathcal I$ である。ゆえに第 $p$ 反復で $x$ が採用され、 $p<q$ であるから $x\in\{g_1,\dots,g_{j-1}\}=P$ となる。これは $x\in Q\setminus P$ に反する。

ゆえにすべての $j\in\{1,\dots,s\}$ について $w(g_j)\ge w(a_j)$ が成り立つ。▨

定理 3.2. $M=(E,\mathcal I)$ をマトロイド、 $w:E\to[0,\infty)$ を非負重みとし、処理順を任意に固定する。このとき貪欲解 $G$ は基底であり、任意の $A\in\mathcal I$ に対し $w(A)\le w(G)$ が成り立つ。とくに $G$ は重みが最大の基底である。

証明. $G$ が基底であることは命題 2.2による。

$A\in\mathcal I$ を取り、補題 3.1の記号を用いる。 $s\le r$ かつ $w(g_j)\ge w(a_j)$ （ $1\le j\le s$ ）であるから $w(A)=\sum_{j=1}^{s}w(a_j)\le\sum_{j=1}^{s}w(g_j)\le\sum_{j=1}^{r}w(g_j)=w(G)$ が成り立つ。二つ目の不等号では、 $j>s$ に対する項 $w(g_j)$ が非負であることを用いた。

基底も独立集合であるから、 $G$ は重みが最大の基底である。▨

命題 3.3. $n=\lvert E\rvert$ とする。定義 2.1の貪欲アルゴリズムのループはちょうど $n$ 回反復し、独立性の判定をちょうど $n$ 回行う。したがって独立性の判定を一回の基本操作として数えると、このアルゴリズムの時間計算量は§D2.8 定義 2.2の意味で $O(n)$ である。

証明.命題 2.2の停止性の議論のとおり、変数 $i$ は $1$ から始まり各反復で $1$ ずつ増え、 $i=n+1$ となった時点で停止する。ゆえに本体が実行される回数は $n$ である。各反復では独立性の判定 $I_{i-1}\cup\{e_i\}\in\mathcal I$ をちょうど一回行うから、判定の総数は $n$ である。

判定の回数を基本操作の回数とすると、実行回数は定数 $c=1$ と $n_0=0$ について $n\le c\cdot n$ を満たすから、§D2.8 定義 2.2より $O(n)$ である。▨

処理順を得るためには $E$ の元を重みについて単調非増加に並べる必要があり、その費用は整列の費用である。整列の計算量は先行記事の主題であって本記事の主張には含まれない。命題 3.3は、処理順が与えられた後の反復だけを対象とする評価である。

4 貪欲アルゴリズムの正当性によるマトロイドの特徴づけ

逆向きの主張を述べる。ここで仮定するのは、すべての非負重みと、同順位の任意の処理順に対して貪欲アルゴリズムが正しい答えを出すことである。二つの量化のいずれを落としても、主張は成り立たなくなる。

定理 4.1. $(E,\mathcal I)$ を定義 1.1の意味の有限独立集合系とする。次の二条件は同値である。

$(E,\mathcal I)$ はマトロイドである。
任意の非負重み $w:E\to[0,\infty)$ と、 $w$ に対する任意の処理順について、貪欲解 $G$ が $w(A)\le w(G)$ をすべての $A\in\mathcal I$ について満たす。

証明.(1) $\Rightarrow$ (2)を示す。定理 3.2そのものである。

(2) $\Rightarrow$ (1)を示す。 $(E,\mathcal I)$ は定義 1.1 条件 (a)と定義 1.1 条件 (b)を満たすから、§E13.15 定義 1.1 条件 (c)を示せばよい。

§E13.15 定義 1.1 条件 (c)が成り立たないと仮定する。 $A,B\in\mathcal I$ 、 $\lvert A\rvert<\lvert B\rvert$ であって、すべての $x\in B\setminus A$ について $A\cup\{x\}\notin\mathcal I$ を満たすものが存在する。 $a=\lvert A\rvert$ 、 $b=\lvert B\rvert$ 、 $k=\lvert A\cap B\rvert$ と置く。 $a<b$ より $a+1\le b$ であり、 $A\cap B\subseteq A$ より $k\le a$ である。

$\varepsilon=\dfrac{1}{a+1}$ と置き、非負重み $w$ を $w(x)=\begin{cases}1+\varepsilon&(x\in A)\\ 1&(x\in B\setminus A)\\ 0&(x\in E\setminus(A\cup B))\end{cases}$ と定める。 $\varepsilon>0$ であるから $w$ の値は非負であり、重みの大きさは $A$ の元、 $B\setminus A$ の元、それ以外の元の順に並ぶ。

処理順として、 $A$ の元をすべて先に並べ、次に $B\setminus A$ の元を並べ、最後に $E\setminus(A\cup B)$ の元を並べたものを取る。この並びは重みについて単調非増加であるから定義 2.1の処理順の条件を満たす。

この処理順に対する貪欲解 $G$ を調べる。まず $A$ の元を走査する段では、走査した時点の部分解を $I$ と書くと $I\subseteq A$ であり、次の元 $x\in A$ について $I\cup\{x\}\subseteq A\in\mathcal I$ であるから定義 1.1 条件 (b)より $I\cup\{x\}\in\mathcal I$ であって $x$ は採用される。ゆえに $A$ の走査が終わった時点の部分解は $A$ である。

次に $B\setminus A$ の元 $x$ を走査する。この段の部分解はつねに $A$ である。実際、仮定よりすべての $x\in B\setminus A$ について $A\cup\{x\}\notin\mathcal I$ であるから、どの元も採用されない。

最後に $E\setminus(A\cup B)$ の元が走査されるが、これらの重みは $0$ である。したがって $G\supseteq A$ かつ $G\cap(B\setminus A)=\emptyset$ であり、 $w(G)=w(A)+0=a(1+\varepsilon)=a+a\varepsilon$ である。

一方 $B\in\mathcal I$ であり、 $B$ は $A\cap B$ の元を $k$ 個、 $B\setminus A$ の元を $b-k$ 個含むから $w(B)=k(1+\varepsilon)+(b-k)\cdot1=b+k\varepsilon\ge b\ge a+1$ である。 $a\varepsilon=\dfrac{a}{a+1}<1$ であるから $w(G)=a+a\varepsilon<a+1\le w(B)$ となり、 $w(B)>w(G)$ である。これは(2)に反する。

ゆえに§E13.15 定義 1.1 条件 (c)が成り立ち、 $(E,\mathcal I)$ はマトロイドである。▨

注意 4.2 (二つの量化はいずれも落とすことができない).定理 4.1 (2)から「任意の非負重み」という量化を落とし、ある一つの非負重みに対してだけ貪欲アルゴリズムが正しいことを要求する形にすると、主張は成り立たなくなる。実際、 $w\equiv0$ を取れば、どの有限独立集合系についても任意の出力の重みは $0$ であり、 $\mathcal I$ の元の重みもすべて $0$ であるから、貪欲解はつねに重み最大である。増大公理を満たさない有限独立集合系がこの条件を満たすので、一つの重みだけでは増大公理を導くことができない。

処理順についての量化も、上の証明が実際に用いている。証明で構成した重み $w$ は $A$ の元すべてに同じ値 $1+\varepsilon$ を、 $B\setminus A$ の元すべてに同じ値 $1$ を与えるので、同順位の元が多数存在する。証明は、 $A$ の元を先に走査する処理順を選んでいる。定理 4.1 (2)が「任意の処理順」を要求しているからこそ、この選択が許される。

5 具体例

例 5.1 (一様マトロイドとグラフ的マトロイドにおける貪欲解). 一様マトロイド. $U_{2,4}$ の台集合を $E=\{1,2,3,4\}$ とし、 $w(1)=5$ 、 $w(2)=5$ 、 $w(3)=2$ 、 $w(4)=0$ とする。処理順を $1,2,3,4$ とすると、貪欲アルゴリズムは $1$ を採用し、 $2$ を採用し（ $\{1,2\}$ は二元集合であるから独立）、 $3$ については $\{1,2,3\}$ が三元集合であるから採用せず、 $4$ についても同様に採用しない。出力は $\{1,2\}$ であり重みは $10$ である。 $U_{2,4}$ の基底は二元集合であり、二つの元の重みの和が最大になるのは重み $5$ の二元を選ぶときであるから、 $10$ が最大値である。処理順を $2,1,3,4$ に取り替えても出力は $\{1,2\}$ である。

グラフ的マトロイド. 頂点 $1,2,3,4$ と六本の辺 $a=\{1,2\},\quad b=\{1,3\},\quad c=\{1,4\},\quad d=\{2,3\},\quad e=\{2,4\},\quad f=\{3,4\}$ からなる完全グラフ $K_4$ を取り、重みを $w(a)=4$ 、 $w(b)=2$ 、 $w(c)=5$ 、 $w(d)=3$ 、 $w(e)=1$ 、 $w(f)=6$ とする。処理順は $f,c,a,d,b,e$ である。

$f=\{3,4\}$ を採用する。部分解は $\{f\}$ であり、 $(V,\{f\})$ は閉路をもたない。
$c=\{1,4\}$ を採用する。 $\{f,c\}$ は頂点列 $3,4,1$ の道であり閉路をもたない。
$a=\{1,2\}$ を採用する。 $\{f,c,a\}$ は頂点列 $3,4,1,2$ の道であり閉路をもたない。三辺であるから全域木である。
$d=\{2,3\}$ は採用しない。 $\{f,c,a,d\}$ は頂点列 $2,3,4,1,2$ の長さ $4$ の閉路を含む。
$b=\{1,3\}$ は採用しない。 $\{f,c,b\}$ は頂点列 $1,3,4,1$ の三角形を含む。
$e=\{2,4\}$ は採用しない。 $\{c,a,e\}$ は頂点列 $2,4,1,2$ の三角形を含む。

出力は $\{f,c,a\}$ であり重みは $6+5+4=15$ である。§E13.15 命題 6.3より基底は全域木の辺集合であって濃度は $\lvert V\rvert-1=3$ であるから、どの基底の重みも三つの辺の重みの和である。六本の辺の重みのうち大きい三つは $6,5,4$ であるから、どの基底の重みも $15$ 以下である。ゆえに $15$ が最大値であり、貪欲解は重み最大の基底である。

例 5.2 (増大公理を満たさない系では貪欲アルゴリズムが誤る). $E=\{1,2,3\}$ とし $\mathcal I=\bigl\{\emptyset,\ \{1\},\ \{2\},\ \{3\},\ \{1,2\}\bigr\}$ と置く。 $\emptyset\in\mathcal I$ であり、 $\mathcal I$ の元の部分集合はすべて $\mathcal I$ に属するから、 $(E,\mathcal I)$ は有限独立集合系である。 $A=\{3\}$ 、 $B=\{1,2\}$ とすると $\lvert A\rvert=1<2=\lvert B\rvert$ であるが、 $\{3,1\}$ も $\{3,2\}$ も $\mathcal I$ に属さないので§E13.15 定義 1.1 条件 (c)は成り立たない。

$w(3)=2$ 、 $w(1)=w(2)=\tfrac32$ と定める。重みはすべて相異なるわけではないが、 $w(3)$ が単独で最大であるから、どの処理順でも最初に走査されるのは $3$ である。貪欲アルゴリズムは $3$ を採用し、続く $1$ と $2$ については $\{3,1\}\notin\mathcal I$ 、 $\{3,2\}\notin\mathcal I$ であるから採用しない。出力は $\{3\}$ であり重みは $2$ である。一方 $\{1,2\}\in\mathcal I$ の重みは $3$ であるから、貪欲解は重み最大ではない。

定理 4.1の証明が構成する重みを、この例について計算すると次のようになる。 $a=\lvert A\rvert=1$ であるから $\varepsilon=\tfrac12$ であり、 $w(3)=\tfrac32$ 、 $w(1)=w(2)=1$ 、 $k=\lvert A\cap B\rvert=0$ である。 $A$ を先に走査する処理順に対する貪欲解は $\{3\}$ で重みは $\tfrac32$ であり、 $w(B)=2>\tfrac32$ である。

6 演習

問題 6.1.

命題 2.2の極大性の証明で、 $I_{i-1}\subseteq I_n$ という包含を用いた。この包含が成り立つ理由を、手続きの更新規則から書き下せ。
補題 3.1の証明のうち、 $w(x)>w(g_j)$ から処理順における $x$ の位置が $g_j$ の位置より前であることを導く段を、参照せずに再現せよ。処理順が重みについて単調非増加であることをどこで用いたかを明示せよ。
補題 3.1の証明で、増大公理を適用する独立集合の対を $(\{g_1,\dots,g_{j-1}\},\ \{a_1,\dots,a_j\})$ に取った。この対を $(\{g_1,\dots,g_j\},\ \{a_1,\dots,a_j\})$ に取ると証明が成立しない理由を、濃度の条件に即して述べよ。
定理 3.2の最後の評価で用いた重みの非負性を落とすと、貪欲解が重み最大の独立集合であるという結論が成り立たなくなる例を、 $U_{1,2}$ に負の重みを与えて構成せよ。
定理 4.1 (2)から (1) の証明で構成した重み $w$ について、 $\varepsilon$ を $\dfrac{1}{a+1}$ ではなく $1$ に取ると証明が破綻することを、 $w(G)$ と $w(B)$ の比較によって確かめよ。破綻しない $\varepsilon$ の範囲を求めよ。
定理 4.1 (2)から (1) の証明を、 $B\setminus A$ の元の重みを $1$ ではなく $1-\delta$ （ $\delta>0$ ）に取り替え、重みがすべて相異なるように設計し直せ。 $\delta$ に課すべき条件を書き下せ。
例 5.1のグラフの例で、重み $w(f)$ を $6$ から $1$ へ変更したときの貪欲解を、処理順を明示して求めよ。得られた解が重み最大の全域木であることを、三辺の重みの和の最大値と比較して確かめよ。

7 つまずいたら

貪欲解は最大重みの基底であり、基底は極大独立集合である。二つの語を書き分ける（§E13.15 定義 2.1、定理 3.2）。
出力が基底であることと、出力が重み最大であることは別の主張である。前者は増大公理を用いずに遺伝性だけから従い（命題 2.2）、後者は増大公理を本質的に用いる。
定理 4.1 (2)は、一つの重みや一つの処理順についての条件ではない。二つの量化のうちどちらを落としても主張が成り立たなくなる理由は注意 4.2に述べた。
重みが負の値を取ることを許すと、重み最大の独立集合が基底とは限らなくなる。本記事の主張はすべて非負重みについてのものである。
計算量の評価は、独立性の判定を一回の基本操作として数える計算モデルにおけるものである（命題 3.3）。判定そのものの費用は、マトロイドの与え方に依存する。

8 扱った範囲と次の記事

本記事は、有限独立集合系と非負重みに対する貪欲アルゴリズムを定め、停止性と、出力が基底であることをループ不変条件の枠組みで証明した。マトロイドについては、貪欲解が独立集合全体の中で重み最大であることを、各順位での重みの比較によって証明した。逆に、すべての非負重みとすべての同順位の処理順に対して貪欲解が重み最大である有限独立集合系は増大公理を満たすことを、増大公理の反例から重みを構成して証明した。二つのマトロイドに共通の独立集合を求める問題、重み付きの共通独立集合、および劣モジュラ関数の最大化に対する近似保証は扱っていない。次の記事では、有限有向非巡回グラフとして表される状態と遷移から漸化式を定め、位相順序による評価が各状態の値を正しく与えることを証明する。

§E13.17マトロイドと貪欲法