0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 10 at 15:25

Your Answer

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

Browse other questions tagged or ask your own question.