9/25/24, 7:41 AM Untitled7.
ipynb - Colab
import random
def input_distance_matrix(num_cities):
# Create a distance matrix by taking user input
distance_matrix = []
print("Enter the distances between cities in the form of a matrix:")
for i in range(num_cities):
row = []
for j in range(num_cities):
if i == j:
row.append(0) # Distance to the same city is 0
else:
distance = int(input(f"Distance from city {i} to city {j}: "))
row.append(distance)
distance_matrix.append(row)
return distance_matrix
def total_distance(path, distance_matrix):
# Calculate the total distance traveled in the given path
total = 0
for i in range(len(path) - 1):
total += distance_matrix[path[i]][path[i+1]]
total += distance_matrix[path[-1]][path[0]] # Return to starting city
return total
def hill_climbing_tsp(num_cities, distance_matrix, max_iterations=10000):
current_path = list(range(num_cities)) # Initial solution, visiting cities in order
current_distance = total_distance(current_path, distance_matrix)
for _ in range(max_iterations):
# Generate a neighboring solution by swapping two random cities
neighbor_path = current_path.copy()
i, j = random.sample(range(num_cities), 2)
neighbor_path[i], neighbor_path[j] = neighbor_path[j], neighbor_path[i]
neighbor_distance = total_distance(neighbor_path, distance_matrix)
# If the neighbor solution is better, move to it
if neighbor_distance < current_distance:
current_path = neighbor_path
current_distance = neighbor_distance
return current_path
def main():
num_cities = int(input("Enter the number of cities: ")) # Number of cities in the TSP
distance_matrix = input_distance_matrix(num_cities) # Get the distance matrix from the user
print("Distance Matrix:")
for row in distance_matrix:
print(row)
print("\nHill Climbing TSP:\n")
solution = hill_climbing_tsp(num_cities, distance_matrix)
print("Optimal path:", solution)
print("Total distance:", total_distance(solution, distance_matrix))
if __name__ == "__main__":
main()
Enter the number of cities: 5
Enter the distances between cities in the form of a matrix:
Distance from city 0 to city 1: 10
Distance from city 0 to city 2: 20
Distance from city 0 to city 3: 15
Distance from city 0 to city 4: 5
Distance from city 1 to city 0: 10
Distance from city 1 to city 2: 13
Distance from city 1 to city 3: 8
Distance from city 1 to city 4: 15
Distance from city 2 to city 0: 20
Distance from city 2 to city 1: 13
Distance from city 2 to city 3: 14
Distance from city 2 to city 4: 30
Distance from city 3 to city 0: 15
Distance from city 3 to city 1: 8
Distance from city 3 to city 2: 14
https://colab.research.google.com/drive/1Be5a1sTsId2rz8qWaTjIpam1roMIK4eZ#scrollTo=8i2h72rOqrEy&printMode=true 1/2
9/25/24, 7:41 AM Untitled7.ipynb - Colab
Distance from city 3 to city 4: 12
Distance from city 4 to city 0: 5
Distance from city 4 to city 1: 15
Distance from city 4 to city 2: 30
Distance from city 4 to city 3: 12
Distance Matrix:
[0, 10, 20, 15, 5]
[10, 0, 13, 8, 15]
[20, 13, 0, 14, 30]
[15, 8, 14, 0, 12]
[5, 15, 30, 12, 0]
Hill Climbing TSP:
Optimal path: [0, 1, 2, 3, 4]
Total distance: 54
https://colab.research.google.com/drive/1Be5a1sTsId2rz8qWaTjIpam1roMIK4eZ#scrollTo=8i2h72rOqrEy&printMode=true 2/2
