Given a matrix and route, function improves route using 2-opt heuristic: reverses segments, reduce total travel distance.

# Traveling Salesman Problem - 2-Opt Heuristic
# Description: Given a distance matrix and an initial route, this function improves the route using the 2-opt heuristic by reversing segments to reduce the total travel distance.

# Traveling Salesman Problem (TSP) - 2-Opt Heuristic Optimization
def calculate_route_distance(route, distance_matrix):
    """
    Calculate the total distance of a route, including return to the starting city.

    Args:
        route (list of int): Ordered list of city indices
        distance_matrix (list of list of float): Matrix of distances between cities

    Returns:
        float: Total route distance
    """
    total_distance = 0
    route_length = len(route)

    # Sum distances between consecutive cities
    for i in range(route_length - 1):
        total_distance += distance_matrix[route[i]][route[i + 1]]

    # Add distance from last city back to first city (complete the tour)
    total_distance += distance_matrix[route[-1]][route[0]]

    return total_distance

def tsp_2opt(initial_route, distance_matrix, max_iterations=100):
    """
    Optimize a TSP route using the 2-opt heuristic algorithm.

    The 2-opt algorithm improves a route by:
    1. Selecting two edges in the current route
    2. Removing these edges
    3. Reconnecting the route in a different way
    4. Keeping the change if it reduces total route distance

    Args:
        initial_route (list of int): Starting route of city indices
        distance_matrix (list of list of float): Distances between cities
        max_iterations (int, optional): Maximum number of optimization iterations

    Returns:
        tuple: (optimized_route, total_distance)

    Time Complexity: O(n^3), where n is the number of cities
    Space Complexity: O(n)
    """
    # Validate inputs
    if not initial_route or len(initial_route) < 3:
        return initial_route, calculate_route_distance(initial_route, distance_matrix)

    # Current best solution
    best_route = initial_route.copy()
    best_distance = calculate_route_distance(best_route, distance_matrix)

    # Track improvement flag
    improved = True
    iterations = 0

    # Continue until no improvement or max iterations reached
    while improved and iterations < max_iterations:
        improved = False

        # Try all possible 2-opt swaps
        for i in range(1, len(best_route) - 1):
            for j in range(i + 1, len(best_route)):
                # Create a new route by reversing the segment between i and j
                new_route = (
                    best_route[:i] +  # Cities before swap point
                    best_route[i:j+1][::-1] +  # Reversed segment
                    best_route[j+1:]  # Cities after swap point
                )

                # Calculate new route distance
                new_distance = calculate_route_distance(new_route, distance_matrix)

                # Update if improved
                if new_distance < best_distance:
                    best_route = new_route
                    best_distance = new_distance
                    improved = True
                    break

            # Exit outer loop if improvement found
            if improved:
                break

        iterations += 1

    return best_route, best_distance

# Demonstration function
def demonstrate_tsp_2opt():
    """
    Demonstrate the 2-opt TSP optimization with sample distance matrix.
    """
    # Example distance matrix (symmetric)
    distance_matrix = [
        [0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]
    ]

    # Initial route
    initial_route = [0, 1, 2, 3]

    print("Initial Route:")
    print(f"Route: {initial_route}")
    print(f"Distance: {calculate_route_distance(initial_route, distance_matrix)}")

    # Optimize route
    optimized_route, optimized_distance = tsp_2opt(initial_route, distance_matrix)

    print("\nOptimized Route:")
    print(f"Route: {optimized_route}")
    print(f"Distance: {optimized_distance}")