貪欲法（グリーディアルゴリズム）とは？仕組み・コード・例題をわかりやすく解説

貪欲法が解く問題

貪欲法の対象は最適化問題です。最も多くの活動を選ぶ、最少のコインを使う、最も安いネットワークを構築する、ファイルを最少のビット数に圧縮する、といったものです。貪欲法は、すべての組み合わせを調べる代わりに、選択肢をソートまたは優先順位づけして、各ステップで最良のものを確定させていきます。計算量は通常 O(n log n) で、多くの場合ソートのコストだけです。

難しいのはコードではなく証明です。自然に思えても誤っている貪欲なルールが多いので、ルールが正しいことを証明するか、全探索の解法と照らし合わせて検証する必要があります。

考え方を言葉で説明すると

1. 選択肢に順位をつけるルールを見つけます。たとえば「終了時刻が早いものから」「最も軽い辺から」などです。
2. そのルールで選択肢をソートするか、優先度付きキューに入れます。
3. 選択肢を順に見ていき、制約がまだ許すものを採用します。
4. 一度行った選択は取り消しません。

貪欲法が正しいのは、2つの性質が成り立つときです。貪欲選択性：最初の貪欲な選択を含む最適解が存在する。最適部分構造：その選択をした後に残る問題が、同じ種類のより小さな問題になる。証明には、交換論法がよく使われます。任意の最適解を取り、その選択の1つを貪欲な選択と入れ替えても悪くならないことを示します。

例題：区間スケジューリング

会議室が1つあり、次の予約リクエスト（開始、終了）があります。A (1, 4)、B (3, 5)、C (0, 6)、D (5, 7)、E (3, 9)、F (5, 9)、G (6, 10)、H (8, 11)。重ならない会議をできるだけ多く予約します。正しい貪欲なルールは、直前に予約した会議の終了後に始まる会議のうち、終了が最も早いものを常に選ぶことです。

結果は A、D、H の3件で、これが最大です。うまくいく理由：終了が最も早い会議は、他のすべての会議のために最も多くの時間を残すので、どの最適なスケジュールの最初の会議をそれに置き換えても、衝突は起きません。

Pythonでの実装

def max_meetings(meetings):
    """meetings: list of (name, start, end). Returns the booked names."""
    booked, last_end = [], float("-inf")
    for name, start, end in sorted(meetings, key=lambda m: m[2]):
        if start >= last_end:
            booked.append(name)
            last_end = end
    return booked

requests = [("A", 1, 4), ("B", 3, 5), ("C", 0, 6), ("D", 5, 7),
            ("E", 3, 9), ("F", 5, 9), ("G", 6, 10), ("H", 8, 11)]
print(max_meetings(requests))  # ['A', 'D', 'H']

もう1つの定番の例が分数ナップサック問題です。品物の一部を取ってもよい場合は、重さあたりの価値が高い順に取るのが最適です。

def fractional_knapsack(items, capacity):
    """items: list of (value, weight). Returns the best total value."""
    total = 0.0
    for value, weight in sorted(items, key=lambda i: i[0] / i[1], reverse=True):
        take = min(weight, capacity)
        total += value * take / weight
        capacity -= take
        if capacity == 0:
            break
    return total

print(fractional_knapsack([(60, 10), (100, 20), (120, 30)], 50))  # 240.0

貪欲法が失敗する場合：反例

時間計算量と空間計算量

空間計算量は、ソートしたコピーやヒープのために、通常 O(n) です。入力がすでにソート済みなら、多くの貪欲法は O(n) で動作します。

貪欲法を使う場面と実世界での用途

• 貪欲選択性を証明できる場合や、高速な近似解で十分な場合に貪欲法を使います。それ以外は動的計画法やバックトラッキングを使います。
• 圧縮：ハフマン符号は、出現頻度が最も低い2つのシンボルを繰り返し併合して、最適なプレフィックス符号を作ります。DEFLATE（ZIP、gzip、PNG）などの形式の内部で使われています。
• ネットワーク：最小全域木（クラスカル法、プリム法）と、最短経路ルーティング（ダイクストラ法）。
• スケジューリング：最早締切優先（EDF）や、会議室・機械の予約。
• 近似：集合被覆問題では、「まだ覆われていない要素を最も多く覆う集合を選ぶ」という貪欲なルールは最適ではありませんが、最適解の対数倍以内であることが保証されます。
• コーディング面接の問題：ジャンプゲーム、ガソリンスタンド、クッキーの割り当て、重ならない区間、風船を割る最小の矢の数、タスクスケジューラ。