Traveling Salesman Problem - Nearest Neighbour

nearest_neighbour.py

class TSPSolver:
    """Base class for TSP solvers."""

    def __init__(self, problem) -> None:
        """
        Initialize the TSP solver.

        Args:
            problem: tsplib95 problem instance
        """
        self.problem = problem
        self.n: int = problem.dimension
        self.nodes: List[int] = list(problem.get_nodes())

    def get_distance(self, node1: int, node2: int) -> float:
        """Get distance between two nodes using the problem's weight function."""
        return self.problem.get_weight(node1, node2)

    def calculate_tour_distance(self, tour: List[int]) -> float:
        """Calculate the total distance of a tour."""
        total_distance: float = 0.0
        for i in range(len(tour)):
            from_node = tour[i]
            to_node = tour[(i + 1) % len(tour)]
            total_distance += self.get_distance(from_node, to_node)
        return total_distance

    def verify_tour(self, tour: List[int]) -> bool:
        """Verify that a tour is valid (visits each city exactly once)."""
        if len(tour) != self.n:
            return False
        return set(tour) == set(self.nodes)

class NearestNeighbor(TSPSolver):
    """
    Nearest Neighbor Algorithm for TSP.

    Time Complexity: O(n²)
    Space Complexity: O(n)

    This is a greedy heuristic that builds a tour by always choosing
    the nearest unvisited city as the next destination.
    """

    def solve(self, start_node: Optional[int] = None) -> Tuple[List[int], float]:
        """
        Construct a tour using the Nearest Neighbor heuristic.

        Args:
            start_node: Starting node for the tour (default: first node)

        Returns:
            Tuple of (tour, distance)
        """
        if start_node is None:
            start_node = self.nodes[0]

        if start_node not in self.nodes:
            raise ValueError(f"Invalid start node: {start_node}")

        # Initialize tour with start node
        tour = [start_node]
        unvisited = set(self.nodes)
        unvisited.remove(start_node)
        current = start_node

        # Greedily build the tour
        while unvisited:
            # Find the nearest unvisited node
            nearest_node = min(
                unvisited, key=lambda node: self.get_distance(current, node)
            )

            tour.append(nearest_node)
            unvisited.remove(nearest_node)
            current = nearest_node

        distance = self.calculate_tour_distance(tour)
        return tour, distance