「大人の教養・知識・気付き」を伸ばすブログ

※今月(8月)は一部コンテンツを隔週更新にします(夏休みです…)。 一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。

MENU

Pythonで学ぶアルゴリズム(13/18)

 アルゴリズムを学ぶのにPythonの学習も兼ねて

を参照していく。

7. 問題を解くための技術

 ナップサック問題を3通りの方法で解いてみる。

7.1 ナップサック問題

 出張や旅行で、異なる重量のお土産を重量制限ギリギリまでなるべく多く*1収めるためにどれをどれだけ収納するかを解く問題をナップサック問題という。

7.1.1 ナップサック問題の概要

 重量に制限(上限)があるナップサックが1つある。他方でn個の品物があり、それぞれの品物には重さと値段がある(いずれも正の整数とする。)。品物にはラベル(名前か番号)を付けて区別する。これらの品物をナップサックに詰めるときに、重量制限を守りつつ、ナップサック内にある品物の価値が最大になるような組み合わせを求めたい。これがナップサック問題である。ここでは各品物は1単位を入れるか入れないかの2択だとする*2
 以下ではすべての品物の重さと値段が異なるものとする。

 まずはテスト用に品物リストを乱数で生成する。各品物の重さ上限は5kg、品物の個数は20個、価値の上限は50万円とする。

##################################
### 品物リストを乱数で作成する ###
##################################

from collections import namedtuple
import random

random.seed(7)# 乱数シード

# クラスを作成:
Item = namedtuple('Item', ('name', 'weight', 'price'))

# 品物の個数
num = 20

# 品物を保持するリスト
item_list = []
max_weight = 5 # 重さの上限値:乱数で発生させるため

# 品物の個数よりも大きな数値にする
max_price = 50

# 値段の候補リストを作り、シャッフルする
price_list = list(range(1, max_price + 1))
random.shuffle(price_list)

# 無作為に品物を作る。名前は番号
for i in range(num):
    w = random.randint(1, max_weight)
    item = Item(i, w, price_list.pop())
    item_list.append(item)

item_list

 また今後のためにナップサックを表現するクラスを定義しておく。

########################
### 各種クラスを定義 ###
########################

class Knapsack:
    
    def __init__(self, size):
        # このナップサックが保持できる最大の重さ
        self.size = size
        
        # 現在の重さ
        self.weight = 0
        
        # 入っている品物の価値の総和
        self.value = 0
        
        # 保持するItemの配列
        self.items = []
        
    def append(self, item):
        """ このナップサックにItemを追加する """
        if not self.has_room_for(item):
            raise ValueError('この品物は入れられません。重量オーバーです。')
        self.items.append(item)
        self.weight += item.weight
        self.value += item.price
        
    def has_room_for(self, item):
        """ 引数に取った品物を入れる余裕があるかを真偽値で返す """
        return self.size >= self.weight + item.weight
    
    def __str__(self):
        val = '重さ {} kg / 価値 {} 万円'.format(self.weight, self.value)
        return val
7.1.2 貪欲法

 解き方としても最も単純な貪欲法(\mathrm{greedy\ algorithm})を考える。これは同じ重さならばより価値があるものを持って帰るだろうと考え、値段を重さで割った値*3で品物を降順に並べ替え、その値が高いものから順にすべての品物についてナップサックに入るかどうかを試す。

def greedy(items, size_limit):
    # 単位重さ当たりの値段で品物を並び替える
    sorted_item_list = sorted(items, key = lambda x: x.price/x.weight, reverse = True)
    my_knapsack = Knapsack(size_limit)
    
    for v in sorted_item_list:
        # 入る余地があるならば品物を入れる
        try:
            my_knapsack.append(v)
        except ValueError:
            continue
    return my_knapsack

knap_g = greedy(item_list, 40)
print(knap_g)
   
7.1.3 総当たり

 品物は全部で20個あり、各品物は入るか否かの2択であるから、ナップサックへの詰め方は2^{20}通りある。これをすべて調べる。そのうちナップサックの重量を超えているものを除外する。残った品物の組み合わせのうち最も価値のあるものが最適な解になる。これを\mathrm{brute}-\mathrm{force}アルゴリズムという。

import itertools

def brute_force(items, size_limit):
    # 答えの候補
    candidate = None
    
    for pattern in itertools.product((0,1), repeat = len(items)):
        my_box = []
        
        for i, val in enumerate(pattern):
            if val: my_box.append(item_list[i])
        w = sum([item.weight for item in my_box])
        
        # ナップサックの重量制限を守れないならば、ループの次へ
        if w > size_limit: continue
            
        # 総額を計算しこれまでの最高を上回るのであれば、候補として残す
        value = sum([item.price for item in my_box])
        
        if candidate is None or value > candidate.value:
            knapsack = Knapsack(size_limit)
            
            for v in my_box:
                knapsack.append(v)
            candidate = knapsack
    return candidate

knap_bf = brute_force(item_list, 40)
print(knap_bf)
7.1.4 組み合わせ爆発

 総当たりは時間が掛かる。上記では2^{20}=1,048,576回実行される。この計算量は\mathcal{O}(2^n)であるから、爆発的に増える。計算量が階乗または指数関数であるようなものを総称して組み合わせ爆発という。組み合わせ爆発を起こすような問題には、最適解を諦めてその良い近似解を求めるという方向性がある。このようなアルゴリズムは一般的に近似アルゴリズムという。
 ただしナップサック問題では多項式時間アルゴリズムで最適解が得られることが知られている。

*1:厳密には価値が最大など目的は問題によって異なってもよい。

*2:このようなナップサック問題は特に0-1ナップサック問題という。

*3:今回は値段も重さも正の整数と仮定しているため、異常値は生じない。

プライバシーポリシー お問い合わせ