Home / Computer science / Traveling salesman problem (TSP) / Computation: Python, Nearest neighbor heuristic (NN)
TODO Search: Use Boolean vector instead of copying
A greedy algorithm that always travels to the nearest city.
# Allocate memory.
x = np.empty(n, dtype=int)
# Start somewhere.
x[0] = random.randint(0, n - 1)
# Distance.
y = 0
# Visit all cities.
for i in range(1, n):
# Find the relevant distances.
here = x[i - 1]
distances_here = np.copy(d[here])
# Exclude the visited cities.
visited = x[:i]
distances_here[visited] = sys.maxsize # HACK No int NaN.
# Find the closes city.
there = np.argmin(distances_here)
# Travel there.
y += distances_here[there]
x[i] = there
# Return to the starting city.
here = x[-1]
y += d[here][x[0]]
None