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

• JorgeM
In summary, the TSP is a difficult problem that has been shown to be related to other optimization problems.
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.

Jorge M

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

Last edited:
JorgeM, DEvens and jim mcnamara
Tom.G said:
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

JorgeM said:
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.

## 1. What is an algorithm for finding the minimum distance over a set of randomly distributed points?

An algorithm for finding the minimum distance over a set of randomly distributed points is the closest pair algorithm. This algorithm works by first sorting the points by their x-coordinate, then dividing the points into two equal-sized sets. Next, it recursively finds the closest pair in each set, and finally compares the minimum distances between the two sets to find the overall minimum distance.

## 2. How does the closest pair algorithm work?

The closest pair algorithm works by dividing the points into two sets, then recursively finding the closest pair in each set. It then compares the minimum distances between the two sets to find the overall minimum distance. This algorithm is based on the divide and conquer approach, which is a common strategy for solving problems that involve large data sets.

## 3. Can the closest pair algorithm work with non-randomly distributed points?

Yes, the closest pair algorithm can work with non-randomly distributed points. However, it may not be as efficient as when working with randomly distributed points. This is because the algorithm relies on the assumption that the points are evenly distributed, and non-randomly distributed points may not follow this pattern.

## 4. What is the time complexity of the closest pair algorithm?

The time complexity of the closest pair algorithm is O(n log n), where n is the number of points in the set. This makes it a relatively efficient algorithm for finding the minimum distance over a set of points.

## 5. Are there any other algorithms for finding the minimum distance over a set of points?

Yes, there are other algorithms for finding the minimum distance over a set of points. Some of these include the brute force algorithm, which compares every pair of points in the set, and the sweep line algorithm, which uses a vertical line to divide the points and then finds the closest pair within each section. However, the closest pair algorithm is generally considered to be the most efficient for randomly distributed points.

• General Math
Replies
5
Views
1K
• Programming and Computer Science
Replies
29
Views
3K
• Introductory Physics Homework Help
Replies
5
Views
594
• General Math
Replies
4
Views
847
• General Math
Replies
1
Views
747
• Classical Physics
Replies
7
Views
936
• Programming and Computer Science
Replies
1
Views
2K
• Computing and Technology
Replies
5
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
15
Views
2K
• Astronomy and Astrophysics
Replies
12
Views
1K