Traveling-Salesman Problem

 

1

 

2

 

4

 

3

 

Distance matrix

 

Analysis:

 

1

 

2

 

3

 

4

 

Let k represents the unvisited city

 

1

 

\

 

40

 

55

 

28

 

we choose, and (p, q) represents the

 

exist link to be inserted.

 

2

 

40

 

\

 

16

 

7

 

We definite:

 

3

 

55

 

16

 

\

 

66

 

H (p, q, k)= d (p, k) +d (k, q) ­d (p, q)

 

4

 

28

 

7

 

66

 

\

 

which is the distance increment.