Untitled
unknown
python
2 years ago
1.2 kB
6
Indexable
import math def distance(city1, city2): # Calculate Euclidean distance between two cities return math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2) def nearest_neighbor(cities): # Start from the first city in the list current_city = cities[0] path = [current_city] total_distance = 0 unvisited_cities = set(cities[1:]) while unvisited_cities: # Find the nearest unvisited city next_city = min(unvisited_cities, key=lambda city: distance(current_city, city)) # Update the total distance and path total_distance += distance(current_city, next_city) current_city = next_city path.append(current_city) unvisited_cities.remove(next_city) # Return to the starting city total_distance += distance(path[-1], path[0]) path.append(path[0]) return path, total_distance # Example usage: # Define a list of cities as (x, y) coordinates cities = [(0, 0), (1, 5), (2, 3), (5, 1), (6, 6), (8, 3)] # Find the path and total distance using the nearest neighbor heuristic path, total_distance = nearest_neighbor(cities) print("Path:", path) print("Total distance:", total_distance)
Editor is loading...
Leave a Comment