HOME
OVERVIEW APPLICATIONS INTERACTIVE APPLETS HISTORY OF THE METHODS/FLOW CHART PUBLICATIONS EDUCATIONAL MATERIAL ACKNOWLEDGEMENTS ABOUT THE AUTHOR/CV Copyright: 19962010 J.A. Sethian 
Continuous Traveling Salesmen Problem
The problem has been the subject of centuries of study: it is difficult to find the optimal solution once the number of cities gets beyon a few dozen. Consequently, many heuristic algorithms have been posed which surrender trying to find the optimal solution in exchange for finding efficient algorithms to find very good solutions. The trade is usually worth it: spending 1000 hours of computer time to find the exact solution to a problem with 100 cities doesn't seem worth it compared to finding a very good solution to a problem with 10000 cities in a few minutes. Continuous Traveling Salesmen ProblemWe are interested in a different version of this problem. Suppose the cost of traveling between the cities themselves is not known? Imagine that there are obstacles in the domain, or that the cost of traveling from one point to the next depends on position. In the figure below, if the cost of traveling through different colored regions is different, then you don't even know the path from one city to the next, let alone how to travel through all of them.We can in fact solve this problem by embedding the Fast Marching Method inside an algorithm to solve the Traveling Salesmen Problem. There are two approaches:
Below, we show the results of doing exactly this. We embed the Fast Marching Method inside two different algorithms:
An Interactive Java Applet:Distribute some cities, pick a cost function, and find the cheapest path.Details: We consider a problem in which we are given a domain, a cost function which depends on position at each point in the domain, and a finite collection of points in the domain. The goal is to determine the cheapest closed path that visits each point in the domain once. This can be thought of as version of the Traveling Salesman Problem, in which an underlying known metric determines the cost of moving through each point of the domain, but in which the actual shortest path between cities is unknown at the outset. We describe algorithms for both a heuristic and an optimal solution to this problem. The runtime of the optimal algorithm is exponential, as expected, and the order of the heuristic algorithm is at worst case M*N log N, where M is the number of cities, and $N$ the size of the computational mesh used to approximate the solutions to the shortest paths problems. The average runtime of the heuristic algorithm is linear in both number of cities and size of the mesh. References

