# Greedy Heuristic for the Traveling Salesperson Problem

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.

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.

• What is your question? It would help if you provide a formal definition for these two methods. (or is that what your asking?) – 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.

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$.