最初の道具 — 貪欲法
あなたはバイトの配達員。地図アプリは故障している。
持っている情報は紙の地図と「今いる場所」だけ。
さて、次にどの店に行く?
たぶん 99% の人がこう言うはず —— 「一番近い店」。
これだ。
これが 貪欲法 (Greedy Algorithm) の精神そのものだ。
「その瞬間、一番良さそうな選択肢を、ただ取り続ける」 —— たったそれだけのアルゴリズム。 人類が最初に思いつく解法であり、そして、半世紀後も現役で使われている解法でもある。
2.1 やってみよう: 第1章の 5 軒問題
覚えてる? 第1章の 5 軒の配達。
営業所から A〜E を回って、また営業所に戻る。
最近傍法 (Nearest Neighbor) で順番を作ってみよう。
頭の中で実行してみよう:
- 営業所から最近いのは E。E に行く。
- E から残り (A,B,C,D) で最近いのは A。
- A から残り (B,C,D) で最近いのは B。
- B から残り (C,D) で最近いのは C。
- 残り D。仕方なく行く。
- 営業所に戻る。
できた。コードを書くなら、10 行に収まる。
def nearest_neighbor(start, points, dist):
tour = [start]
unvisited = set(points) - {start}
while unvisited:
last = tour[-1]
nxt = min(unvisited, key=lambda p: dist(last, p))
tour.append(nxt)
unvisited.remove(nxt)
tour.append(start)
return tourこれで TSP の解が出る。100 軒でも 1,000 軒でも一瞬。
…問題は解の質だ。
2.2 貪欲法のお決まりの失敗
図 2.1 をもう一度見てほしい。 最後の D → 営業所の線がやたら長い。
これが貪欲法の典型的な失敗パターン。
序盤に楽な選択肢ばかり食ってしまい、終盤に詰む。
ピザのテーブルの上のチーズだけ最初に食べていって、最後に冷めた生地だけ残る、あの感じ。
じゃあ最近傍法はダメな子なのか? 違う。
- 計算が速い (
O(n²)) - 実装が短い
- 大体の問題で、最適から25% 増し程度には収まる
- 「とりあえずの基準線」として超優秀
この性質を活かして、貪欲法は「最終解」ではなく「初期解」として使われることが多い。 本書の後の章で見るどんな高級な手法も、最初の一手はだいたい貪欲だ。
2.3 もう一つの貪欲: 挿入法
最近傍法は「経路の先端から延ばす」貪欲だった。
これとは違うやり方もある。挿入法 (Insertion Heuristic)。
こちらは「小さな輪っかから始めて、外側を太らせていく」イメージ。
最近傍法と挿入法の違いは 解の作り方の哲学そのものだ:
最近傍法
「経路の端っこから伸ばす」
序盤に楽 → 終盤に詰む
挿入法
「全体の形を保ちながら膨らます」
各段階で全体に気を配るので、最終形がきれい
挿入法のほうが解の質は良いことが多い。配送計画 (VRP) のソフトウェアでは、 今もこの「挿入」が中核として動いている。
2.4 工場でも貪欲は現役: ディスパッチ規則
場面を変えよう。今度は工場の現場。
ジョブが 5 個。機械は 1 台。どの順番で流す?
こんな状況だ:
| ジョブ | 処理時間 | 納期 |
|---|---|---|
| J1 | 4 時間 | 10 時 |
| J2 | 2 時間 | 14 時 |
| J3 | 1 時間 | 6 時 |
| J4 | 3 時間 | 12 時 |
| J5 | 5 時間 | 20 時 |
「平均で早く終わらせたい」と「納期に間に合わせたい」では、選ぶ順番が変わる。
工場で何十年も使われてきた、3 つの「貪欲ルール」を紹介する。
SPT (Shortest Processing Time): 処理時間が短い順
→ J3 (1h), J2 (2h), J4 (3h), J1 (4h), J5 (5h)
「平均完了時刻」を最小化する。これは数学的に証明された最適手だ。
EDD (Earliest Due Date): 納期が早い順
→ J3 (6時), J1 (10時), J4 (12時), J2 (14時), J5 (20時)
「最大の遅刻」を最小化する。これも証明可能で最適。
WSPT (重み付き SPT): 「重要度 ÷ 処理時間」が大きい順
重み付き完了時刻の最小化に効く。
ここで奇跡が起きている。
SPT も EDD も貪欲法なのに、ちゃんと最適なのだ。
さっきの TSP では「貪欲はダメ子」と言ったのに?
これにはちゃんと理由がある。問題に**「貪欲が最適になる隠れた構造」があるのだ。 それをマトロイド**と呼ぶ。
2.5 マトロイド — 貪欲が最適になる「秘密の構造」
ここはちょっと数学っぽい話。読み飛ばしても本書のあとの章には支障ない。
でも「なぜ SPT は最適で、Nearest Neighbor は最適じゃないのか」が腑に落ちると、 かなり気持ちいいので、軽く目を通しておくのをおすすめする。
直感的に説明する。
「集合を独立 / 独立でない」と判定するルールがあって、それが次の二つを満たすとき、
その構造を マトロイド と呼ぶ:
- 独立な集合の部分集合も独立。 (一部だけ取っても問題ない)
- もし独立集合 A より大きな独立集合 B があれば、B の中に「A に加えても独立を保つ要素」が存在する。 (拡張できる)
わかりやすい例:
グラフの「森 (= サイクルを含まない辺集合)」はマトロイドだ。
だから最小全域木は Kruskal の貪欲法で最適に解ける (これは多くの人が見たことあるはず)。
シングル機械の SPT も同じ構造。
TSP の経路はマトロイドではない。だから貪欲では最適にならない。
言いたいのはこれ:
「貪欲がうまくいくか」は気分の問題じゃない。問題の構造が決めている。
2.6 貪欲を強くする 3 つのトリック
貪欲がそのままじゃ届かない問題でも、ちょい足しで強くする手がある。
① ランダム化 (GRASP)
「最良の候補だけ取る」のではなく、「上位 α% からランダムに取る」。
同じ問題に対して毎回違う解が出るので、何回か回して一番いいのを採用する。
② 後悔値で選ぶ (Regret-based)
「後回しにすると最大の損をする要素」から処理する。
配送計画でよく使う発想。「めっちゃ遠い顧客は早めに組み込まないと、後で苦しむ」。
③ ビームサーチ
1 本の道を伸ばすかわりに、k 本の道を並行で伸ばす。
k=1 が普通の貪欲、k=∞ が全探索。途中の k がスイートスポット。
2.7 名作: VRP の Clarke–Wright 節約法
1964 年に発表された貪欲法のなかで、今も現役のレジェンドを紹介する。
配送計画 (CVRP) でほぼ全ての商用ソフトが初期解生成に使う、Clarke–Wright 節約法。
あなたは配送センターの所長。10 軒の配達先がある。
最初の発想: 「車を 10 台用意して、各車が 1 軒担当」。
これは絶対に実行可能だけど、絶対にバカ。
次の発想: 「2 軒を 1 台にまとめたら、どれだけ走行距離が減る?」
これがアイデアの核だ。
2 軒 i, j をひとつのルートに合体したときの節約値:
s(i, j) = (車庫→i の距離) + (車庫→j の距離) − (i→j の距離)
これを全ペア計算して、節約値が大きい順にどんどん合体させていく。
ただし、車の積載量を超えないように。
これだけ。コードにしてざっくり 40 行。
それでも最適解の 5〜15% 増しに収まる。1964 年から不滅。
2.8 で、貪欲は本番で使うの?
ここまで読むと、「貪欲は弱い! でも実は強い場面もある!」と整理がつかないかもしれない。
結論はこう:
最終解として貪欲だけを使うのは、たいてい NG。
だが、本気のシステムの中では貪欲は必ず使われる。
- 📌 初期解の生成: 局所探索もメタヒューリスティクスも、最初に貪欲を呼ぶ。
- 📌 下界・上界の即席計算: 「ベンチマークの基準線」。
- 📌 緊急時のフォールバック: 高級アルゴリズムがタイムアウトしても、貪欲なら必ず動く。
- 📌 説明可能性: 「SPT 順です」は現場に説明できる。これは強い。
2.9 この章の振り返り
- 貪欲法は「その瞬間ベストを選び続ける」シンプルな解法。
- 多くの問題でそのまま使うと終盤に詰む。最寄りばかり食う罠。
- でも SPT や Kruskal のように、問題の構造 (マトロイド) があれば最適になる。
- 挿入法、GRASP、Regret、Beam Search は貪欲の発展形。
- Clarke–Wright のような名作は今も現役。シンプルが勝つことはある。
- 本番では「初期解 / 下界 / フォールバック / 説明」として貪欲が支える。
さて、貪欲で初期解はできた。でもこれは「終盤詰みの解」。
次の章では、この解を磨く方法を覚える。
入れ替えてみる。逆にしてみる。それで良くなれば採用する。 これが 局所探索だ。