# Untitled

unknown

python

2 months ago

2.4 kB

2

Indexable

Never

^{}

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)

Leave a Comment