1) Let n = number of Cities 2) For each city j 2a) Start at city j 2b) Visit the

Question

1) Let n = number of Cities 2) For each city j 2a) Start at city j 2b) Visit the unvisited city closest to the city most recently visited, breaking ties arbitrarily 2c) Stop when all cities have been visited 2d) Calculate the cost of the cycle you have created 3) Report the cheapest of the n cycles created in this way Use the Nearest Neighbor Heuristic to find a solution to the symmetric TSP in volving the following data: To From City 1 City 2 City 3 City 4 City 5 City 1 City 2 City 3 City 4 City 5 50 40 35 0 30 45 25 25 50 50 40 40 40 45 35 65 80 0

Explanation / Answer

Start from City 1

Route considering nearest neighbour is 1-2-3-4-5-1 with cost = 25+40+35+80+30=210

Start from City 2

Route considering nearest neighbour is 2-1-5-3-4-2 with cost = 25+30+65+35+40=195 -------(1)

Start from City 3

Route considering nearest neighbour is 3-4-2-1-5-3 with cost = 35+40+25+30+65=195 -------(2)

Start from City 4

Route considering nearest neighbour is 4-3-2-1-5-4 with cost = 35+40+25+30+80=210

Start from City 5

Route considering nearest neighbour is 5-2-1-3-4-5 with cost = 45+25+50+35+80=235

Anyone of (1) or (2) can be select as cheapest cost path.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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