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 math

class TSP:
	"""
	TSP（Travelling Salesman Problem）
	旅行商问题的类
	"""
	def __init__(self, points):
		"""
		points包含了所有旅行城市的位置坐标，起点默认是（0，0）
		points例如: [(1,2), (3,2)]
		"""
		# 加入起点
		self.points = [(0, 0)] + points
		self.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.5


	def 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 map

	def router_distance(self, router):
		"""
		计算路径的总距离
		router: [(0, 0), (x1, x2), (x2, y2), (x3, y3)]
		最后还要回到(0, 0)
		"""
		router = router + [(0, 0)]
		ret = 0
		for i in range(1, len(router)):
			ret += self.distance(router[i-1], router[i])
		return ret


class 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:
				continue
			if row[i] < min_:
				min_ = row[i]
				index = i
		return index

	def greed(self):
		"""
		从起点(0, 0)出发，选择最近的点；
		再从该点出发，选择最近的点；
		重复执行该步骤，直到没有点时返回起点。

		返回路径
		例如： [(0, 0), (3, 4), (0, 0)]
		"""
		curr = 0
		router = [self.points[0]]
		arrived = set()
		arrived.add(0)
		total_distance = 0
		while True:
			curr = self.nearest(self.map[curr], arrived)
			if curr is None:
				break
			router.append(self.points[curr])
			arrived.add(curr)
		# print(arrived, router)
		print("greed 总距离:", self.router_distance(router))
		return router


class ClimbSolution(TSP):
	"""
	爬山算法解决TSP问题:
	"""
	def __init__(self, points):
		super().__init__(points)


	def climb(self):
		"""
		爬山算法，查找局部最优解
		查找过程参考：
		交换任意两个节点的顺序, 找到局部最优解
		"""
		router = self.points
		distance = self.router_distance(router)

		turn = 1000
		while 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_distance
				router = temp
			turn -= 1
		print("climb总距离：", distance)
		return router



class 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.points
		distance = self.router_distance(router)

		a = 0.99  # 降温系数
		turn = 1000
		e = math.e
		for _ 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_distance
				router = temp
			# 更新降温系数
			a = a * a
		print("sa总距离：", distance)
		return router

points = [(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())