2009年5月26日火曜日

巡回セールスマン問題を解く(7)

 結局、ガッツリと指導してもらったおかげで、10,000都市の問題も2,3分ぐらいで解けるようになった。1,000都市なら数秒で解ける。しかし、実際の所、一人で1,000件も回れないとも思う。実際にリアルタイムに解こうと思うと、都市間のコスト設定(ルート計算)の方が膨大に時間がかかってしまう。札幌近郊で50点をランダムに作成して、その50地点を回る問題でデモしようと思ったら、50x49=2,450通りの最短ルート計算に1分近く時間がかかってしまい、巡回セールスマン問題のデモとしては、面白みに欠けてしまった。
 都市間のコストは、直線距離で代用しても良いのだが、作成したルーチンは一方通行も含めてコストをまじめに利用して計算しているので、勿体無い感じもする。300地点のコストを事前に計算しておいて、ランダムに100地点を選んで巡回セールスマン問題を解くデモを作成する予定です。時間があれば、都市番号と都市間コストを貰って、結果を返すAPIのデモも考えていますが、リソースが無いので、そこまで手が回るかどうか…(仕事になるなら、優先してこっちを叩くんだけど…)。最終的には、Windows Azure ベースで、B2B向けサービス構築しようと考えてます。

0 件のコメント: