# How does the nearest insertion heuristic for TSP work?

In my theoretical computer science class and we were covering "Heuristics". In it we covered "Greedy Heuristics" for the "Vertex Cover Problem", "Interval Scheduling" and the "Traveling Salesperson Problem".

In it we covered the "Nearest Neighbor", "Closest Pair" and "Insertion" heuristics approach to solve the TSP Problem.

The first two are quite clear - the first one connects the starting point to the nearest neighbor and then connect that to its neighbor and so on. The second one you move to the point closest to one of the two ends of your current path. But I don't understand how the third one actually works.

The example is as follows: And continue this five more times and you get the answer below. • @Raphael, Seriously? Why would the images be useful? It only clutters the whole post. My edit simplified this question for further readers not to lose time. Please, reject my edit of the answer below, because, at this point, I added my own answer. Also, your edit even contains a typo in the title... – nbro Nov 12 '18 at 13:49
• You give the example, but not what exactly your question about it is. "I don't understand" is not enough and, as nbro notes correctly, makes the example useless. Please add which step you don't follow, and why. – Raphael Nov 12 '18 at 15:23
• @nbro It is okay to edit posts of others to make minor adjustments. It is usually not okay the completely change them; posting your own answer (or question) is exactly the right thing to do in such cases. – Raphael Nov 12 '18 at 15:23

1. We're looking to construct a cycle $C$ containing all the nodes of our problem. We will do this by initially constructing a small cycle and slowly adding nodes to it until it contains all the nodes. We start by choosing some starting node $N$ and adding it to $C$. $C$ now contains a single node, $N$.
2. We want to add to $C$ the node which will increase its length the least. To do this we need to find which node to add to our cycle and then figure out where in the cycle to put it. We select this node by choosing the node (not in $C$) which is the closest to any node in $C$. We then insert this node between two nodes in $C$ such that the increase in length is minimal. More formally: Let $k$ be the node we selected. Find an edge $(i,j)$ such that $d_{ik}+d_{kj}-d_{ij}$ is minimal.
3. Add $k$ to $C$, remove edge $(i,j)$, and add edges $(i,k)$ and $(k,j)$.
4. If $C$ contains all the nodes, stop. Otherwise, go to 2.