Algorithm: shortest path between all points

algorithm artificial-intelligence path shortest-path
Jeroen picture Jeroen · Mar 23, 2010 · Viewed 21.9k times · Source

Suppose I have 10 points. I know the distance between each point.

I need to find the shortest possible route passing through all points.

I have tried a couple of algorithms (Dijkstra, Floyd Warshall,...) and they all give me the shortest path between start and end, but they don't make a route with all points on it.

Permutations work fine, but they are too resource-expensive.

What algorithms can you advise me to look into for this problem? Or is there a documented way to do this with the above-mentioned algorithms?

Answer

Graviton picture Graviton · Mar 23, 2010

Have a look at travelling salesman problem.

You may want to look into some of the heuristic solutions. They may not be able to give you 100% exact results, but often they can come up with good enough solutions (2 to 3 % away from optimal solutions) in a reasonable amount of time.

Related questions

What is the optimal algorithm for the game 2048?

I have recently stumbled upon the game 2048. You merge similar tiles by moving them in any of the four directions to make "bigger" tiles. After each move, a new tile appears at random empty position with a value of either 2 …

Read More
What are good examples of genetic algorithms/genetic programming solutions?

Genetic algorithms (GA) and genetic programming (GP) are interesting areas of research. I'd like to know about specific problems you have solved using GA/GP and what libraries/frameworks you used if you didn't roll your own. Questions: What problems …

Read More
What algorithm for a tic-tac-toe game can I use to determine the "best move" for the AI?

In a tic-tac-toe implementation I guess that the challenging part is to determine the best move to be played by the machine. What are the algorithms that can pursued? I'm looking into implementations from simple to complex. How would I …

Read More