数学の具体的な問題にPythonを使って、数学もPythonも同時に学んでしまいましょう。今回はPythonを使った確率・統計の問題として、ナップサック問題をみてみたいと思います。重量と価値の決まった品物をナップサックに詰める問題ですが、ナップサックには重量制限があり、制限を満たすなかで詰め込んだ品物の価値を最大化するのはどのような組み合わせか？という問題で、実用上も面白い問題です。ここでは重量に制限があるとしましたが、容量と読み替えても同じですし、あるいは問題をより複雑にするためには、重量と容量の両方に制限を設けて考察することもできるでしょう。
今回は問題を簡単にするために重量のみについて制限を設けて考えてみます。
品物の重量・価値・個数
以下が品物の重量と価値、用意できた個数のリストだとします。
| 品物1 | 品物2 | 品物3 | 品物4 | 品物5 | 品物6 | 品物7 | 品物8 | 品物9 | 品物10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 重量 | 87 | 66 | 70 | 25 | 33 | 24 | 89 | 63 | 23 | 54 |
| 価値 | 96 | 55 | 21 | 58 | 41 | 81 | 8 | 99 | 59 | 62 |
| 個数 | 3 | 3 | 5 | 3 | 4 | 3 | 8 | 3 | 3 | 5 |
重量制限を750として、これらの品物をナップサックに詰めてみます。全部で10種類40個の品物があり、それら一つひとつについてナップサックに入れるか入れないか判断するのですから、単純には
（1兆！）だけの組み合わせが考えられます。これらの中から条件を満たすものだけを取り出して、さらに価値を最大にする組み合わせを探し出す、というのはなかなか大変そうです。
そこで重量制限内でとにかく当てずっぽうに品物を詰めるという試行をある程度の回数（ここでは例えば10,000回としてみます）繰り返して、その価値が最大となった組み合わせを出力してみます。この方法ではそれがベストな組み合わせであるという保証はありませんが、まずまずベターな組み合わせであることには違いないでしょう。100点満点のベストな組み合わせが得られればそれは確かに素晴らしいことですが、現実の問題では、ずっと少ない手間で90点以上の成果が得られればじゅうぶんということも往々にしてあります。ここではそういった気楽な態度でナップサック問題に取り掛かってみます。
品物の情報の入力
item_list = [1,2,3,4,5,6,7,8,9,10] item_weight = [87,66,70,25,33,24,89,63,23,54] item_value = [96,55,21,58,41,81,8,99,59,62] item_number = [3,3,5,3,4,3,8,3,3,5]
品物をランダムに選ぶ
残り個数がゼロになってしまっている品物はもう選ぶことはできません。そこで、残り個数がゼロになってしまった品物を選ぶ確率はゼロに、まだ残りがある品物は等確率でランダムで選ぶような関数を定義してみます。
そこで、残り個数がゼロの場合には０を、残り個数がゼロでない場合には１を返す関数 w を定義します。
def w(k): if k == 0: return 0 else: return 1
この関数 w を品物の残り個数のリスト item_number の各要素に作用して、重み付けのためのリスト rand_weight を作成します。
def rand_weight(item_number): rw = [] for k in item_number: rw.append(w(k)) return rw
この段階ではナップサックにはまだ何も詰めていないので、品物の残り個数のリストは、用意した品物の個数のリストと同じで、重み付けのためのリスト rand_weight は
rand_weight(item_number)
より
で、どの品物についても等しい重みになっています。重み付けのリスト rand_weight にしたがってランダムに品物１つを選ぶ関数 rand_item を定義します。
import random as rd def rand_item(r): return rd.choices(item_list, k=1, weights = rand_weight(item_number))[0]
ナップサックに品物を詰める
以下では、制限重量を超えてしまうまで次々にランダムに品物を選ぶ（ナップサックに詰める）ことを繰り返します。制限重量を超えてしまった時点で、その手前の状態までの品物のリストを試行結果として処理します。このような試行を繰り返し、価値がより高い組み合わせが出現するたびに（暫定的な）最高価値の組み合わせを次々に更新していくことによって、試行回数の中で最も価値の高い品物の組み合わせを探してみます。
# 重量制限 weight_limit = 750 # 試行回数 number_trial = int(1e4) # 試行回数中の最高価値の組み合わせ better_item = [] better_weight = weight_limit better_value = 0 # 各試行の価値と重量の結果リスト trial_value_list = [] trial_weight_list = [] count = 0 # ランダムにナップサックに品物を詰める試行 while( count < number_trial ): # 試行ごとに品物の残り個数を初期化する item_number = [3,3,5,3,4,3,8,3,3,5] # ナップサックに詰めた品物のリスト・重量・価値 knapsack_item = [] knapsack_weight = 0 knapsack_value = 0 # 制限重量を超えるまでランダムに品物を選ぶ while( knapsack_weight < weight_limit ): a = rand_item(0) if knapsack_weight + item_weight[a-1] <= weight_limit: knapsack_item.append(a) knapsack_weight = knapsack_weight + item_weight[a-1] item_number[a-1] = item_number[a-1] -1 knapsack_value = knapsack_value + item_value[a-1] else: break # 試行の価値・重量を結果リストに加える trial_value_list.append(knapsack_value) trial_weight_list.append(knapsack_weight) # 暫定的な最高価値の組み合わせとの比較・更新 if knapsack_value > better_value: better_item = knapsack_item better_weight = knapsack_weight better_value = knapsack_value elif knapsack_value == better_value: if knapsack_weight < better_weight: better_item = knapsack_item better_weight = knapsack_weight better_value = knapsack_value # 試行回数のカウント count = count + 1 # 全試行回数中の最高価値の組み合わせ [better_item, better_weight, better_value]
より、試行結果として
などという結果を得ます。つまり
| 品物1 | 品物2 | 品物3 | 品物4 | 品物5 | 品物6 | 品物7 | 品物8 | 品物9 | 品物10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 個数 | 2 | 0 | 0 | 3 | 3 | 3 | 0 | 3 | 3 | 1 |
のように18個ナップサックに詰めて、そのときの重量は732、価値は1268という値になります。
試行結果の度数分布表（ヒストグラム）
結果の妥当性を検討するために、ランダムにナップサックを詰めたときの重量・価値のヒストグラムを見てみましょう。まず重量は
import matplotlib.pyplot as plt plt.hist(trial_weight_list, bins=25, range=(600, 800)) plt.show()
より
から、720から750に多く分布していることがわかります。実装の手順から、ナップサックに詰めて制限重量を超えた時点でその手前の状態を試行結果としているので、最も重量の大きい品物7（重量89）を最後に加えて制限重量をオーバーしてしまう 662 が試行の下限値になりうるのですが、確かにそのようになっていそうなことがわかります。次に価値については
plt.hist(trial_value_list, bins=20, range=(600, 1300)) plt.show()
より
という分布を得ます。一見して中央値が800くらいで、1100を超える試行となると極端に少ないことがわかります。探索結果は1268だったので、なかなか良い組み合わせだったことがわかると思います。もちろん、これが最適な組み合わせであることを示すことはできませんし、実際、ランダム性のために試行のたび結果は変わってきます。しかしながら、同じ当てずっぽうに選ぶにしても、自分で試行錯誤するより、コンピュータを使ってランダムに振り分けて条件に合うものを取り出し、その中からベターなものを選択するというのは、より現実的で効率の良い手法です。冒頭にも述べましたが、100点満点のベストな答えは確かに素晴らしいですが、ずっと少ない手間で90点以上の答えを得られるというのもまた素晴らしいことです。
今回は、乱数を使ってナップサック問題を考察してみました。
