貪欲法

貪欲法#

概要#

貪欲法（Greedy Algorithm） は、各ステップで「その時点で最も良く見える選択」を繰り返すことで解を構築するアルゴリズム設計手法である。

基本的な考え方#

問題をステップに分割し、各ステップで局所的に最適な選択をする
一度した選択は覆さない（後戻りしない）
全体の最適解を保証するには、問題が以下の2つの性質を満たす必要がある

性質	説明
貪欲選択性（Greedy Choice Property）	局所最適な選択を重ねることで大域最適解に到達できる
最適部分構造（Optimal Substructure）	問題の最適解が部分問題の最適解を含む

利点と欠点#

利点

実装がシンプルで理解しやすい
多くの場合、動的計画法より高速

欠点

適用できる問題が限られる（すべての最適化問題に使えるわけではない）
局所最適解が大域最適解にならないケースがある（例：一般的なコイン問題、0/1 ナップサック問題）

応用例#

例1: コイン問題#

Q. \(X\) 円の金額を日本の硬貨で支払うとき、必要な硬貨の最小枚数は？

大きい硬貨から貪欲に使っていくことで最小枚数が得られる（日本円の硬貨体系では成立する）。

coins = [500, 100, 50, 10, 5, 1] # 硬貨の種類

X = 873 # 例：873円を払いたい
total = 0
for coin in coins:
    count = X // coin  # その硬貨を何枚使えるか
    if count > 0:
        total += count
        X %= coin      # 残りの金額を更新

print(total)

例2: 区間スケジューリング問題#

Q. 複数の仕事（開始時刻・終了時刻が決まっている）の中から、重複しない範囲で 最大数 の仕事をこなすには？

貪欲な選択: 終了時刻が早い仕事から順に選ぶ。

def activity_selection(jobs: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """
    区間スケジューリング: 重複なしで選べる仕事の最大集合を返す

    Parameters
    ----------
    jobs : list of (start, end)
    """
    sorted_jobs = sorted(jobs, key=lambda x: x[1])  # 終了時刻でソート
    selected = []
    last_end = -1

    for start, end in sorted_jobs:
        if start >= last_end:
            selected.append((start, end))
            last_end = end

    return selected


jobs = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14)]
result = activity_selection(jobs)
print(f"選択された仕事 ({len(result)}件):")
for s, e in result:
    print(f"  [{s}, {e})")

選択された仕事 (3件):
  [1, 4)
  [5, 7)
  [8, 11)

例3: 分数ナップサック問題#

Q. 容量 \(W\) のナップサックに、重さ \(w_i\)・価値 \(v_i\) のアイテムを詰めるとき価値を最大化するには？アイテムを 分割して詰めてよい（分数ナップサック）場合は貪欲法で最適解が得られる。

貪欲な選択: 単位重量あたりの価値（\(v_i / w_i\)）が高いアイテムから詰める。

※ アイテムの分割が許されない 0/1 ナップサック問題 では貪欲法では最適解が保証されない（動的計画法が必要）。

def fractional_knapsack(capacity: float, items: list[tuple[float, float]]) -> float:
    """
    分数ナップサック問題

    Parameters
    ----------
    capacity : float
        ナップサックの容量
    items : list of (weight, value)

    Returns
    -------
    float
        最大価値
    """
    # 単位重量あたりの価値で降順ソート
    sorted_items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0.0
    remaining = capacity

    for weight, value in sorted_items:
        if remaining <= 0:
            break
        take = min(weight, remaining)
        total_value += value * (take / weight)
        remaining -= take

    return total_value


capacity = 50
items = [
    (10, 60),  # 重さ10, 価値60  → 単価6.0
    (20, 100), # 重さ20, 価値100 → 単価5.0
    (30, 120), # 重さ30, 価値120 → 単価4.0
]

max_value = fractional_knapsack(capacity, items)
print(f"最大価値: {max_value}")

最大価値: 240.0

貪欲法

Contents