Is Mapquest's "driving directions" program just a highly elaborate application of the "travelling saleman" problem?

[notfred]

See title.

 

[Colt45]

what is the travelling salesman problem

 

[pulse8]

Originally posted by: Colt45
what is the travelling salesman problem

 

[notfred]

Originally posted by: pulse8

Originally posted by: Colt45
what is the travelling salesman problem

One site.
Many more.

 

[notfred]

Did the links scare everyone off?

 

[Phoenix86]

Yes and I guess so... Which is why it isn't accurate, but it'll get you there.

 

[Achtung]

Yeah I'm guessing it uses a similar algorithm, although in travelling salesman I thought you had to visit all the stops exactly once. Mapquest just finds the shortest route between points, and there is a similar algorithm for that which I remember from AI class, just not the exact name. Actually there are a couple of different ones, some quick and dirty, others longer but more exact.

 

[bigredguy]

Originally posted by: Achtung
Yeah I'm guessing it uses a similar algorithm, although in travelling salesman I thought you had to visit all the stops exactly once. Mapquest just finds the shortest route between points, and there is a similar algorithm for that which I remember from AI class, just not the exact name. Actually there are a couple of different ones, some quick and dirty, others longer but more exact.

There has to be more than just that because mapquest will often tell me to take the freeway even though it is shorter to just take regular streets.

 

[notfred]

Originally posted by: bigredguy

Originally posted by: Achtung
Yeah I'm guessing it uses a similar algorithm, although in travelling salesman I thought you had to visit all the stops exactly once. Mapquest just finds the shortest route between points, and there is a similar algorithm for that which I remember from AI class, just not the exact name. Actually there are a couple of different ones, some quick and dirty, others longer but more exact.

There has to be more than just that because mapquest will often tell me to take the freeway even though it is shorter to just take regular streets.

"shorter" isn't neccesarily measured by distance between points,but possibly by time between points.

 

[arcain]

Yes. Why do you ask? There is not much to discuss, it's not really a subjective matter.

Achtung: A*, Depth First Search, Breadth First Search are probably the more fundamental ones. I'm sure Mapquests algorithms are based on them and heavily heuristical in nature. Otherwise it would take far too long to calculate driving directions from Los Angeles to New York.

 

[arcain]

Originally posted by: notfred

Originally posted by: bigredguy

Originally posted by: Achtung
Yeah I'm guessing it uses a similar algorithm, although in travelling salesman I thought you had to visit all the stops exactly once. Mapquest just finds the shortest route between points, and there is a similar algorithm for that which I remember from AI class, just not the exact name. Actually there are a couple of different ones, some quick and dirty, others longer but more exact.

There has to be more than just that because mapquest will often tell me to take the freeway even though it is shorter to just take regular streets.

"shorter" isn't neccesarily measured by distance between points,but possibly by time between points.

The searching would be the same.. you either weight the paths by distance or by time (distance / speed). You could potential search for the "simplest" route, the one with fewest turns, which would translate to the path with the shortest depth.

 

[Martin]

I would think they use an algorithm based on Dijkstras algorithm. Since its O(n^2) they consider major intersections as nodes to save time, or something along those lines.

 

[RaiderJ]

Gah! I hated algorithms in college. Worst class ever! Good thing you could find homework solutions on the net. I think Google passed more of my class than I did!

 

[Ameesh]

I don't think it is, TS requires you hit all nodes in the graph, mapquest doesn't, mapquest can just simply use a greedy algorithm and its good.