基于生成器替代嵌套循环的TSP问题2-opt算法实现需求

Alright, let's work through adapting the 2-opt algorithm for your Traveling Salesman Problem setup with that custom road_map input. I’ve put together a tailored solution that handles your data format and optimizes the route effectively:

The 2-opt algorithm works by iteratively swapping pairs of edges in the route to eliminate "crossings" that add unnecessary distance. For your use case, we’ll:

• First process your mixed-type (string/float) geographic coordinates
• Calculate accurate real-world distances using the Haversine formula (better than Euclidean distance for lat/long)
• Iteratively refine the route until no more distance reductions are possible

import math

def haversine_distance(lat1, lon1, lat2, lon2):
    """Calculate spherical distance between two geographic points (in kilometers)"""
    EARTH_RADIUS = 6371.0  # Average radius of Earth in km
    # Convert degrees to radians
    lat1_rad = math.radians(lat1)
    lon1_rad = math.radians(lon1)
    lat2_rad = math.radians(lat2)
    lon2_rad = math.radians(lon2)

    # Haversine formula calculations
    delta_lat = lat2_rad - lat1_rad
    delta_lon = lon2_rad - lon1_rad
    a = math.sin(delta_lat / 2)**2 + math.cos(lat1_rad) * math.cos(lat2_rad) * math.sin(delta_lon / 2)**2
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))

    return EARTH_RADIUS * c

def calculate_total_route_distance(route):
    """Compute total distance of a given TSP route"""
    total_distance = 0.0
    num_points = len(route)
    for i in range(num_points):
        # Get current point and next point (wrap back to start at end)
        current_point = route[i]
        next_point = route[(i + 1) % num_points]
        # Convert coordinates to float (handles string inputs)
        lat1 = float(current_point[2])
        lon1 = float(current_point[3])
        lat2 = float(next_point[2])
        lon2 = float(next_point[3])
        total_distance += haversine_distance(lat1, lon1, lat2, lon2)
    return total_distance

def two_opt_tsp_optimizer(road_map):
    """
    Optimize TSP route using 2-opt algorithm
    Args:
        road_map: List of tuples, each formatted as (Region, City, Latitude, Longitude)
    Returns:
        Tuple of (optimized_route, optimized_total_distance)
    """
    num_points = len(road_map)
    # Edge case: no optimization needed for 2 or fewer points
    if num_points <= 2:
        return road_map, calculate_total_route_distance(road_map)
    
    # Initialize with input route as starting point
    best_route = road_map.copy()
    best_distance = calculate_total_route_distance(best_route)
    improvement_found = True

    while improvement_found:
        improvement_found = False
        for i in range(1, num_points - 1):
            for j in range(i + 1, num_points):
                if j - i == 1:
                    continue  # Skip adjacent points (swap does nothing)
                # Generate new route by reversing the segment between i and j
                new_route = best_route[:i] + best_route[i:j+1][::-1] + best_route[j+1:]
                new_distance = calculate_total_route_distance(new_route)
                # Update best route if new distance is shorter
                if new_distance < best_distance:
                    best_route = new_route
                    best_distance = new_distance
                    improvement_found = True
                    break  # Restart loop after finding improvement to speed up convergence
            if improvement_found:
                break

    return best_route, best_distance

Test the code with your sample input (expanded to show meaningful optimization):

# Sample input road map (mixed string/float coordinates)
sample_road_map = [
    ('South England', 'London', '32.361538', '-86.279118'),
    ('Yorkshire', 'Manchester', 35.6656, '-86.4543'),
    ('Scotland', 'Edinburgh', '33.520661', '-86.802490'),
    ('Wales', 'Cardiff', 34.020730, '-86.134951')
]

# Run optimization
optimized_route, optimized_distance = two_opt_tsp_optimizer(sample_road_map)

# Print results
print("Optimized Route:")
for idx, location in enumerate(optimized_route):
    print(f"{idx+1}. {location[0]} - {location[1]}")
print(f"\nTotal Distance: {optimized_distance:.2f} km")

• Coordinate Type Handling: The code automatically converts string-formatted latitudes/longitudes to floats, so you don’t have to pre-process your input.
• Geographic Accuracy: Uses the Haversine formula instead of Euclidean distance to calculate real-world travel distances between points.
• Efficiency: Restarts the iteration loop immediately after finding an improvement, reducing unnecessary computations.

内容的提问来源于stack exchange，提问作者maracuja