Quote:
Originally posted by dcann1222@Aug 18 2003, 10:08 PM
Wow, that's great. Are you checking all possible routes? My script solves the 5-destination route in 0.02 seconds, but it grows exponentially from there.
|
No, I don't check all possible routes. I construct a modified minimum spanning tree and continue modifying it (adding shortest edges) until I get a straight path that contains all the nodes. I didn't have time to do additional pruning on my MST so I just keep adding shortest edges until there exists a straight line containing all the nodes instead of forcing a tree structure so it still has an exponential worst case. But in the average case it runs quickly.
Well, that's what I do for larger numbers of destinations. For smaller numbers of destinations it's okay to check all possible routes since it can be done quickly. I basically cap out at 40 seconds of searching for the best route and then switch to my MST approach.