1 ナップザック問題とは
ナップザック問題とは、ナップザックに容量を超えずに荷物を詰めるときにその荷物の合計価値が最大とな る組み合わせ（以下最適解と呼ぶ）を求める最適化問題です。あらかじめ荷物のリスト（重さと値段の組）と ナップザック容量は与えられているとします。具体例としては、図1のようにナップザックの容量が2kgの場合に3つの商品（牛乳、おにぎり、サンドイッチ）の中からの場合にどの組み合わせをナップザックに入れれば値段合計を最大にできるかという問題となります。問題自体は非常に簡単なものですが、一般の最適解を求めるには全ての組み合わせを試す必要があり、今回の例では牛乳、おにぎり、サンドイッチのそれぞれを入れた場合と入れない場合の合計 2×2×2 = 2^3 = 8通りの組み合わせの計算が必要となります。ちなみにこの問題の最適解は「牛乳+おにぎり」（値段合計350円）となります。
組み合わせの総数は、商品の数が10個だと 2^10 = 1024通り、100個になると2^100 ∼ 1030となり、商品の数とともに膨大に増えていきます。したがって全ての組み合わせを試して最適解を求める方法は計算時間の観点から難しくなります。これがナップザック問題の難しさです。
2 身の回りのナップザック問題
身の回りでナップザック問題が応用できるケースとしては、離島や宇宙ステーションなど物資の輸送キャパ シティが不十分な状況でどのような物資を輸送するかといった問題や、試験時間が短いテストでどの問題を解 くかといったものが当てはまります。つまり、需要に対して供給の潜在能力はあるがキャパシティが不十分で あり、かつ供給の選択肢に富んでいる状況がナップザック問題に該当します。
3 ナップザック問題の近似解の探索
それでは、全ての組み合わせを計算するのが不可能な場合に、最適解ではなくそれに近い解（近似解）を求めるアルゴリズムをいくつか紹介します。
3.1 貪欲法について
近似解を得る方法としてまず最初に思いつくのが、「重さあたりの値段（以下コスパと呼びます）が大きい ものから順に入るだけナップザックに詰めていく」という愚直な方法で、「貪欲法」と呼ばれています。上の 例の場合は、牛乳、おにぎり、サンドイッチのコスパがそれぞれ200円/kg、214円/kg、240円/kgとなるので、コスパが高いサンドイッチを始めにナップザックに入れて、次におにぎりを入れて、次の牛乳はもう入れられないので「サンドイッチ＋おにぎり（合計270円）」が貪欲法の解となります。
ただし、この方法だととんでもない大間違いが起こるケースがあります。図2を見てください。ナップザックの容量が10kg、商品の候補としてビン牛乳（1kgで100円）、パック牛乳（10kgで900円）があり、この場合の最適解は明らかにパック牛乳（合計900円）です。ただ、コスパで選んでしまうと、先にビン牛乳をナップザックに入れてしまいパック牛乳はもうナップザックに入らないので、貪欲法の解はビン牛乳（合計100円）となります。貪欲法の解が最適解の1/9になってしまいました。
3.2 貪欲法以外の近似アルゴリズムについて
貪欲法はナップザック問題のためのアルゴリズムでしたが、他の最適化問題（巡回セールスマン問題など） でも適用可能な一般的な近似アルゴリズムもいくつか提案されています。これらについて紹介します。
最適化問題の一般の近似アルゴリズムでは、解の候補を1つの状態とみなしその状態をある規則に基づいて遷移させていき解に到達します。遷移ルールをどのように設定するかでいくつかのアルゴリズムが提案されていますが、基本的な考え方として重要なことが2つあります。
1つ目は「全ての組み合わせではなく、最適解となりそうなところに絞って探索する」ことで総試行数を大幅に減らすことです。これを実現する規則の例としては「遷移先の状態は前の状態より値段合計が増加している」などがあります。
2つ目は「狭い範囲の解だけでなく、広い範囲もうまく探索する」ことで最適解に近づけるということです。これは、「最終的な解の候補にならなそうな不要な荷物を取り除く」ような遷移が挙げられます。
この2つは相反する概念のため、遷移規則を定める際に2つのバランスをどのように取るかが重要になります。これらのバランスはアルゴリズムのパラメータの値として調整します。
近似アルゴリズムの1つとして焼きなまし法というもの。これは金属が冷えて結晶化する物理過程に立脚したアルゴリズムです。系の温度パラメータを設定し単調に減少させていきますが、温度が高い時ほど荷物を取り出すような遷移を許して探索範囲を広げ、温度が冷えてくると荷物を詰めていく遷移のみに許すように絞り込み行き着いた先を最適解とします。また、タブー探索法というのもあり、これは一度通った状態をタブーリストとして登録ししばらくの間その状態への遷移を禁止するというアルゴリズムです。これにより広い範囲の解をうまく探すことができます。
4 まとめ
ナップザック問題自体は数学的な最適化問題として知られていますが、荷物輸送やタスク処理など身の回りでも様々な適用事例が考えられます。荷物候補が増えると組み合わせ数が爆発的に増加し最適解を求めるのは難しいため、少ない計算時間で近似的な解を求める貪欲法や焼きなまし法などのアルゴリズムが提案されています。
（担当：アナリティクスチームN）
