組合せ計算アルゴリズム

　私たちの生活や産業活動のなかには、線形計画法、ダイナミックプログラミング、整数計画法などの数学的な手法が利用できる場合がある。これらの数学は統計学、計量経済学などと並んで、企業や国家の計画立案にも利用されている。このなかで、組合せ計算の問題というのがある。　この種類の問題の中には、組合せの数が巨大になるため実際的な時間の制限のなかでは解が得られないものがある。たとえば、「巡回セールスマン問題」はその代表的な問題である。

　「地図があって、セールスマンが行かねばならない複数の客先の場所とその道路がわかっている。どの順番に客先を選んで回れば最も移動距離が小さくできるか」
　客先の数がｎあれば、計算すべき組合せの数は n の階乗になり、n が1,000を越えれば、その組合せの数は極めて大きな数になってくる。

　このような問題を解くために、数学者達は知恵を振り絞ってきた。1980年代には米国で「カーマーカー特許」という線形計画法の解法を特許にするという事件まで持ち上がっている。（参考：今野浩著「カーマーカー特許とソフトウエア」中公新書、1995年）

　このほかにも、ナップザック問題というのがある、すなわち、

　「山男がn種類の品物（ｉ=1,2,3…n）をナップザックに詰めて登山に出かけようとしている。持ち運べる質量は最大Mグラムであり、品物ｉの1個の質量はCiグラムである。品物Ciの1個あたりの効用（有効な価値）がPiであるとするとき、効用（Piの合計）を最大にするための品物をどのように選べばよいか」

　実際、旅行や登山に出かける前にこの問題が現実になることは少ない。なぜなら、旅行や登山に持ってゆかねばならない品物には、それぞれに固有の価値があり、効用を合計したりしてもナンセンスなことが多いからだ。ヒゲソリと水筒の効用を合計してどうなるというのか。しかし、このような形式の問題が現実になることもある。

　当研究所ではこのナップザック問題の解法を研究して、以下のようなアルゴリズムを開発した。この方法は、基本的には繰り返し計算による収束接近法であり、途中で打ちきっても、それまでに計算した最良の組合せを保持している。

　①まず、適当な要素の組合せを選んでその合計量を計算する。
　②つぎに、要素のうちのひとつについて、
　　 1）未使用の要素と交代させるか
　　 2）使わなくするか
　　 3）新しく、別の未使用の要素を追加するか
　　の3種の方法のうち、最も、目標値に近づく方法を選択して、選択した要素の構成を変更する。
　③この方法を繰り返して、使用するホッパーの合計値を算出し、目標値からのずれが小さいものへと接近してゆく。改善が生じなくなれば終了である。

　この計算方法が現実的な時間内に有効な答を見出すのに利用できる。現在、実際の問題への適用を検討中である。