- 物理機リージョン/AZ
- ハイパーバイザVM exit で捕まえる
- VMゲストOS
- コンテナnamespace / cgroup
- プロセスアプリ / DB今ここ
プロセスの中で動く計算の話です。今回は「先を読まずに決めてよい」と言える構造を扱います。
まず結論
貪欲法は「いま一番良く見える手を取り続ける」だけの手法です。速く、書くのも簡単です。
それが正しいのは「最適解の1手目を、貪欲の1手目に入れ替えても損しない」と言えるときに限られます。この性質(貪欲選択性)が無い問題では、貪欲は速く、そして黙って間違えます。
硬貨が 1円・3円・4円 の3種類だけの国で、6円を「大きい硬貨から取れるだけ取る」方法で払うと何枚になり、それは最少でしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
先を読まずに決めてよい、と言えるか
貪欲法は、その時点で一番良く見える手を取り、二度と取り消さない解き方です。おつりなら「払える中で一番大きい硬貨を取る」。先を読まないので速く、書くのも簡単です。
では、いつ正しいのか。鍵になるのは次の問いです。
最適解が1つあるとする。その1手目を、貪欲が選ぶ1手目に入れ替えても損しないか。
入れ替えても最適のままなら、1手目は貪欲どおりに決めてかまいません。残りは「小さくなった同じ問題」なので、同じ問いを繰り返せます。この性質を貪欲選択性、入れ替えで示す考え方を交換論法と呼びます。証明はここでは求めません。「入れ替えられるか」を具体例で試せれば十分です。
- ・入れ替えが言えない問題では、貪欲は答えを返すが最適とは限らない
- ・この判定は自動では行われない。書く人が根拠を持つ必要がある
日本の硬貨では入れ替えが効く
日本の硬貨 {1, 5, 10, 50, 100, 500} で、1〜10,000円の全額を2通りに数えました。大きい順に取る貪欲と、DP の回で扱う表(小さい金額から順に最少枚数を埋める)で求めた最適です(Python 3.14.6 / macOS 26.5.2 / arm64、2026-10-07。Docker の Python 3.14.7 でも同じ枚数)。
JP coins [1, 5, 10, 50, 100, 500], 1..10000: greedy==optimal for 10000 amounts, differs for 0e.g. 9999: greedy 33 dp 33 ; 10000: 20 20
10,000件すべてで一致し、食い違いは0件でした。入れ替えの感覚もつかめます。最適解が1円を5枚使っていたら5円1枚に、10円を5枚使っていたら50円1枚に替えられ、枚数は減ります。大きい硬貨を先に取っても損しない、という入れ替えの直観が、この組では数え上げと合っています。
ただし、これはこの6種類の組についての結果です。数え上げで確かめたのは1〜10,000円の範囲だけで、貪欲法一般の性質ではありません。
{1,3,4} で6円を払うとき、最適解 3+3 の中に貪欲の1手目(4円)を入れ替えて入れられないのはなぜですか。
構造が無いと、貪欲は速く間違える
硬貨を {1, 3, 4} に替えると、同じ手順が崩れます。
| 金額 | 貪欲(大きい順) | 最適(表で求めた) |
|---|---|---|
| 6円 | 4+1+1 = 3枚 | 3+3 = 2枚 |
最適解 3+3 の中に、足して4円になる組がありません。入れ替えられないので、貪欲の1手目(4円)が最適解につながる保証がない。実際に外れます。1〜30円で食い違うのは 6, 10, 14, 18, 22, 26, 30 円で、6円が最初、以後4円おきでした。1〜10,000円では2,499件です。
注意したいのは、貪欲は外れても何も知らせないことです。3枚という答えはすぐ返り、正しそうに見えます。1〜5円では最適と一致するので、数例を試しただけでは気づけません。
Huffman 符号 — 最も少ない2つを毎回くっつける
貪欲法が正しく働く代表が、Huffman 1952 の符号です。論文の冒頭はこう始まります(スキャン画像から目視で転記)。
One important method of transmitting messages is to transmit in their place sequences of symbols.
手続きは貪欲です。出現回数の最も少ない2つをくっつけて1つにし、それを最後の1つになるまで繰り返す。「最も少ない2つ」を毎回取り出すのには、この期のヒープの回で扱うヒープが使えます。直観としては、一番まれな2つを一番深い位置に兄弟として置いても損しない、という入れ替えが効いています。RFC 1951 §3.2.1 は、結果をこう呼びます。
(one which represents strings with those symbol frequencies using the fewest bits of any possible prefix codes for that alphabet). Such a code is called a Huffman code.
"this is an example of a huffman tree"(36文字、16種類。英語版 Wikipedia の Huffman coding の項で使われている例文)で数えました(同じ環境)。
text='this is an example of a huffman tree' len=36 distinct=16fixed-length: 4 bits x 36 = 144 bits; Huffman total = 135 bits; Kraft sum = 1.0
16種類なので固定長は4ビット×36 = 144ビット、Huffman は135ビットです。差は9ビット、約6%しかありません。この文は頻度があまり偏っていないからです。Huffman は最短を保証しますが、大きく縮むとは限りません。同点の結び方で個々の符号長は変わり得ますが、合計の135ビットは変わりません。
実物では、前提が加わると話が変わります。
- DEFLATE(RFC 1951): 動的 Huffman(BTYPE=10)なら、ブロックごとに頻度から符号を作り、符号の表の代わりに符号長の並び(それ自体も圧縮して)を送ります。固定 Huffman(BTYPE=01)もあります。符号長は §3.2.7 で「
0 - 15: Represent code lengths of 0 - 15」としか表せないので、上限は15です。この上限について §3.2.1 は「This constraint complicates the algorithm for computing code lengths from symbol frequencies.」と書いています。 - HPACK(RFC 7541 付録 B): 頻度を毎回数えず、統計から作った固定表を両端が共有します。「This Huffman code was generated from statistics obtained on a large sample of HTTP headers.」表の257項目を数えると、符号長は5〜30ビットで、Kraft 和は1.0でした。第18期の「共有する表は、届く順序を要求する」で、この表を使う側を見ています。
RFC 1951 は、DEFLATE の Huffman 符号に符号長の上限があることについて何と書いていますか。
硬貨 {1,3,4} で6円
大きい順に4円を取ると 4+1+1 の3枚。最適は 3+3 の2枚です。最適解の中に合計4円の組が無く、1手目を入れ替えられません。答えはすぐ返りますが外れています。
Huffman 符号
最も少ない2つを毎回くっつけます。一番まれな2つを一番深い所に兄弟で置いても損しない、という入れ替えが効くので、合計ビット数は最小になります。例文では144ビットが135ビットになりました。
片方では貪欲が外れ、もう片方では最適になります。手続きの形はどちらも「目先で一番の手を取る」です。違いを生んでいるのは何でしょうか。
それぞれ「最適解を1つ持ってきて、その1手目を貪欲の1手目に替えたら、悪くなるか」を試してください。
この章のまとめ
- 貪欲法は、いま一番良く見える手を取り、取り消さない。速くて書きやすい。
- 正しいのは、最適解の1手目を貪欲の1手目に入れ替えても損しないと言えるとき(貪欲選択性)。示し方の直観が交換論法。
- 日本の硬貨では1〜10,000円の10,000件すべてで貪欲が最少。
{1,3,4}では6円で外れる(貪欲3枚、最適2枚)。以後4円おき。 - 構造が無いと、貪欲は速く、黙って間違える。 数例が合っても根拠にならない。
- Huffman 符号は、最も少ない2つを毎回くっつける貪欲で最短の語頭符号を作る。例文では144ビットが135ビットで、差は小さい。
- DEFLATE は動的 Huffman ならブロックごとに符号を作り、符号長は0〜15でしか表せない。HPACK は統計から作った固定表(符号長5〜30)。
- 既存クイズでは、「アルゴリズムとデータ構造」の algorithm-14、「II(応用編)」の algorithm-2-9、「計算理論と形式言語 II(発展編)」の computation-theory-2-8・-9 がこの章の結論の一行版です。
- CLRS(『アルゴリズムイントロダクション』)の目次や索引で greedy algorithm(貪欲法) を探すと、この回の内容に対応する章や節が見つかります。章の題と番号は版で変わるので、手元の目次で確かめてください。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
日本の硬貨 {1,5,10,50,100,500} で、1〜10,000円の全額について「大きい順に取る」枚数と表で求めた最少枚数を突き合わせました。結果として正しいものはどれですか。
用語集(4語)
- 貪欲法(greedy)
- 各段階で、その時点で一番良く見える手を取り、後から取り消さない解き方。速くて書きやすいが、正しいのは貪欲選択性を持つ問題に限られる。
- 貪欲選択性
- 最適解の1手目を、貪欲が選ぶ1手目に入れ替えても損しない(最適のまま残る)という性質。これが言えると、1手目を決めたあと残りの小さな問題に同じ議論を繰り返せる。
- 交換論法
- 「最適解の一部を貪欲の選択に入れ替えても悪くならない」と示すことで、貪欲法の正しさを示す考え方。本教材では直観だけを扱い、証明は求めない。
- Huffman 符号
- 記号の出現頻度から、合計ビット数が最小になる語頭符号を作る方法。頻度の最も少ない2つを毎回くっつける貪欲な手続きで組み立てる。