Section 2.3 - Helping Traveling Salesman
Instructions
- The first video below explains the concepts in this section.
- This page also includes exercises that you should attempt to solve yourself. You can check your answers and watch the videos explaining how to solve the exercises.
Concepts
- Finding low cost Hamiltonian circuits for weighted graphs
- Nearest Neighbor Algorithm
- Sorted Edges Algorithm
Exercises
Directions: You should try to solve each problem first, and then click "Reveal Answer" to check your answer. You can click "Watch Video" if you need help with a problem.
1. Use the Nearest Neighbor method to find a low cost Hamiltonian circuit starting at B.
BDACB
cost: 45
cost: 45
2. Use the Nearest Neighbor method to find a low cost Hamiltonian circuit starting at D.
DACBD
cost: 19
cost: 19
3. Use the Nearest Neighbor method to find a low cost Hamiltonian circuit starting at F.
FEABDCF
cost: 1264
cost: 1264
4. Use the Nearest Neighbor method to find a low cost Hamiltonian circuit starting at C.
CEFABDC
cost: 1250
cost: 1250
5.
Use the table and the Nearest Neighbor Algorithm to solve the TSP starting at Malaga.
| Southern Iceland | Toulouse | Bologna | Malaga | Innsbruck | Petra | |
|---|---|---|---|---|---|---|
| Southern Iceland | 0 | 238 | 255 | 280 | 237 | 423 |
| Toulouse, France | 238 | 0 | 105 | 113 | 111 | 283 |
| Bologna, Italy | 255 | 105 | 0 | 160 | 47 | 234 |
| Malaga, Spain | 280 | 113 | 160 | 0 | 172 | 311 |
| Innsbruck, Austria | 237 | 111 | 47 | 172 | 0 | 245 |
| Petra, Jordan | 423 | 283 | 234 | 311 | 245 | 0 |
MTBI(SI)PM
cost: 1236
cost: 1236
6.
Use the table and the Nearest Neighbor Algorithm to solve the TSP starting at B.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 173 | 186 | 78 | 111 |
| B | 173 | 0 | 90 | 39 | 199 |
| C | 186 | 90 | 0 | 162 | 44 |
| D | 78 | 39 | 162 | 0 | 55 |
| E | 111 | 199 | 44 | 55 | 0 |
BDECAB
cost: 497
cost: 497
7.
Use the table and the Nearest Neighbor Algorithm to solve the TSP starting at A.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 173 | 186 | 78 | 111 |
| B | 173 | 0 | 90 | 39 | 199 |
| C | 186 | 90 | 0 | 162 | 44 |
| D | 78 | 39 | 162 | 0 | 55 |
| E | 111 | 199 | 44 | 55 | 0 |
ADBCEA
cost: 362
cost: 362
8. Use the Sorted Edges method to find a low cost Hamiltonian circuit.
ADBCA
cost: 45
cost: 45
9. Use the Sorted Edges method to find a low cost Hamiltonian circuit.
BACDB
cost: 17
cost: 17
10. Use the Sorted Edges method to find a low cost Hamiltonian circuit.
Video Errata: Around 5:35, the presenter should have x'd the 252, instead of checking it.
ABCDFEA
cost: 1284
cost: 1284
11. Use the Sorted Edges method to find a low cost Hamiltonian circuit.
ABCDA
Cost: 123.5
Cost: 123.5
12. By the brute force method, the optimal route has cost 76. Use the Nearest Neighbor method (at A) and the Sorted Edges method to solve the TSP. How do they compare to the optimal route?
Video Errata: At 2:08, the total for the Nearest Neighbor method should be 98, not 96.
Nearest Neighbors: ACBDEA for cost of 98
Sorted Edges: ABEDCA for cost of 81
Neither algorithm found the optimal route of cost 76.
Sorted Edges: ABEDCA for cost of 81
Neither algorithm found the optimal route of cost 76.