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
You should be able to beat 70.