巡回セールスマン問題を解く（３）

　今の解法は、都市のノード間を直線距離で計算して、最適解を導くというものなのですが、実際の道路は直線で結ばれているわけなんてないのです。自前で書いたTSPルーチン、悪くは無いと思うのですが、pgRouting の TSPルーチンと比較すると、ことごとく負けてしまいました。直線距離で最適解を導くという勝負においては負けていないと思うのですが（地図上で経路を見て比較しただけで厳密な検証はまだ）、実道路にあてはめてみると pgRouting の TSPの方が良いです。
　こういう部分で、pgRouting の TSPを開発した方の思い入れをなんとなく感じてしまいます。pgRouting のコードは、実計算部分の方をほとんど見ていませんが、プログラマーならではの、ある種の会話をした気分です。
　とは言え、負けは負けで悔しいので、直線距離での計算から、実距離での計算へ方針を転換する事にしました。都市数Ｎに対して、Ｎ×Ｎ通りの距離を計算しなければならないですが、ある都市からの最短経路を計算するという事は、結局、他の全都市への最短経路を計算する事でもあります。よって、実距離の計算はＮ回＋α行えば良く、小規模であれば今のコンピュータだと一瞬で終わります。なるべく曖昧な要因は排除できるなら排除した方がいい。これで負けたら諦めもつくってもんです。