Find
the
best approximate TSP solution you can for this graph.
| A B |
C D |
E
F | G H |
I J
+-----------+-----------+-----------+-----------+----------
A|
10 | 5 7 |
6 9 | 14
14
| 8 7
B|
10 |
14
12 | 9 16 |
15 9 |
2 5
-+-----------+-----------+-----------+-----------+----------
C|
5 14
|
11 | 10 4 |
19
19 | 11 11
D|
7 12 |
11 |
3 15 | 8
11 |
10 6
-+-----------+-----------+-----------+-----------+----------
E|
6 9 | 10
3
| 14 |
9 9 |
7 4
F|
9 16 | 4
15 |
14 |
23
22 | 14 15
-+-----------+-----------+-----------+-----------+----------
G|
14 15 | 19
8
| 9 23
| 8 |
14 11
H|
14 9 | 19
11
| 9 22 |
8 |
10 8
-+-----------+-----------+-----------+-----------+----------
I|
8 2 | 11
10
| 7 14 | 14
10
| 4
J|
7 5 | 11
6
| 4 15 |
11
8 | 4
DISTANCES BY NEAREST NEIGHBOR BEGINNING AT:
A 69
B 74
C 70
D 68
E 69
F 70
G 76
H 70
I 74
J 67
BEST ROUTE BY REPETITIVE NEAREST NEIGHBOR:
J 67
ROUTE BY NEAREST NEIGHBOR:
J -> E 4
E -> D 3
D -> A 7
A -> C 5
C -> F 4
F -> I 14
I -> B 2
B -> H 9
H -> G 8
G -> J 11
------
DISTANCE: 67
ROUTE FOUND BY CHEAPEST LINK:
A -> C 5
C -> F 4
F -> G 23
G -> H 8
H -> B 9
B -> I 2
I -> J 4
J -> E 4
E -> D 3
D -> A 7
------
DISTANCE: 69
Optimal Solution
E -> D 3
D -> G 8
G -> H 8
H -> J 8
J -> B 5
B -> I 2
I -> F 14
F -> C 4
C -> A 5
A -> E 6
------
DISTANCE: 63