グリーディアルゴリズムとは何か、そしていつ機能するのか？

Question

Accepted Answer

**グリーディアルゴリズム**は各ステップで**局所的に最適な選択**を行い、グローバルな最適解につながることを期待します。シンプルで高速ですが、問題が**greedy-choice property**と**optimal substructure**を持つ場合のみ正しい結果が得られます。

## アイデア

過去の選択を再考しない — 最善の即座のオプションにコミットして先に進む。

## 例：標準的なコインでのコイン両替

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

これは米国のコインに対して最適ですが、{1, 3, 4}のようなセットでは**失敗し**、グリーディは6に対して4+1+1を与えますが、代わりに3+3すべきです。

## グリーディが機能する場合

- **Optimal substructure:** 最適解は最適な部分解を含む。
- **Greedy-choice property:** 局所的な最適解はグローバルな最適解の一部である。

機能する例：Dijkstra、Kruskal/Prim（MST）、Huffman coding、interval scheduling。

## 計算量

通常は高速 — ソート後は多くの場合 O(n log n)。

## 落とし穴

グリーディは**常に正しいとは限りません**。greedy-choice propertyを証明するか、それを信頼する前にbrute-force/DPベースラインに対してテストしてください。

## なぜ重要なのか

グリーディが適用される場合、DPやbrute forceよりもはるかにシンプルで高速です。

それが有効である*とき*を知る — そして沈黙して誤った答えを与えるとき — はアルゴリズム的成熟さの証です。

多くの基本的なグラフアルゴリズムは本質的にグリーディです。