前話でNP問題に触れたが、NP問題は証明されていない（解決されていない）数学の問題の集合体である。その問題の数は、数百とも数千ともいわれているが、その数に意味はない。何故なら、１つの問題が解ければ全ての問題が解けるだろうと考えられているからである。NP問題に属する各問題はクラスに区分されている。ここでNP問題の詳細を説明するのは億劫であるから簡単にするが、巡回セールスマン問題のクラスはNP困難に属している。最も解決が難しいだろうといわれているクラスである。ところがクラスにNP完全というものがあって、巡回セールスマン問題は完全なNP問題の仲間とは見做されていないようである。とここまでが、巡回セールスマン問題のあまりにも簡単な紹介であるが、この紹介は俗世間との関係でわたしと巡回セールスマン問題の関係ではない。
　わたしと巡回セールスマン問題との関係は２５年にもわたった。この期間がどれほど長いかというとわたしの夫婦生活が１２年で終焉を迎えたことを考えれば明らかである。巡回セールスマン問題に興味を持って取り組む研究者は結構いるらしいのだが、長続きはしないらしい。特に大学などで職を得ているものは長くて３～４年の研究期間の末に解決することを諦めるようである。何故なら、結果を出せないから職を失う可能性があるというのが、人から聞いた話である。従って、２５年もの間巡回セールスマン問題と関係を持っていたわたしは珍しい部類に入るものと思われる。
　巡回セールスマン問題とは次のような問題である。
「都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である」 つまり、「複数のノード（点）があるとき、最も総距離が最短の一筆書きをしなさい」ということであるが、一筆書きは線が交差してもよいことになっている。実は線が交差する一筆書きは最短の経路とならないのだが、命題はそれを許している。尚、巡回セールスマン問題について詳しいことを知りたい方はWIKIなどを参照することをお勧めしたい。わたしの説明ではますます混乱すると思うからである。
　 何故に一筆書きがこうも大きな問題になるかというと、それは計算量の膨大さにある。N点数のノードの一筆書きの組み合わせは、ざっとN！（階乗）となる。階乗とは１からNまでを全て掛け算しなさいという式で、エクセルなどで計算させるとNが５０点を超えないうちにエラーとなる。あまりにも大きな数にエクセルも嫌気がさすようなのだ。そのエクセルも嫌気がさす数の中から最短の経路を探さねばならないのだから問題は大きいことになる。まともに計算すると現代のスーパーコンピュータでもNが３桁の計算は無理なようである。スーパーコンピュータが答えを出す時間は、この宇宙が何回か創造と消滅を繰り返すほどのものであるらしい。さて、次話から本題に入りたい。