Our map file system is expandable to an unlimited size,
allowing for both an unlimited number of points, as well
as unlimited distance between points. On top of this map
file, we've created a fast and elegant engine. Depending
on what you want to do, one of three actions will occur:
1. Shortest Route
When you tell the engine to calculate the shortest
route between point A and point B, the engine starts
cranking away, spiraling out of point A in an attempt
to reach point B. As soon as one of these threads
reaches point B, the thread adds the route it took to
get there to a list, and then sets a variable
containing the distance it took to get to point B.
Because the first route found may not be the fastest,
the engine continues.
Because a variable has been set with the length of the first route, all threads will terminate themselves if they exceed that number. If you are trying to get from Santa Fe to Los Alamos, and you've already found the route that only has to go 50 miles, then there is no sense in continuing a route that has already exceeded 50 miles.
If a shorter route is found, the engine will store the new route, and change the variable. Once all threads have finished, because they have gone as deep as possible, the engine goes through all the routes that where found and locates the shortest. This may not be necessary, because of the variable used to store the longest possible route, but it may be if a supercomputer can run enough threads at the same time.
Because a variable has been set with the length of the first route, all threads will terminate themselves if they exceed that number. If you are trying to get from Santa Fe to Los Alamos, and you've already found the route that only has to go 50 miles, then there is no sense in continuing a route that has already exceeded 50 miles.
If a shorter route is found, the engine will store the new route, and change the variable. Once all threads have finished, because they have gone as deep as possible, the engine goes through all the routes that where found and locates the shortest. This may not be necessary, because of the variable used to store the longest possible route, but it may be if a supercomputer can run enough threads at the same time.
2. Schedule
This function of the engine is rather simple. It will
just find the shortest route from the first item in
your schedule to the second, and from the second to
the third, and so on, until it finishes your route.
This could be useful if you had to, for example,
deliver and pick up some cargo at point A, then
proceed to point B, then to point C.
3. Salesmen
The third and perhaps the most useful function of the
engine is the ability to “salesman.” The engine will
take in a point, and then calculate the fastest route
to go to all other points, and then return to the
start point.
The method used is similar to the method used for getting the shortest route. The engine starts a stream of threads, discovering every possible route that can be taken from the start point. When the thread gets deep enough that it will no longer produce a unique route, it stops and saves its
route to a variable.
Once this lengthy task finishes, the engine will remove all the routes that do not pass over every point on the map. We call this “route skimming,” as it is comparable to skimming the top of a glass of liquid to filter the bad, floating particles out.
Once we have every route that goes to every point, we add the original starting point to the end of each route, so that we actually end where we started. After that, we simply go through each route, calculate its distance, and return the shortest one. And thus, the traveling salesman problem is solved.
The method used is similar to the method used for getting the shortest route. The engine starts a stream of threads, discovering every possible route that can be taken from the start point. When the thread gets deep enough that it will no longer produce a unique route, it stops and saves its
route to a variable.
Once this lengthy task finishes, the engine will remove all the routes that do not pass over every point on the map. We call this “route skimming,” as it is comparable to skimming the top of a glass of liquid to filter the bad, floating particles out.
Once we have every route that goes to every point, we add the original starting point to the end of each route, so that we actually end where we started. After that, we simply go through each route, calculate its distance, and return the shortest one. And thus, the traveling salesman problem is solved.