「巡回セールスマン問題」は全ての都市を最短距離で巡回するルートを解く問題です。11都市あるので、ルートは1,814,400（＝10！/2）通りあります。30都市の場合は、4.42×1030通りになり、計算速度10テラFlopsという高速コンピュータをもってしても25京年以上かかるそうです。 有効な近似解を求めるアルゴリズムの一つは「遺伝的アルゴリズム」があります。「遺伝子が数式の最適解を見つける？」で遺伝的アルゴリズムは説明しています。 この他に「粘菌コンピュータ」や「DNDコンピュータ」など微生物やDNAを利用するコンピュータが研究されています。 粘菌については「眠くならない数学の本」で話題にしました。 DNAは、４つの塩基の組合せでできていますが、各都市を６つの塩基の分子で作製して、混ぜ合わせた後にPCR(ポリメラーゼ連鎖反応）によって解の候補になるDNAをつくり、分離して最適解を得る方法です。解になるDNAは瞬時にできるようですが、分離に時間がかかる律速があるようです。 微生物や生体物質は最短ルートを本能的に導き出す能力を保有しているようですね。
DNAコンピュータについてはこちら → http://www.s-graphics.co.jp/nanoelectronics/kaitai/dnacom/3.htm