Post Correspondence Problem (PCP): The Post Correspondence Problem is a well-known example of an undecidable problem in computer science. Given two lists of strings over some alphabet, the task is to determine whether there exists a sequence of indices such that the concatenation of the strings from the first list is identical to the concatenation of the strings from the second list, using the same sequence of indices. It has been proven that no general algorithm can solve the PCP for all possible inputs, thereby demonstrating its undecidability, similar to the Halting Problem.
def nearest_neighbor_tsp(distances, start=0):
n = len(distances)
visited = [False] * n
path = [start]
total_distance = 0
current = start
visited[current] = True
for _ in range(n - 1):
nearest = None
nearest_dist = float('inf')
for i in range(n):
if not visited[i] and distances[current][i] < nearest_dist:
nearest = i
nearest_dist = distances[current][i]
path.append(nearest)
total_distance += nearest_dist
visited[nearest] = True
current = nearest
total_distance += distances[current][start]
path.append(start)
return path, total_distance
distances = [
[0, 2, 9, 10],
[1, 0, 6, 4],
[15, 7, 0, 8],
[6, 3, 12, 0]
]
path, total_dist = nearest_neighbor_tsp(distances)
print("Path:", path)
print("Total Distance:", total_dist)
Path: [0, 1, 3, 2, 0]
Total Distance: 33
Example: Route Planning for Delivery Companies (like UPS, FedEx) Delivery companies use heuristics like the nearest neighbor or “left-turn avoidance” because finding the absolutely shortest route (solving the full Traveling Salesman Problem exactly) would take way too much time and computational power, especially with hundreds or thousands of stops. Instead, heuristic approaches quickly find “good enough” solutions that save time and fuel, even if they aren’t 100% perfect.