Algorithm for the min. distance over a set of points randomly distributed

[JorgeM]

TL;DR Summary

Hello there, I need to identify the best path for the minimun distance over a set of points randomly distributed over an X-Y plane.

The only restrictions are:
-There are N points randomly distributed over an X-Y plane and it is necesary to pass every point at least 1 time, in order to get the path of the minimun distance throught all of them.
-If does not matter how many times you pass any of this points.
-You have to pass every point at least one time.
-The only known point is (0,0) as the first.

How may I solve this algorithm? I have been reading and I found something about Djikstra's algorithm But I am afraid it is only for getting the best path from the point A to the point B over a set of points without taking care of passing by all the points, or Am I wrong?

If you know any algorithm that could solve this problem, I would thank you for telling me its name.

Thanks for your advise.

Jorge M

 

[Tom.G]

Do a Google search for: Traveling Salesman Problem
Also see an animation at: https://en.wikipedia.org/wiki/Travelling_salesman_problem

Although your problem is a relaxed version, Traveling Salesman is a classic problem and, IIRC, was only recently shown to be NP Hard, rather than the long-standing assumption of being NP Complete.

Have Fun!
Tom

 

[JorgeM]

Do a Google search for: Traveling Salesman Problem
Also see an animation at: https://en.wikipedia.org/wiki/Travelling_salesman_problem

Although your problem is a relaxed version, Traveling Salesman is a classic problem and, IIRC, was only recently shown to be NP Hard, rather than the long-standing assumption of being NP Complete.

Have Fun!
Tom

I started to read a lot about the different methods for solving this problem. I think I'm going to use the one that requires Marcov's chains.
Thanks a lot

 

[Klystron]

I started to read a lot about the different methods for solving this problem. I think I'm going to use the one that requires Marcov's chains.
Thanks a lot

A Google search combining 'TSP' and 'Markov chains' found several interesting papers including this heuristic algorithm paper from 1991 where Markov chains embed in the Monte Carlo search method.

It has often been the case that progress on the TSP has led to progress on other combinatorial optimization (CO) problems and on more general optimization problems. In this way, the TSP is a playground for the study of NP-complete problems. Though the present work concentrates on the TSP, a number of our ideas are general and apply to all optimization problems.