# What is the difference between nearest and cheapest insertion algorithms for a Traveling salesman problem?

I know that in the cheapest insertion algorithm we include the node which is not in the "base group" that has smaller cost given all possible combinations, and for the nearest we include the node with smaller cost. So, do they differ only in how combinations are made?

For example, I have the following weighted matrix graph:

     2  13  14  17  20
2  0.0 Inf Inf 1.9 1.7
13 Inf 0.0 7.3 7.4 7.2
14 Inf 7.3 0.0 7.7 7.8
17 1.9 7.4 7.7 0.0 9.2
20 1.7 7.2 7.8 9.2 0.0


If I start from node 2 from each method:

Nearest

1) 2-20-2

2.1) 2-17-20-2 = 12,8

2.2) 2-17-20-2 = 12,8 *Choosen

3.1) 2-13-20-17-2 = Inf

3.2) 2-20-13-17-2 = 18,2 *Choosen

3.3) 2-20-17-13-2 = Inf

4.1) 2-14-20-13-17-2 = Inf

4.2) 2-20-14-13-17-2 = 26,1

4.3) 2-20-13-14-17-2 = 25,8 *Choosen one

4.4) 2-20-13-17-14-2 = Inf

Cheapest

1) 2-20-2 2.1.a) 2-13-20-2 = Inf

2.1.b) 2-20-13-2 = Inf

2.2.a) 2-14-20-2 = Inf

2.2.b) 2-20-14-2 = Inf

2.3.a) 2-17-20-2 = 12,8

2.3.b) 2-20-17-2 = 12,8

So, with the cheapest approach, do I explicitly make all combinations?

• Can you give a reference to your heuristics? Presumably, these references will outline what these heuristics are in more detail; but the nature of heuristics is such that they are quite pliable. – Yuval Filmus Sep 10 '19 at 15:25