我尝试优化我编写的一个简单的Python算法,该算法大致解决了旅行商问题:
import math
import random
import matplotlib.pyplot as plt
import datetime
#Distance between two point
def distance(point1, point2):
return math.sqrt((point2[0]-point1[0])**2+(point2[1]-point1[1])**2)
#TSP TimeTraveler Algorithm
def TSP_TimeTraveler(Set_Points):
print("Solving TSP")
#For calculating execution time
time_start = datetime.datetime.now()
#Copy the set points
points = Set_Points.copy()
route = []
#Take 3 points at random
route.append(points.pop(random.randint(0,len(points)-1)))
route.insert(0,points.pop(random.randint(0,len(points)-1)))
route.insert(1,points.pop(random.randint(0,len(points)-1)))
#Calulating the initial route length
Length = distance(route[0],route[1]) + distance(route[1],route[-1]) + distance(route[-1],route[0])
#Time Traveler Algorithm
while len(points)>0 :
print("Points left : ", len(points),' ', end="\r")
#Take a random point from the Set
point = points.pop(random.randint(0,len(points)-1))
###############################################################################################################
#### Finding the closest route segment by calculation all lengths posibilities and finding the minimum one ####
###############################################################################################################
Set_Lengths = []
for i in range(1,len(route)):
#Set of Lengths when the point is on each route segment except the last one
L = Length - distance(route[i-1],route[i]) + distance(route[i-1],point) + distance(point, route[i])
Set_Lengths.append((i,L))
#Adding the last length when the point is on the last segement
L = Length - distance(route[-1],route[0]) + distance(route[-1],point) + distance(point, route[0])
Set_Lengths.append((0,L))
###############################################################################################################
###############################################################################################################
#Sorting the set of lengths
Set_Lengths.sort(key=lambda k: k[1])
#Inserting the point on the minimum length segment
route.insert(Set_Lengths[0][0], point)
#Updating the new route length
Length = Set_Lengths[0][1]
#Connecting the start point with the finish point
route.append(route[0])
#For calculating execution time
time_end = datetime.datetime.now()
delta = (time_end-time_start).total_seconds()
print("Points left : ", len(points),' Done ',)
print("Execution time : ", delta, "secs")
return route
#######################
#Testing the Algorithm#
#######################
#Size of the set
size = 2520
#Generating a set of random 2D points
points = []
for i in range(size):
points.append([random.uniform(0, 100),random.uniform(0, 100)])
#Solve TSP
route = TSP_TimeTraveler(points)
#Plot the solution
plt.scatter(*zip(*points),s=5)
plt.plot(*zip(*route))
plt.axis('scaled')
plt.show()
该算法分为三个简单步骤:
1/ 首先,我从点集中随机选择3个点,并将它们连接成初始路径。
2/ 然后,每一步,我从剩余的点集中随机选择一个点,并尝试找到最接近已有路径的线段并将其连接。
3/ 我重复执行第2步,直到剩余点集为空为止。
这是算法解决120个点集的gif图:TimeTravelerAlgorithm.gif
我将其命名为“时间旅行者”,因为它的操作类似于贪心推销员算法。但不同的是,贪心推销员在现在前往最近的新城市,而贪心推销员则会回到过去,前往他已经访问过的最近城市,然后继续他的正常路线。
时间旅行者从3个城市开始路线,每一步都会在过去添加一个新城市,直到他访问完所有城市并返回家乡。
该算法可以快速地为小规模点集提供合理的解决方案。以下是在一台2.6GHz双核Intel Core i5处理器的Macbook上每组点的执行时间:- 大约0.03秒内完成120个点
- 大约0.23秒内完成360个点
- 大约10秒内完成2520个点
- 大约3分钟内完成10000个点
- 大约5小时内完成100000个点(解决方案地图)
我希望您能对其进行审查和帮助优化。我尝试解决可能极大的点集的近似解,而不产生交叉路径。
PS:我的算法和代码是开放的。互联网上的人们,请随意在任何项目或任何研究中使用它。
O(log h)
而不是O(h)
,其中h
是当前解决方案中的点数。可能是KD树或其他东西。还要实现2或3-opt以消除交叉。 - Nuclearman