Untitled

import random

# Define the distance matrix (example distances between cities)
distance_matrix = {
    'A': {'A': 0, 'B': 5, 'C': 8, 'D': 4, 'E': 6},
    'B': {'A': 5, 'B': 0, 'C': 2, 'D': 7, 'E': 9},
    'C': {'A': 8, 'B': 2, 'C': 0, 'D': 3, 'E': 1},
    'D': {'A': 4, 'B': 7, 'C': 3, 'D': 0, 'E': 5},
    'E': {'A': 6, 'B': 9, 'C': 1, 'D': 5, 'E': 0}
}

# Calculate the total distance of a route
def calculate_total_distance(route):
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += distance_matrix[route[i]][route[i+1]]
    total_distance += distance_matrix[route[-1]][route[0]]  # Return to the starting city
    return total_distance

# Generate a neighboring solution by swapping two cities
def generate_neighbor(route):
    index1, index2 = random.sample(range(1, len(route)), 2)  # Exclude the starting city from swapping
    new_route = route[:]
    new_route[index1], new_route[index2] = new_route[index2], new_route[index1]  # Swap cities
    return new_route

# Hill Climbing algorithm
def hill_climbing(start_city, max_iterations):
    cities = [city for city in distance_matrix if city != start_city]
    current_solution = [start_city] + random.sample(cities, len(cities))
    current_distance = calculate_total_distance(current_solution)
    
    for _ in range(max_iterations):
        neighbor = generate_neighbor(current_solution)
        neighbor_distance = calculate_total_distance(neighbor)
        
        if neighbor_distance < current_distance:  # Minimization
            current_solution = neighbor
            current_distance = neighbor_distance
            
    return current_solution, current_distance

# Visualize the optimal route
def visualize_route(route):
    print("\nOptimal Route:")
    for i in range(len(route) - 1):
        print(route[i], "->", end=" ")
    print(route[-1], "->", route[0])  # Return to the starting city

# Main loop
while True:
    start_city = input("\nEnter the starting city (A, B, C, D, or E), or type 'exit' to quit: ").upper()
    if start_city == 'EXIT':
        break
    elif start_city not in distance_matrix:
        print("Invalid starting city. Please choose from A, B, C, D, or E.")
    else:
        max_iterations = 1000
        solution, distance = hill_climbing(start_city, max_iterations)
        visualize_route(solution)
        print("Total Distance:", distance)