学生時代に学んだ知識は、あくまで学問としての理解にとどまり、それを実社会で活かすということは意外と難しいものです。そもそも、大学入試を目的として学んだことや、大学卒業(単位の取得)の為だったりすると尚更、直ぐに忘れてしまいます。人間の脳は10%程度しか利用していないといわれていますが、なぜ、利用していない脳に情報を書き込むことはせず、10%にも満たない範囲に上書きしてしまうのか不思議です。

 さて、学生時代に学んだことに「ナップサック問題」というのがありました。いわゆる組合せ最適化問題といわれるもので、似たような問題には、「巡回セールスマン問題」や「長方形詰め込み問題」など有名な問題がいくつか有ります。これらの問題を見たことある、という人は多いと思いますが、内容を忘れてしまっている人も多いと思いますので、もう一度おさらいしてみたいと思います。

 まず、組合せ最適化問題とは、条件を満たす解の中で一番良い結果を求める問題で、解が順序や割り当てのような組合せ構造を持つものを指します。
 具体的な問題として、先に出た巡回セールスマン問題に触れてみます。とあるセールスマンが多数ある都市を一度ずつ訪問するにあたって、最も効率の良い巡回経路を求めようとする問題です。与えられるデータは、(1)都市の数(n個)と(2)2地点間の距離の二つのみ。全ての都市を一度ずつ訪問し元の地点に戻り、その総距離が一番短いルートを求める、という問題です。
 全ての巡回経路を列挙して、その総距離が一番短いものを調べれば解くことは出来ますが、その経路のパターンは、n!=n(n-1)(n-2)…2・1通りとなります。nの数が3個の場合には6通りしかありませんが、nが10個の場合3,628,800通りとなり、nが30個の場合2.7*10^32通りのパターンが存在しますので、もう現実的に皆さんが使っているPCでは計算不可能です。
img20150116

 次に、ナップサック問題を見てみます。ナップサック問題で与えられるデータは(1)n個の商品の価値と(2)その商品の値段、および(3)ナップサックの容量(もしくは予算上限)です。複数の商品を選んで、選んだ商品の値段が予算の上限を超えないように、しかも出来るだけ価値を大きくしたい、という問題です。
 ちょっと漠然としているので、分りやすい例をあげてみます。
 あなたは小学生です。今度の日曜日に遠足があり、おやつは300円までと決まっています。以下の6種類の中からいくつかを買ってもって行くかを決めるとします。あなたならどれを持っていきますか?(お菓子の満足度を計るパラメータとして、かなり乱暴ですがカロリーを一つの目安とします。カロリー値は便宜上、任意に設定しました。)

品名 価値(満足度) 値段 価値÷値段
チョコレート 150 220 0.681
お煎餅 40 80 0.5
ガム 30 40 0.75
グミ 10 60 0.166
ポテトチップス 80 100 0.8
ラムネ 20 20 1

 選び方はいろいろありますが、例えば、満足度の高い順から選んだとします。
 まず、満足度が一番高い150のチョコレートを選びます。次に満足度の高いポテトチップスを選びたいのですが、これを選ぶと20円予算オーバーなので、その次に満足度の高いお煎餅を選びます。そうすると、220円+80円で300円ぴったり購入でき、満足度は190となります。
 次に、値段の安い順から選んだとします。まず、ラムネを選び、次にガム、グミ、お煎餅、ポテトチップスと順に選びます。ここまでくると丁度300円となり、満足度は合計で180となります。
 今度は、価値÷値段でパラメータの大きい順に選んだとします。そうすると、ラムネ、ポテトチップス、ガムと選びます。次はチョコレートですが、これを選ぶと予算オーバーになるため、チョコレートを飛ばしてお煎餅とグミを選びます。そうすると、300円丁度となり、満足度は180になります。
 ですが、全部のパターンを調べると、チョコレート、ガム、ラムネの三つを選ぶと最も満足度が高いことが分ります。280円を使って満足度は200となります。
 こうしてみると、先に優先順位をつけて最適解を求めようとしても求められず、全検索(列挙)ではじめて最適解が出てくるのです。
 それでは、このようなナップサック問題はどのくらいの組合せがあるかというと、2^nとなり、nが3個であれば8通り、nが10個であれば1,024通り、nが30個であれば1,073,741,824通りなります。先ほどの巡回セールスマンほどではありませんが、nが大きくなると爆発的に大きくなり、演算が困難になってきます。

 ここで立ち返って欲しいのですが、最適解でなければ絶対にダメというものと、そうでないものとが有ります。たぶん、現実的には最適解に近い近似解で十分目的を達成できることも多いと思います。それの精度をどれだけ上げ、最適解に近づけるかが重要だったりしますし、そのような研究は発展しており、有限な時間で最適解に可也近い解を出せるようになってきています。
 先のナップサック問題に類似した事象が現実問題としてあった場合、価値÷値段を選ぶことが多いと思います。そういう私もよく、この方法を採用していました。しかし、このケースを最適解に変更することで20円安い値段で満足度は20も高い成果を上げられるのです。300円のおやつであれば、それほど気にもならない差かも知れませんが、その予算規模が大きくなれば、相応の効果が期待されます。