40 Algorithms Every Programmer Should Know

Using a greedy algorithm

If we use a greedy algorithm to solve the TSP, then, at each step, we can choose a city that seems reasonable, instead of finding a city to visit that will result in the best overall path. So, whenever we need to select a city, we just select the nearest city without bothering to verify that this choice will result in the globally optimal path.

The approach of the greedy algorithm is simple:

1. Start from any city.

2. At each step, keep building the tour by moving to the next city where the nearest neighborhood has not been visited before.

3. Repeat step 2.

Let's define a function named greedy_algorithm that can implement this logic:

def greedy_algorithm(cities, start=None):    C = start or first(cities)    tour = [C] unvisited ...