Given an undirected graph G whose vertices represent towns and edges represent r

Question

Given an undirected graph G whose vertices represent towns and edges represent roads between two towns. Each edges is marked by the distance between two towns. The traveling salesman wants to leave one of these towns, to visit each other town exactly once, and to arrive back at the starting point (town) with the minimal total distances. Consider the following greedy strategy. At each step, the salesman chooses to visit the town that is adjacent to his current point (town) and with the minimum distance to his current point (town). Does this greedy algorithm always produce the optimal solution? If yes, give your explanation. Or if not, give a counter example.

Explanation / Answer

Greedy algorithm "Travelling sales man problem" will not give always optimal solution.

Consider this conter example..

Assume we have four cities, n =4 and distance bwetween them are..
AB-200 , AC-201, BC-200, AD-400, BD-201, CD-300

Then travelling sales man probleam will produce output like
Tour ABCDA is 1100 (since 200+200+300+400=1100)
But it very worst unique solution since other paths are better than this..
ABDCA->902 and ACBDA->1002

So it clearly shown that travelling sales man nearest neighbour problem produces uniqueworst possible tour.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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