CTGについて組合せ計算アルゴリズム私たちの生活や産業活動のなかには、線形計画法、ダイナミックプログラミング、整数計画法などの数学的な手法が利用できる場合がある。並んで、企業や国家の計画立案にも利用されている。このなかで、組合せ計算の問題というのがある。この種類の問題の中には、組合せの数が巨大になるため実際的な時間の制限のなかでは解が得られないものがある。「巡回セールスマン問題」はその代表的な問題である。「地図があって、セールスマンが行かねばならない複数の客先の場所とその道路がわかっている。1,000を越えれば、その組合せの数は極めて大きな数になってくる。このような問題を解くために、数学者達は知恵を振り絞ってきた。1980年代には米国で「カーマーカー特許」という線形計画法の解法を特許にするという事件まで持ち上がっている。「山男がn種類の品物(i=1,2,3...n)をナップザックに詰めて登山に出かけようとしている。持ち運べる質量は最大Mグラムであり、品物iの1個の質量はCiグラムである。実際、旅行や登山に出かける前にこの問題が現実になることは少ない。旅行や登山に持ってゆかねばならない品物には、それぞれに固有の価値があり、効用を合計したりしてもナンセンスなことが多いからだ。ヒゲソリと水筒の効用を合計してどうなるというのか。このような形式の問題が現実になることもある。当研究所ではこのナップザック問題の解法を研究して、以下のようなアルゴリズムを開発した。この方法は、基本的には繰り返し計算による収束接近法であり、途中で打ちきっても、それまでに計算した最良の組合せを保持している。1まず、適当な要素の組合せを選んでその合計量を計算する。2つぎに、要素のうちのひとつについて、1)未使用の要素と交代させるか2)使わなくするか3)新しく、別の未使用の要素を追加するかの3種の方法のうち、最も、目標値に近づく方法を選択して、選択した要素の構成を変更する。3この方法を繰り返して、使用するホッパーの合計値を算出し、目標値からのずれが小さいものへと接近してゆく。改善が生じなくなれば終了である。この計算方法が現実的な時間内に有効な答を見出すのに利用できる。