scipy.optimize
函数并不是为旅行商问题(TSP)提供直接适应的构造。为了简单解决方案,我建议使用2-opt算法,这是一个解决TSP的广受认可的算法,相对容易实现。以下是我的算法实现:
import numpy as np
path_distance = lambda r,c: np.sum([np.linalg.norm(c[r[p]]-c[r[p-1]]) for p in range(len(r))])
two_opt_swap = lambda r,i,k: np.concatenate((r[0:i],r[k:-len(r)+i-1:-1],r[k+1:len(r)]))
def two_opt(cities,improvement_threshold):
route = np.arange(cities.shape[0])
improvement_factor = 1
best_distance = path_distance(route,cities)
while improvement_factor > improvement_threshold:
distance_to_beat = best_distance
for swap_first in range(1,len(route)-2):
for swap_last in range(swap_first+1,len(route)):
new_route = two_opt_swap(route,swap_first,swap_last)
new_distance = path_distance(new_route,cities)
if new_distance < best_distance:
route = new_route
best_distance = new_distance
improvement_factor = 1 - best_distance/distance_to_beat
return route
以下是该函数的使用示例:
# Create a matrix of cities, with each row being a location in 2-space (function works in n-dimensions).
cities = np.random.RandomState(42).rand(70,2)
# Find a good route with 2-opt ("route" gives the order in which to travel to each city by row number.)
route = two_opt(cities,0.001)
这里是近似解路径在图上的显示:
import matplotlib.pyplot as plt
new_cities_order = np.concatenate((np.array([cities[route[i]] for i in range(len(route))]),np.array([cities[0]])))
plt.scatter(cities[:,0],cities[:,1])
plt.plot(new_cities_order[:,0],new_cities_order[:,1])
plt.show()
print("Route: " + str(route) + "\n\nDistance: " + str(path_distance(route,cities)))
![2-opt旅行商问题近似解决方案](https://istack.dev59.com/thFz1.webp)
如果算法速度对你很重要,我建议预先计算距离并将它们存储在矩阵中。这将大大缩短收敛时间。
编辑:自定义起始和结束点
对于非圆形路径(以不同于起点的位置结束的路径),请编辑路径距离公式为
path_distance = lambda r,c: np.sum([np.linalg.norm(c[r[p+1]]-c[r[p]]) for p in range(len(r)-1)])
然后使用xx重新排列城市以进行绘图
new_cities_order = np.array([cities[route[i]] for i in range(len(route))])
代码中,起始城市被固定为cities
中的第一个城市,而结束城市是可变的。
为了使结束城市成为cities
中的最后一个城市,在two_opt()
函数中改变swap_first
和swap_last
的范围限制交换城市的范围即可:
for swap_first in range(1,len(route)-3):
for swap_last in range(swap_first+1,len(route)-1):
为了使起始和结束城市都可变,请扩展
swap_first
和
swap_last
的范围。
for swap_first in range(0,len(route)-2):
for swap_last in range(swap_first+1,len(route)):