A Shiny New Engine for OptiMap

By   February 28, 2009

OptiMap, the free TSP solver for Google Maps, used to guarantee the optimal solution for up to 9 locations only. That number has now been increased to 15. If you had more than that number of locations, you would get a solution close to the optimal (often the optimal).

The new OptiMap uses the dynamic programming solution to the TSP for problems of size 10 – 15. I tested various values for the cutoff in different browsers, and I could have set it differently. The main problem with the dynamic programming solution is its memory footprint. It uses O(n * 2^n) memory, which gets problematic around n = 15 in JavaScript (n being the number of locations, of course). This is especially true on smaller devices like smartphones. It would probably work well with n = 18 on most desktop computers and browsers, but I haven’t gotten around to making a dedicated smartphone version yet.

There is also a noticable difference between different browsers in JavaScript execution speed. Safari 4 is the fastest browser I tried so far. I haven’t tested Google Chrome yet, but I suspect it is also in the super-fast category. Once Opera comes with its Carakan JavaScript engine, I will run a speed test on OptiMap and publish the results here. Maybe I should set n automatically based on the user’s browser?

2 Comments on “A Shiny New Engine for OptiMap

  1. Rodrigo Mccraight

    Not to hijack this thread, but, I need Atlanta dentists and I can’t figure out how to find them… has anyone ever heard of this Atlanta dental care? They’reIt’s based out of Atlanta, near me. I am not able to find reviews on them – Exceptional Smile LLC, 4420 Bankers Cir, Atlanta, GA 30360 – (678) 841-8800

  2. idesentupidorauberlandia

    It’s actually a great and helpful piece of info. I am satisfied that you simply shared this useful information with us. Please stay us up to date like this. Thank you for sharing.

Comments are closed.