Skip to content

Instantly share code, notes, and snippets.

@45deg
Last active April 4, 2023 20:01
Show Gist options
  • Save 45deg/1448c97f333d70b95567de834f100aee to your computer and use it in GitHub Desktop.
Save 45deg/1448c97f333d70b95567de834f100aee to your computer and use it in GitHub Desktop.
2-opt tsp
import random
import matplotlib.animation as animation
import matplotlib.pyplot as plt
capitals = {
'AL': (32.3777, -86.3006), # Montgomery, Alabama
'AK': (58.3019, -134.4197), # Juneau, Alaska
'AZ': (33.4484, -112.0740), # Phoenix, Arizona
'AR': (34.7465, -92.2896), # Little Rock, Arkansas
'CA': (38.5767, -121.4934), # Sacramento, California
'CO': (39.7392, -104.9903), # Denver, Colorado
'CT': (41.7670, -72.6770), # Hartford, Connecticut
'DE': (39.1619, -75.5267), # Dover, Delaware
'FL': (30.4383, -84.2807), # Tallahassee, Florida
'GA': (33.7490, -84.3880), # Atlanta, Georgia
'HI': (21.3074, -157.8574), # Honolulu, Hawaii
'ID': (43.6166, -116.2008), # Boise, Idaho
'IL': (39.7984, -89.6548), # Springfield, Illinois
'IN': (39.7684, -86.1581), # Indianapolis, Indiana
'IA': (41.6005, -93.6091), # Des Moines, Iowa
'KS': (39.0481, -95.6778), # Topeka, Kansas
'KY': (38.1867, -84.8753), # Frankfort, Kentucky
'LA': (30.4583, -91.1403), # Baton Rouge, Louisiana
'ME': (44.3078, -69.7824), # Augusta, Maine
'MD': (38.9786, -76.4911), # Annapolis, Maryland
'MA': (42.3582, -71.0637), # Boston, Massachusetts
'MI': (42.7336, -84.5555), # Lansing, Michigan
'MN': (44.9551, -93.1022), # Saint Paul, Minnesota
'MS': (32.2988, -90.1848), # Jackson, Mississippi
'MO': (38.5767, -92.1735), # Jefferson City, Missouri
'MT': (46.5958, -112.0270), # Helena, Montana
'NE': (40.8090, -96.6789), # Lincoln, Nebraska
'NV': (39.1608, -119.7539), # Carson City, Nevada
'NH': (43.2067, -71.5381), # Concord, New Hampshire
'NJ': (40.2206, -74.7597), # Trenton, New Jersey
'NM': (35.6672, -105.9644), # Santa Fe, New Mexico
'NY': (42.6526, -73.756), # Albany, New York
'NC': (35.7804, -78.6391), # Raleigh, North Carolina
'ND': (46.8083, -100.7837), # Bismarck, North Dakota
'OH': (39.9612, -82.9988), # Columbus, Ohio
'OK': (35.4822, -97.5350), # Oklahoma City, Oklahoma
'OR': (44.9429, -123.0351), # Salem, Oregon
'PA': (40.2697, -76.8756), # Harrisburg, Pennsylvania
'RI': (41.8230, -71.4189), # Providence, Rhode Island
'SC': (34.0007, -81.0348), # Columbia, South Carolina
'SD': (44.3680, -100.3364), # Pierre, South Dakota
'TN': (36.1627, -86.7816), # Nashville, Tennessee
'TX': (30.2672, -97.7431), # Austin, Texas
'UT': (40.7608, -111.8910), # Salt Lake City, Utah
'VT': (44.2601, -72.5754), # Montpelier, Vermont
'VA': (37.5407, -77.4360), # Richmond, Virginia
'WA': (47.0425, -122.8931), # Olympia, Washington
'WV': (38.3498, -81.6326), # Charleston, West Virginia
'WI': (43.0747, -89.3843), # Madison, Wisconsin
'WY': (41.1456, -104.8020) # Cheyenne, Wyoming
}
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment