Well I have a pathfinding problem that involves finding the shortest path to get to all points in a list. The problem isn't to find the path from point to point but what order you need to go to all the points in order to minimize distance.

The only reasonable solution I can think of is the brute force way which is to find the path from every point to every other point and then test every combination to figure out which combination is the shortest. This obviously is very slow and the work required grows very quickly with the number of points in the list and even if it's precomputed it could take ridiculus amounts of time if the list grows past a small handful of points.

I was also suggested by someone that I should just start from an initial point then solve the paths to the nearest few points and just go with the path that is solved to be the shortest. This seemed good at first but after thinking about it this solution would only get the shortest path for the majority of the points and leave a few distant points remaining which would probably have very long paths to get to whereas if they had been gone to earlier it wouldn't have been as far. Here's a cheap example with poor ascii art :). The periods are points that need to be gone to.


.............................




.


If the algorithm starts with the upper left point it would take the path to the right then go to the distant point below the line. This is a much longer path than if it would have just went to the distant point from the initial point first then continue with the rest.

So anyone know of any slick algorithms to handling this problem :P?