【貪欲法はどれくらい精度が高いの？】ナップサック問題を貪欲法で解いたら最適解とどれくらいギャップがあるのかを実験してみた

こんにちは！しゅんです！

最近ある問題をソルバーで解いてたときにこう思いました。

特に実務で最適化問題を扱うときはこう考える場合が多いんじゃないでしょうか。ということでこの記事では、貪欲法でナップサック問題を解いたときに最適解と比べてどれくらいギャップがあるのかを調査してみました！

それではやっていきましょう！

ナップサック問題とは、与えられた品物集合とそれぞれの品物に設定された重さおよび価値、そしてナップサックの容量という制約条件の下で、ナップサックに詰め込める品物の組み合わせの中で、総価値が最大となるものを選ぶ問題です。

ここでは、品物の集合を

\(I=\{1,2,…,n\}\)

とし、各品物 \(i \in I\) に対して重さ \(w_i\) と価値 \(v_i\) が定められているとします。またナップサックの容量を \(W\) とします。つまり、選ばれた品物の集合 \(X \subseteq I\) に対して

\(\sum\limits_{i \in X} w_i \leq W\)

という制約を満たしながら、総価値

\(\sum\limits_{i \in X} v_i\)

を最大化するのが目的です。

例）
\(I = \{1,2,3,4\}\)
品物1: \(w_1=2, ; v_1=3\)
品物2: \(w_2=3, ; v_2=4\)
品物3: \(w_3=4, ; v_3=5\)
品物4: \(w_4=5, ; v_4=6\)
ナップサックの容量: \(W=5\)

この例では、いくつかの品物の組み合わせを考えることができます。

・\(\{1,2\}\) を選んだ場合
重みの総和： \(w_1+w_2=2+3=5\)
価値の総和： \(v_1+v_2=3+4=7\)
となり、容量 \(W\) をちょうど満たし、かつ価値は 7 です。

・\(\{4\}\) を選んだ場合
重みの総和： \(w_4=5\)
価値の総和： \(v_4=6\)
となります。

・\(\{1,3\}\) を選んだ場合
重みの総和： \(w_1+w_3=2+4=6\)
となり容量 \(W=5\) を超えてしまうため、この選択は不適です。

この問題例では、最適解は \(\{1,2\}\) であり、得られる総価値は7となります。

それでは次に貪欲法（Greedy Algorithm）について簡単に説明します。貪欲法を一言で説明すると

です。最適解を必ず得られるわけではないですが、ある程度精度が高い解を比較的シンプルで高速に実行できることが多いのが魅力です。

貪欲法は問題ごとに設定します。もちろんナップサック問題向けの貪欲法も存在します。今回はこのナップサック問題を解くための貪欲法を使って、どれくらいの精度の解が得られるのかを調査したいと思います。

それでは次に今回の本題である、

ナップサック問題を貪欲法で解く方法

を解説したいと思います。もう一度貪欲法がどんなアルゴリズムかを説明すると

です。このことを頭に入れてここからの話を読むと理解しやすいと思います。

最も「よさそう」な選択肢ってなんだろう？

ナップサック問題において「最もよさそう」な選択肢とは、直観的には

「価値が高く、かつ重さが軽い」品物を選ぶこと

です。すなわち品物ごとの価値対重さの比（value-to-weight ratio）が高いものを優先するという考え方に基づきます。例えば以下の問題例について考えてみましょう。

\(I = \{1,2,3,4\}\)
品物1：\(w_1=2, ; v_1=3\)
品物2：\(w_2=3, ; v_2=4\)
品物3：\(w_3=4, ; v_3=5\)
品物4：\(w_4=5, ; v_4=6\)
ナップサックの容量: \(W=5\)

各品物について価値対重さの比を計算すると下記のようになります。

品物1：\(\frac{v_1}{w_1}=\frac{3}{2}=1.5\)
品物2：\(\frac{v_2}{w_2}=\frac{4}{3}=1.33333333…\)
品物3：\(\frac{v_3}{w_3}=\frac{5}{4}=1.25\)
品物4：\(\frac{v_4}{w_4}=\frac{6}{5}=1.2\)

これがコスパの良さを表す指標となります。これが大きい順にナップサックに詰めていって、容量制限に到達した時点で終了します。

上の例だと品物1→品物2→品物3→品物4の順にナップサックに詰めていきます。しかし品物2を詰めた時点でナップサックの容量制限に到達するので、解\(\{1,2\}\)を出力します。ちなみにこの解は最適解になります。

数式を使って貪欲法を説明する

それでは次に、今説明した貪欲法を数式で表してみましょう。

数式が入ってややこしくなりましたが、やってることはさっきと一緒です。さっきの例を使って詳しく見ていきます。各品物の比率は下記のように計算されます。

・品物1: \(r_1=\frac{3}{2}=1.5\)
・品物2: \(r_2=\frac{4}{3}=1.33333333…\)
・品物3: \(r_3=\frac{5}{4}=1.25\)
・品物4: \(r_4=\frac{6}{5}=1.2\)

比率の大きい順に並べると、品物1, 品物2, 品物3, 品物4 の順になります。まず、品物1を選ぶと残容量は

\(W’=5-2=3\)

になります。次に品物2を見ますが、品物2の重さは \(w_2=3\) であり、残容量 \(W’=3\) とちょうど合致するので、品物2も選択されます。品物2を選ぶと残容量は

\(W’=3-3=0\)

その結果、選ばれた解は \(\{1,2\}\) となり、総価値は \(3+4=7\) となります。

貪欲法が最適解を出力するとは限らない

さっきまで考えていた例では貪欲法が最適解を出力していましたが、どんな問題例でも最適解を出力するとは限らないです。

例えば下記の問題例を考えます。

品物の集合：\(I=\{1,2,3\}\)
ナップサックの容量：\(W=8\)
品物1： \(w_1=3,\quad v_1=4\)
品物2： \(w_2=4,\quad v_2=5\)
品物3： \(w_3=5,\quad v_3=6\)

この問題に対して貪欲法を適用します。まず各品物の比率 \(r_i\) に基づいて降順に並べます。比率は

\(r_1=1.33333333…,\)
\(r_2=1.25\)
\(r_3=1.2\)

となるため、選択順は「品物1 → 品物2 → 品物3」となります。

最初に品物1を選ぶと、残りの容量は \(8-3=5\) になり、現在の総価値は4となります。

次に品物2を選びます。品物2の重さは4で、残り容量5に収まるため選択され、残容量は \(5-4=1\) に、総価値は \(4+5=9\) となります。

最後に品物3は重さ5で、残り容量1では選択できないため、最終的な解は品物1と品物2の組み合わせとなります。しかしながらこの問題の最適解は品物1と品物3を選ぶことで価値の総和は10です。

貪欲法が出力する解
選ばれた品物：品物1と品物2
価値の総和：9

最適解
選ばれた品物：品物1と品物3
価値の総和：10

このように、0-1ナップサック問題においては、価値対重さ比に基づく貪欲法は必ずしも最適解を与えるとは限らないことが分かります。

それでは最後に、貪欲法で得られた解が最適解と比べてどれくらいの精度なのかを実験してみたいと思います。実験方法は下記の通りです。

貪欲法を実行するコード

import random
import pulp
import time

def generate_knapsack_instance(n_items, weight_range=(1, 20), value_range=(1, 20), capacity=None):
    # ランダムにナップサック問題のインスタンスを生成する関数
    # weights: 各品物の重さのリスト
    # values: 各品物の価値のリスト
    # capacity: ナップサックの容量（指定がなければ品物重さの合計の半分に設定）
    weights = []
    values = []
    for i in range(n_items):
        w = random.randint(*weight_range)
        v = random.randint(*value_range)
        weights.append(w)
        values.append(v)
    if capacity is None:
        capacity = int(sum(weights) * 0.5)
    return weights, values, capacity

def greedy_knapsack(weights, values, capacity):
    # 貪欲法による0-1ナップサック問題の解法
    # 各品物について価値/重さの比率を計算し、降順にソートしてから、
    # ナップサックに入る品物を順次選択する
    start_time = time.time()
    n = len(weights)
    # 各品物の比率 (value-to-weight ratio) とインデックスのタプルリスト
    ratios = [(values[i] / weights[i], i) for i in range(n)]
    # 比率の降順にソート（比率が高いものを優先）
    ratios.sort(reverse=True)
    remaining = capacity
    chosen_indices = []
    total_value = 0
    for ratio, i in ratios:
        if weights[i] <= remaining:
            chosen_indices.append(i)
            total_value += values[i]
            remaining -= weights[i]
    end_time = time.time()
    elapsed_time = end_time - start_time
    return chosen_indices, total_value, elapsed_time

def solve_knapsack_ilp(weights, values, capacity):
    # 整数計画問題（ILP）によって最適解を求める関数
    # x_i: 品物 i を選ぶか否かのバイナリ変数
    # 目的関数: Σ v_i * x_i の最大化
    # 制約: Σ w_i * x_i ≤ capacity
    start_time = time.time()
    n = len(weights)
    prob = pulp.LpProblem("Knapsack", pulp.LpMaximize)
    x = [pulp.LpVariable(f"x_{i}", cat="Binary") for i in range(n)]
    
    # 目的関数の設定
    prob += pulp.lpSum(values[i] * x[i] for i in range(n))
    
    # ナップサック容量制約
    prob += pulp.lpSum(weights[i] * x[i] for i in range(n)) <= capacity, "Capacity"
    
    prob.solve(pulp.PULP_CBC_CMD(msg=0))
    chosen_indices = [i for i in range(n) if pulp.value(x[i]) > 0.5]
    total_value = pulp.value(prob.objective)
    end_time = time.time()
    elapsed_time = end_time - start_time
    return chosen_indices, total_value, elapsed_time

def run_experiments(n_trials=100, n_items=20, weight_range=(1,20), value_range=(1,20)):
    # 100回の実験を行い、貪欲法と整数計画問題による解の総価値のギャップを比較する関数
    greedy_values = []
    greedy_times = []
    optimal_values = []
    optimal_times = []
    for _ in range(n_trials):
        weights, values, capacity = generate_knapsack_instance(n_items, weight_range, value_range)
        _, g_value, g_elapsed = greedy_knapsack(weights, values, capacity)
        _, o_value, o_elapsed = solve_knapsack_ilp(weights, values, capacity)
        greedy_values.append(g_value)
        greedy_times.append(g_elapsed)
        optimal_values.append(o_value)
        optimal_times.append(o_elapsed)
    # ギャップ：貪欲法の価値 / 最適（ILP）による価値
    gaps = [o / g if o > 0 else 0 for g, o in zip(greedy_values, optimal_values)]
    num_equal = sum(1 for gap in gaps if gap == 1)
    avg_gap = sum(gaps) / len(gaps) if gaps else 0
    g_avg_time = sum(greedy_times) / len(greedy_times)
    o_avg_time = sum(optimal_times) / len(optimal_times)
    print(f"(最適値 = 貪欲法の総価値) となる回数：{num_equal}回 / {n_trials}回")
    print(f"ギャップの平均値 (greedy / optimal)：{avg_gap:.4f}")
    print(f"計算時間（貪欲法）：{g_avg_time:.6f}秒")
    print(f"計算時間（CBCソルバー）：{o_avg_time:.6f}秒")
    #return greedy_values, optimal_values  # 解を比較したい場合は「#」を消す

実験1の結果

実験1の結果は上図のようになりました。これを見ると

貪欲法で最適解が得られた回数：58回
最適解が得られなかった回数：42回

となりました。40%くらいは最適解は得られていないということですね。ギャップの所を見ると平均して最適値は貪欲法で得られた解の目的関数値の約1.0008倍であることが分かります。

全然ギャップが小さいですね。ほぼ最適値です。気になって調べてみましたが、一番ギャップが大きかった問題例でも約1.004倍でした。

計算時間も貪欲法の方が約1380倍速いという結果になりました。（この程度ならソルバーでも相当高速ですが。）

実験2の結果

実験2の結果は上図のようになりました。これを見ると

貪欲法で最適解が得られた回数：100回
最適解が得られなかった回数：0回

となりました。なんと全ての試行で最適解が得られたということです。これはびっくりしました。問題のサイズが大きくなったのにむしろ最適解を得やすくなったのは驚きました。

計算時間も貪欲法の方が約82倍速いという結果になりました。（この程度ならソルバーでも相当高速ですが。）

ということで結論としてはナップサック問題に対する貪欲法は、近似保証がないもののかなり強力なアルゴリズムだと思いました。

今回はナップサック問題を貪欲法で解いてみました！

今後もこのような組合せ最適化に関する記事を書いていきます！

最後までこの記事を読んでくれてありがとうございました。