TSP(旅行商问题) 贪心、爬山、退火算法的python解决方案

贪心、爬山、退火算法的python解决方案"/>

TSP(旅行商问题) 贪心、爬山、退火算法的python解决方案

TSP问题的python简单解决方案（贪婪、爬山、退火）

*该方案中使用直角坐标系来表示各个城市的位置，其中起点为（0，0）

TSP类中计算了map,是所有点到点之间的距离数组

	例如起点 点1 点2[起点[0,  2,  3],点1 [1,  0,  2],点2 [3,  2,  0]]如其中的map[1][0] = 1 就表示点1到起点的距离为1

• 贪心算法：从起点(0, 0)出发，选择最近的点；再从该点出发，选择最近的点；重复执行该步骤，直到没有点时返回起点。
• 爬山算法：查找局部最优解，从起点(0, 0)出发，交换任意两个节点的顺序, 如果比当前的解优秀则采纳，重复n次（n由用户设置）找到局部最优解。
• 模拟退火算法：在爬山算法的基础上，可以接受比当前解不优秀一些的解。从起点(0, 0)出发，交换任意两个节点的顺序, 如果解<当前解* e ** a则采纳，【降温系数α<1，以Tn+1=αTn的形式下降，比如取α=0.99 ，e是math.e≈2.718281828459】，每轮的最后修改a = a * a (所以随着轮数的增多，e**a在变小越来越接近1，越来越像爬山算法)

代码使用面向对象的形式编写，有详尽的注释，可以说是目前全网最容易看懂的TSP解法了（比起一上来就大几百行c++甩一脸，一个注释都没有😂）

import random
import copy
import mathclass TSP:"""TSP（Travelling Salesman Problem）旅行商问题的类"""def __init__(self, points):"""points包含了所有旅行城市的位置坐标，起点默认是（0，0）points例如: [(1,2), (3,2)]"""# 加入起点self.points = [(0, 0)] + pointsself.length = len(self.points)self.map = self.distance_map()def distance(self, point1, point2):"""计算两点之间的距离point1: (x1, y1)point2: (x2, y2)"""return ((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2) ** 0.5def distance_map(self):"""计算所有点到点之间的距离数组例如起点 点1 点2[起点[0,  2,  3],点1 [1,  0,  2],点2 [3,  2,  0]]"""map = [[0 for _ in range(self.length)] for _ in range(self.length)]for row in range(self.length):for col in range(self.length):map[row][col] = self.distance(self.points[row], self.points[col])return mapdef router_distance(self, router):"""计算路径的总距离router: [(0, 0), (x1, x2), (x2, y2), (x3, y3)]最后还要回到(0, 0)"""router = router + [(0, 0)]ret = 0for i in range(1, len(router)):ret += self.distance(router[i-1], router[i])return retclass GreedSolution(TSP):"""贪心算法解决TSP问题:"""def __init__(self, points):super().__init__(points)def nearest(self, row, arrived):"""找到贪心算法在某个点上可以选择的最优的点的坐标row: 某个点对应与另外所有点的距离列表arrvied: 已经到达过的点的集合"""min_ = float('inf')index = None# print("arrived in nearest:", arrived)for i in range(len(row)):if i in arrived or row[i] == 0:continueif row[i] < min_:min_ = row[i]index = ireturn indexdef greed(self):"""从起点(0, 0)出发，选择最近的点；再从该点出发，选择最近的点；重复执行该步骤，直到没有点时返回起点。返回路径例如： [(0, 0), (3, 4), (0, 0)]"""curr = 0router = [self.points[0]]arrived = set()arrived.add(0)total_distance = 0while True:curr = self.nearest(self.map[curr], arrived)if curr is None:breakrouter.append(self.points[curr])arrived.add(curr)# print(arrived, router)print("greed 总距离:", self.router_distance(router))return routerclass ClimbSolution(TSP):"""爬山算法解决TSP问题:"""def __init__(self, points):super().__init__(points)def climb(self):"""爬山算法，查找局部最优解查找过程参考：交换任意两个节点的顺序, 找到局部最优解"""router = self.pointsdistance = self.router_distance(router)turn = 1000while turn:p1 = int(random.random() * self.length)p2 = int(random.random() * self.length)while p1 == p2:p2 = int(random.random() * self.length)temp = copy.deepcopy(router)temp[p1], temp[p2] = temp[p2], temp[p1]curr_distance = self.router_distance(temp)if curr_distance < distance:distance = curr_distancerouter = tempturn -= 1print("climb总距离：", distance)return routerclass SASolution(TSP):"""模拟退火算法解决TSP问题:SA（Simulated annealing)"""def __init__(self, points):super().__init__(points)def sa(self):"""模拟退火算法，查找全局最优解查找过程参考：交换任意两个节点的顺序, 找到局部最优解退火的方式：1.降温系数α<1，以Tn+1=αTn的形式下降，比如取α=0.99 (*目前采用)2.Tn=T0/(1+n)3.Tn=T0/log(1+n)"""router = self.pointsdistance = self.router_distance(router)a = 0.99  # 降温系数turn = 1000e = math.efor _ in range(turn):p1 = int(random.random() * self.length)p2 = int(random.random() * self.length)while p1 == p2:p2 = int(random.random() * self.length)temp = copy.deepcopy(router)temp[p1], temp[p2] = temp[p2], temp[p1]curr_distance = self.router_distance(temp)if curr_distance < distance * e ** a:distance = curr_distancerouter = temp# 更新降温系数a = a * aprint("sa总距离：", distance)return routerpoints = [(4, 3), (1, 2), (7, 8), (0.5, 0.9)]problem = ClimbSolution(points)
print(problem.climb())
problem = GreedSolution(points)
print(problem.greed())
problem = SASolution(points)
print(problem.sa())