Why does the Greedy Algorithm fail to find the optimal solution for TSP?

Conditions

• The algorithm starts at any city.
• It repeatedly moves to the closest city that has not yet been visited.
• It returns to the starting city after all others are visited.

Reasoning, step by step

1. Start at an arbitrary city.
2. Find the nearest unvisited city and move to it.
3. Repeat the process until all cities are visited.
4. Return to the starting city to complete the route.
5. Observe that the resulting route may contain self-intersections, indicating sub-optimality.

Example

The video demonstrates the Greedy Algorithm on 8 cities, producing a route that crosses over itself, and states, "Greedy will produce a sub-optimal route (except in trivial cases)".

Common misconceptions

• Assuming that always making the locally optimal choice leads to the globally optimal solution.
• Believing that the Greedy Algorithm is always efficient and accurate for complex optimization problems.

Watch the explanation

Explore next

• How does a 2-Opt swap work to improve a route?
• What is the process of Local Search optimization and what is its main limitation?
• What is the Traveling Salesman Problem and how many possible routes are there for 8 cities?