# 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]]

# 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=" ")

# 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)
```