Python Program

import itertools

def calculate_distance(city1, city2):
    """
    Calculate the distance between two cities.
    
    Parameters:
    city1 (tuple): Coordinates of the first city (x1, y1).
    city2 (tuple): Coordinates of the second city (x2, y2).

    Returns:
    float: The distance between the two cities.
    """
    return ((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2) ** 0.5

def total_distance(route, cities):
    """
    Calculate the total distance of the given route.

    Parameters:
    route (list): A list of city indices representing the route.
    cities (list): A list of city coordinates.

    Returns:
    float: The total distance of the route.
    """
    return sum(calculate_distance(cities[route[i]], cities[route[i + 1]]) for i in range(len(route) - 1))

def traveling_salesman(cities):
    """
    Solve the Traveling Salesman Problem using a brute-force approach.
    
    Parameters:
    cities (list): A list of tuples representing city coordinates.

    Returns:
    tuple: The optimal route and its total distance.
    """
    num_cities = len(cities)
    all_routes = itertools.permutations(range(num_cities))
    
    best_route = None
    min_distance = float('inf')
    
    for route in all_routes:
        current_distance = total_distance(route + (route[0],), cities)
        if current_distance < min_distance:
            min_distance = current_distance
            best_route = route
            
    return best_route, min_distance

# Example usage
if __name__ == "__main__":
    cities = [(0, 0), (1, 2), (2, 4), (3, 1)]
    best_route, min_distance = traveling_salesman(cities)
    print(f"Best route: {best_route} with distance: {min_distance}")

Program Structure Explanation

The program is structured into several key functions:

• calculate_distance(city1, city2): This function computes the Euclidean distance between two cities given their coordinates.
• total_distance(route, cities): This function calculates the total distance of a specified route through the cities.
• traveling_salesman(cities): This is the main function that generates all possible routes using permutations and finds the one with the minimum distance.
• if __name__ == “__main__”: This block allows the script to be run directly, providing an example usage of the program.

Usage

To use the program, define a list of city coordinates as tuples and call the traveling_salesman function with that list. The output will include the best route found and the corresponding distance.