I too see this as the TSP--in fact, it's useful to question whether it's topologically equivalent. In the TSP, a travelling salesman must hawk his wares in 20 cites across the country while paying his own expenses. He wants to keep fuel costs to a minimum (he's driving) and he wants to hit every city at least once.
One thing that occurs to me is that, in the TSP, the salesman can hit any city from any other city and incur the cost of the fuel to drive there. In your problem, if your "salesman" is in cell (1,2) and wants to jump over to cell (3,5), it's not allowed. He can only visit the "directly connected" cities. So they are topologically different problems, and that leads me to think that this problem's solution is not on the order of n! as the TSP is.
Here is a
for more eloquent discourse on this algorithm than I could deliver.
Instead, I will get off the topic and suggest a solution to the TSP that others might find interesting. If we accept there's no way to get the One Best Answer to the TSP because it's too much calculatin', is there a way to get close? Yes--through genetics!
How's it work? Ok, imagine that we make a list of the 20 cities that represents the order in which the TS will visit them. For any such list, we can quickly calculate the total distance the TS will cover. Next, imagine we create a pool of such lists, say 500 of them, and each one represents an itinerary that is randomly generated. Next, we sort the pool of these lists from shortest distance to longest. Since we're searching for the shortest possible path, we can define the "value of" a pool as the length of its shortest itinerary.
Here's the genetic part. If we "select out" the longest half of the pool by killing them, we are left with the 250 shortest itineraries and 250 empty spots in the pool. Next, we copy each of the remaining 250 lists to one of the empty spots, but in doing so, we introduce a "mutation"--we alter the copy in some way. We can use a "point mutation", simply swapping two adjacent cities, or a "crossover mutation", in which an entire subsequence of that itinerary is moved...we could even come up with a rule that let's surviving members in the pool "sexually reproduce" and combine their lists. Always reserve a couple of spots for totally new, randomly generated itineraries to introduce a different kind of diversity.
This process of selecting out some percentage of the pool as weak and replacing their spots with mutated copies of the "stronger" members is an evolution. All you have to do now is repeat the evolutions until some criteria is met, say, the value of a pool varies by less than 1% over 5 evolutions.
It is surprising how quickly this algorithm homes in on the shortest path. Whereas the brute force method would take billions and billions of years to run to completion for just 20 cities, this can oftentimes return an itinerary within a few percent of the shortest possible path in under a minute on a modern desktop computer. Furthermore, you can design maps that intentionally have an obvious shortest path built in and
test to see how long this algorithm takes to find it...and you'll be surprised at the results.
It helps a lot if you make sure every aspect of this evolutionary algorithm can be finetuned. For instance, instead of killing off half of the population in each evolution, make that number configurable and try different values. Perform the different kinds of mutations probabilistically...a point mutation will occur 50% of the time a copy is made, a crossover 10%. In this way, one copy might incur both, increasing the diversity. And on and on...very fun to play with.
Also, you can modify this approach to great effect by setting up different kinds of pools. The above pool would be a random pool, but you could also set up a matrix pool in which you don't generate lists, you generate matrices that approximately correspond (with some randomness, obviously) to where cities fall geographically on the map. In this case, instead of simply adding up the distance for a list, you use djikstra's algo to get the shortest path between distant cities to set up subsequences that are likely to yield good results.
sev
[ February 25, 2004: Message edited by: sever oon ]
