import math

def distance(p1, p2):
    return math.hypot(p1[0] - p2[0], p1[1] - p2[1])

def nearest_neighbor_tsp(cities):
    n = len(cities)
    visited = [False] * n
    path = [0]  # start at the first city
    visited[0] = True
    total_distance = 0

    for _ in range(n - 1):
        last = path[-1]
        nearest = None
        nearest_dist = float('inf')
        for i in range(n):
            if not visited[i]:
                d = distance(cities[last], cities[i])
                if d < nearest_dist:
                    nearest = i
                    nearest_dist = d
        path.append(nearest)
        visited[nearest] = True
        total_distance += nearest_dist

    # Return to start
    total_distance += distance(cities[path[-1]], cities[0])
    path.append(0)
    
    return path, total_distance

# Example usage:
cities = [(0, 0), (1, 3), (4, 3), (6, 1)]
path, dist = nearest_neighbor_tsp(cities)
print("Path:", path)
print("Total distance:", dist)


Path: [0, 1, 2, 3, 0]
Total distance: 15.073467315212788

  1. Another Undecidable Problem One example of another undecidable problem that I researched is the Post Correspondence Problem. If you have two lists of word pieces, and you’re trying to arrange them using the same order of pieces from each list so that they make the exact same word. There no general way (no algorithm) that can always figure out if that’s possible. Some cases are just too tricky, and no computer can solve every possible version of this, so it’s undecidable.

  2. Real-World Example of Heuristics A good example of using a heuristic is Google Maps. When you ask it for the fastest way to get somewhere, it doesn’t try every single possible route—that would take forever. Instead, it uses shortcuts and smart guesses based on things like traffic, distance, and speed limits to find a good route quickly. An exact solution would take way too long, especially in big cities with thousands of roads.