We're studying Heuristic in my Theoretical CS class, more specifically Greedy-Algorithms for the Traveling Salesperson Problem. The first one is the "next neighbor heuristic", where you start at any given point and connect it with the nearest point and then connect that to the next nearest one until all points are covered - then going back to the first point.

enter image description here

Where "P" is the starting and ending point.

The second approach, which gives the optimal answer, is the "closest pair of points" or "Engstes-Paar-Heuristic". I don't understand how this approach works because from the looks of it, you simply make a straight line but I don't understand this approach.

Sorry about the possible name changes, it's originally in German.

enter image description here

  • $\begingroup$ What is your question? It would help if you provide a formal definition for these two methods. (or is that what your asking?) $\endgroup$ – Discrete lizard Mar 5 '18 at 8:33

First let's name your points $P_A$, $P_B$, $P$, $P_C$, and $P_D$ (from left to right).

With the first heuristic you start at one point ($P$) and move to the closest point. From that new point, you move to the next closest point, and so on and so forth.

With the second heuristic you again start at one point ($P$) but you move to the point closest to one of the two ends of your current path. It is a simple improvement over the first heuristic.

For your example:

  1. Current path: $P$. Closest point to $P$: $P_B$.
  2. Current path: $P-P_B$. Closest point to $P$ or $P_B$: $P_C$.
  3. Current path: $P_B-P-P_C$. Closest point to $P_B$ or $P_C$: $P_A$.
  4. Current path: $P_A-P_B-P-P_C$. Closest point to $P_A$ or $P_C$: $P_D$.
  5. Current path: $P_A-P_B-P-P_C-P_D$. The only choice left is to connect $P_A$ to $P_D$.

The example shows the Travelling salesman problem for the case that all points are on a straight line. That’s rarely the case. And you cant just move the points to solve the problem, they are where they are.

The closest pair heuristics seems to be that you find the closest connection and add it, then again the closest connection that is still available and so on.

You can easily show that this is optimal if all the points are on a straight line, but usually it’s not.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.