tsp greedy

#TSP greedy import math import random # Function to calculate Euclidean distance for cities with coordinates def calculate_distance_between_coordinates(city1, city2): return math.sqrt((city2[0] - city1[0])2 + (city2[1] - city1[1])2) # Function to calculate the distance from a distance matrix def calculate_distance_between_matrix(i, j, dist_matrix): return dist_matrix[i][j] def greedy_tsp(cities=None, dist_matrix=None, city_names=None, start_city=None, end_city=None): """ Solve TSP using a greedy approach while including city names in the result. Args: - cities (list): List of cities (x, y) coordinates for each city (only if using coordinates). - dist_matrix (list): Distance matrix (only if distances between cities are provided directly). - city_names (list): List of city names corresponding to the cities. - start_city (int): Optional starting city index. If None, the first city will be used. - end_city (int): Optional end city index. If None, the tour will return to the starting city. Returns: - tuple: The total distance of the tour and the path (list of city names). """ # Use appropriate distance calculation method if cities is not None: calculate_distance = calculate_distance_between_coordinates else: calculate_distance = calculate_distance_between_matrix # Initialize start and end cities if start_city is None: start_city = 0 # Default to the first city if end_city is None: end_city = start_city # Default to returning to the start city # Initialize unvisited cities and the tour unvisited = list(range(len(cities))) if cities is not None else list(range(len(dist_matrix))) path = [unvisited.pop(start_city)] # Start with the start city total_distance = 0 while unvisited: last_city = path[-1] next_city = min(unvisited, key=lambda city: calculate_distance(last_city, city, dist_matrix) if cities is None else calculate_distance(cities[last_city], cities[city])) unvisited.remove(next_city) path.append(next_city) total_distance += calculate_distance(last_city, next_city, dist_matrix) if cities is None else calculate_distance(cities[last_city], cities[next_city]) # Close the tour by returning to the starting city total_distance += calculate_distance(path[-1], path[0], dist_matrix) if cities is None else calculate_distance(cities[path[-1]], cities[path[0]]) path.append(path[0]) # Add the starting city at the end to complete the tour # Return the total distance and path with city names city_path = [city_names[city] for city in path] return total_distance, city_path # Example usage for Greedy TSP with City Names: # City names city_names = ["City A", "City B", "City C", "City D"] # Example distance matrix (distances between cities) dist_matrix = [ [0, 2, 4, 1], [2, 0, 3, 5], [4, 3, 0, 6], [1, 5, 6, 0] ] # Run the TSP with greedy approach total_distance, path = greedy_tsp(dist_matrix=dist_matrix, city_names=city_names) print("Total Distance:", total_distance) print("Path:", " -> ".join(path))

Mar 23, 2025 - 13:21

#TSP greedy


import math
import random

# Function to calculate Euclidean distance for cities with coordinates
def calculate_distance_between_coordinates(city1, city2):
    return math.sqrt((city2[0] - city1[0])**2 + (city2[1] - city1[1])**2)

# Function to calculate the distance from a distance matrix
def calculate_distance_between_matrix(i, j, dist_matrix):
    return dist_matrix[i][j]

def greedy_tsp(cities=None, dist_matrix=None, city_names=None, start_city=None, end_city=None):
    """
    Solve TSP using a greedy approach while including city names in the result.

    Args:
    - cities (list): List of cities (x, y) coordinates for each city (only if using coordinates).
    - dist_matrix (list): Distance matrix (only if distances between cities are provided directly).
    - city_names (list): List of city names corresponding to the cities.
    - start_city (int): Optional starting city index. If None, the first city will be used.
    - end_city (int): Optional end city index. If None, the tour will return to the starting city.

    Returns:
    - tuple: The total distance of the tour and the path (list of city names).
    """
    # Use appropriate distance calculation method
    if cities is not None:
        calculate_distance = calculate_distance_between_coordinates
    else:
        calculate_distance = calculate_distance_between_matrix

    # Initialize start and end cities
    if start_city is None:
        start_city = 0  # Default to the first city
    if end_city is None:
        end_city = start_city  # Default to returning to the start city

    # Initialize unvisited cities and the tour
    unvisited = list(range(len(cities))) if cities is not None else list(range(len(dist_matrix)))
    path = [unvisited.pop(start_city)]  # Start with the start city
    total_distance = 0

    while unvisited:
        last_city = path[-1]
        next_city = min(unvisited, key=lambda city: calculate_distance(last_city, city, dist_matrix) if cities is None else calculate_distance(cities[last_city], cities[city]))
        unvisited.remove(next_city)
        path.append(next_city)
        total_distance += calculate_distance(last_city, next_city, dist_matrix) if cities is None else calculate_distance(cities[last_city], cities[next_city])

    # Close the tour by returning to the starting city
    total_distance += calculate_distance(path[-1], path[0], dist_matrix) if cities is None else calculate_distance(cities[path[-1]], cities[path[0]])
    path.append(path[0])  # Add the starting city at the end to complete the tour

    # Return the total distance and path with city names
    city_path = [city_names[city] for city in path]
    return total_distance, city_path

# Example usage for Greedy TSP with City Names:

# City names
city_names = ["City A", "City B", "City C", "City D"]

# Example distance matrix (distances between cities)
dist_matrix = [
    [0, 2, 4, 1],
    [2, 0, 3, 5],
    [4, 3, 0, 6],
    [1, 5, 6, 0]
]

# Run the TSP with greedy approach
total_distance, path = greedy_tsp(dist_matrix=dist_matrix, city_names=city_names)
print("Total Distance:", total_distance)
print("Path:", " -> ".join(path))