Skip to content

Instantly share code, notes, and snippets.

@45deg
Last active April 20, 2024 15:58
Show Gist options
  • Save 45deg/19a8ad0d1007f35903048b30d2370132 to your computer and use it in GitHub Desktop.
Save 45deg/19a8ad0d1007f35903048b30d2370132 to your computer and use it in GitHub Desktop.
Traveling Salesman Problem (TSP) using the 2-opt algorithm (Japan's prefectoral capital) 都道府県庁所在地の巡回セールスマン
import random
import matplotlib.animation as animation
import matplotlib.pyplot as plt
capitals = {
'Hokkaido': (43.0646, 141.3468),
'Aomori': (40.8246, 140.7406),
'Iwate': (39.7036, 141.1527),
'Miyagi': (38.2688, 140.8721),
'Akita': (39.7186, 140.1023),
'Yamagata': (38.2404, 140.3636),
'Fukushima': (37.7499, 140.4675),
'Ibaraki': (36.3418, 140.4468),
'Tochigi': (36.5658, 139.8836),
'Gunma': (36.3912, 139.0609),
'Saitama': (35.8617, 139.6455),
'Chiba': (35.6047, 140.1233),
'Tokyo': (35.6895, 139.6917),
'Kanagawa': (35.4478, 139.6425),
'Niigata': (37.9161, 139.0364),
'Toyama': (36.6953, 137.2137),
'Ishikawa': (36.5947, 136.6256),
'Fukui': (36.0652, 136.2214),
'Yamanashi': (35.6642, 138.5689),
'Nagano': (36.2384, 138.5400),
'Gifu': (35.4233, 136.7606),
'Shizuoka': (34.9769, 138.3831),
'Aichi': (35.1802, 136.9066),
'Mie': (34.7303, 136.5086),
'Shiga': (35.0044, 135.8683),
'Kyoto': (35.0116, 135.7681),
'Osaka': (34.6937, 135.5023),
'Hyogo': (34.6913, 135.1830),
'Nara': (34.6851, 135.8048),
'Wakayama': (34.2260, 135.1675),
'Tottori': (35.5031, 134.2372),
'Shimane': (35.4723, 133.0505),
'Okayama': (34.6551, 133.9190),
'Hiroshima': (34.3853, 132.4553),
'Yamaguchi': (34.1785, 131.4738),
'Tokushima': (34.0704, 134.5547),
'Kagawa': (34.3401, 134.0438),
'Ehime': (33.8416, 132.7656),
'Kochi': (33.5597, 133.5311),
'Fukuoka': (33.5903, 130.4017),
'Saga': (33.2494, 130.2988),
'Nagasaki': (32.7503, 129.8779),
'Kumamoto': (32.8032, 130.7079),
'Oita': (33.2382, 131.6126),
'Miyazaki': (31.9111, 131.4239),
'Kagoshima': (31.5968, 130.5579),
'Okinawa': (26.2124, 127.6809)
}
def tsp(cities: list[tuple[float, float]]) -> tuple[list[int], float]:
"""
Solve the Traveling Salesman Problem (TSP) using the 2-opt algorithm.
Args:
cities: A list of tuples representing the (x, y) coordinates of each city.
Returns:
A tuple containing the optimal path that visits all cities exactly once, represented as a list of city indices,
and the length of the optimal path.
"""
n = len(cities)
path = list(range(n))
random.shuffle(path) # Initialize path randomly
def get_path_length(path: list[int]) -> float:
"""Calculate the length of a given path."""
return sum(distance(cities[path[i]], cities[path[i+1]]) for i in range(-1, n-1))
def distance(city1: tuple[float, float], city2: tuple[float, float]) -> float:
"""Calculate the Euclidean distance between two cities."""
return ((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2) ** 0.5
# Iterate until no further improvements can be made
improvement = True
path_history = [path]
while improvement:
improvement = False
for i in range(n - 1):
for j in range(i + 1, n):
# Reverse the path between city i and j and check if the resulting path is shorter
new_path = path[:i] + path[i:j+1][::-1] + path[j+1:]
new_length = get_path_length(new_path)
if new_length < get_path_length(path):
path = new_path
path_history.append(new_path)
improvement = True
break
if improvement:
break
return path_history, get_path_length(path)
def plot_tsp_path(cities: list[tuple[float, float]], list_path: list[list[int]], capitals: dict[str, tuple[float, float]]) -> None:
"""
Plot the cities in USA and the path generated by the TSP solver using Matplotlib.
Args:
cities: A list of tuples representing the (latitude, longitude) coordinates of each city.
list_path: A list of lists of city indices representing the optimal paths to be rendered one by one.
capitals: A dictionary mapping state codes to the (latitude, longitude) coordinates of their respective capital cities.
"""
fig, ax = plt.subplots()
# Extract the latitude and longitude coordinates of each city
latitudes = [city[0] for city in cities]
longitudes = [city[1] for city in cities]
def animate(i):
path = list_path[i]
ax.clear()
# Create a scatter plot of the cities and add labels for each city using the corresponding state capital
for j in range(len(cities)):
x, y = longitudes[j], latitudes[j]
label = list(capitals.keys())[list(capitals.values()).index((y, x))]
ax.scatter(x, y, label=label)
# Add a label for the city using the corresponding state capital
ax.annotate(
label, # Text of the label
xy=(x, y), # Position of the city dot
xytext=(x + 0.2, y + 0.2), # Position of the label relative to the city dot
fontsize=8, # Font size of the label
color='black', # Color of the label
ha='left', # Horizontal alignment of the label
va='center' # Vertical alignment of the label
)
# Plot the optimal path as a red line
for j in range(len(path) - 1):
start = path[j]
end = path[j + 1]
x_start, y_start = longitudes[start], latitudes[start]
x_end, y_end = longitudes[end], latitudes[end]
ax.plot([x_start, x_end], [y_start, y_end], color='red')
# Plot the final edge connecting the last and first cities
x_start, y_start = longitudes[path[-1]], latitudes[path[-1]]
x_end, y_end = longitudes[path[0]], latitudes[path[0]]
ax.plot([x_start, x_end], [y_start, y_end], color='red')
# Set the x and y limits of the plot to encompass all cities with same scale
max_range = max(max(longitudes) - min(longitudes), max(latitudes) - min(latitudes))
ax.set_xlim(min(longitudes) - 0.1 * max_range, max(longitudes) + 0.1 * max_range)
ax.set_ylim(min(latitudes) - 0.1 * max_range, max(latitudes) + 0.1 * max_range)
# Add axis labels and legend
ax.set_xlabel('Longitude')
ax.set_ylabel('Latitude')
# Create an animation using the `animate` function and save it as a GIF
ani = animation.FuncAnimation(fig, animate, frames=len(list_path), interval=50, repeat=True)
ani.save('tsp.gif')
# Example usage
cities = list(capitals.values())
path_history, length = tsp(cities)
print("Optimal path:", path_history[-1])
print("Optimal length:", length)
plot_tsp_path(cities, path_history, capitals)
@45deg
Copy link
Author

45deg commented Apr 20, 2024

tsp

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment