Here is a graph representing ten cities with distances between them 60 70 30 10

Question

Here is a graph representing ten cities with distances between them 60 70 30 10 20 70 20 70 Note that not all possible distances are provided (for example, cities 3 and 9 are not connected by an edge on this graph). Assume that you can only travel directly from city A to city B if these two cities are connected by an edge. As in class, the task is to determine a path that visits every city and returns to the original city while traversing as little total distance as possible This graph is way too big to enumerate all Hamiltonian circuits like we did in class, determine their lengths, and pick the shortest one. So, you need a strategy. Your assignment is to come up with a strategy, and use it to come up with a good path. I do not expect you to completely solve the problem. That is, I do not expect you to actually find the shortest path. All I expect is that you formulate a strategy, describe the strategy, and implement it to see what path you come up with. Also, I will award bonus points for each additional strategy that you formulate and implement!

Explanation / Answer

Routes and distances 1 and 2 50 2 and 10 70 5 and 7 60 1 and 3 60 3 and 4 20 6 and 7 70 1 and 8 70 3 and 5 70 6 and 8 70 1 and 9 30 3 and 10 40 7 and 8 40 1 and 10 10 4 and 5 20 7 and 9 50 2 and 3 10 4 and 6 70 8 and 9 30 2 and 4 90 4 and 7 80 8 and 10 60 2 and 5 70 5 and 6 70 9 and 10 20 Apart from using Hamiltonian Circuits , the following Strategies are formed. Total Distance covered Strategy 1 : Go outer cities first and then inner cities circularly 470 Strategy2: Go inner cities and then outer cities circularly 490 Strategy 3: Form Triangles and connect them 420 Strategy 4: Visit by forming Trapeziums Route 1 390 Strategy 5: Visit by forming Trapeziums Route 2 490 Strategy 6: Pick up possible shortest route from each node 380 Strategy 7: Shortest possible Trianges 390 Strategy 1 Strategy 2 Strategy 3 1 to 8 70 1 to 10 10 1 to 9 to 8 30 30 60 8 to 6 70 10 to 3 40 8 to 7 to 6 40 70 110 6 to 5 70 3 to 4 20 6 to 4 to 5 70 20 90 5 to 2 70 4 to 7 80 5 to 3 to 2 70 10 80 2to 3 10 7 to 9 50 2 to 10 to 1 70 10 80 3 to 4 20 9 to 8 30 4 to 7 80 8 to 6 70 Total 420 7 to 9 50 6 to 5 70 9 to 10 20 5 to 2 70 Strategy 7 10 to 1 10 2 to 1 50 1 to 10 to 8 10 60 70 8 to 9 to 7 30 50 80 Total 470 Total 490 7 to 6 to 5 70 70 140 5 to 4 to 3 20 20 40 3 to 2 to 1 10 50 60 Total 390 Strategy 4 Strategy 5 Strategy 6 1 to 10 10 1 to 9 30 1 to 10 10 10 to 9 70 9 to 10 20 10 to 9 20 9 to 8 30 10 to 3 40 9 to 8 30 8 to 7 40 3 to 4 20 8 to 7 40 7 to 6 70 4 to 7 80 7 to 6 70 6 to 5 70 7 to 8 40 6 to 4 70 5 to 4 20 8 to 6 70 4 to 5 20 4 to 3 20 6 to 5 70 5 to 2 70 3 to 2 10 5 to 2 70 2 to 1 50 2 to 1 50 2 to 1 50 Total 390 Total 490 Total 380 Conclusion: Strategy 6: Pick up possible shortest route from each node Total Distance cobered 380

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.