旅行售货员问题（TSP）

2023-07-20

完成时间：大二上

问题描述

旅行售货员问题：即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

实现

class TSP:
    def __init__(self, matrix, names):

        matrix.append([0]*len(matrix))

        matrix.insert(0, [0]*len(matrix))

        for i in range(len(matrix)):

            matrix[i].insert(0, 0)

            matrix[i].append(0)

            self.matrix = matrix

            self.names = names

            self.num = len(names) # 城市个数

            self.temp_path = [i for i in range(0, self.num+1)] # 当前路径

            self.temp_len = 0 # 当前路径长度

            self.best_path = [0] * (self.num+1) # 最短路径

            self.best_len = 99999999 # 最短路径的长度

    def __backtrack(self, node):

        if node > self.num:

            v = self.matrix[self.temp_path[self.num]][1]

            if (v != 0) and (v + self.temp_len < self.best_len):

                self.best_len = v + self.temp_len

                for i in range(1, self.num + 1):

                    self.best_path[i] = self.temp_path[i]

        else:

            for i in range(node, self.num + 1):

                v = self.matrix[self.temp_path[node-1]][self.temp_path[i]]

                if (v != 0) and (v + self.temp_len < self.best_len):

                    self.temp_path[node], self.temp_path[i] = self.temp_path[i], self. temp_path[node]

                    self.temp_len += self.matrix[self.temp_path[node-1]][self.temp_path [node]]

                    self.__backtrack(node + 1)

                    self.temp_len -= self.matrix[self.temp_path[node-1]][self.temp_path [node]]

                    self.temp_path[node], self.temp_path[i] = self.temp_path[i], self. temp_path[node]

        return

    def solve(self):

        self.__backtrack(2)

        path_str = ""

        for i in range(1, self.num+1):

            path_str += self.names[self.best_path[i]]

            path_str += self.names[1]

        return path_str, self.best_len

if __name__ == '__main__':
    n = int(input("城市数量："))
    distance = []
# distance = [[0, 1231, 5582, 344, 8164, 9588],

# [8943, 0, 3363, 9212, 12335, 11319],

# [5582, 3363, 0, 5850, 1012, 10872],

# [344, 9212, 5850, 0, 8238, 5739],

# [8164, 12475, 11012, 7238, 0, 2103],

# [9588, 11319, 10872, 9739, 2103, 0]]

# 记录两个城市之间距离的邻接矩阵
    print("请输入城市之间的邻接矩阵")
    for i in range(n): 
        distance.append((input().split(' ')) )
        distance[i]=list(map(int, distance[i]))    
    # print(distance)  
# 城市名字
# city_name = {1: 'L', 2: 'M', 3: 'N', 4: 'P', 5: 'B', 6: 'T'}
city_name = {}
for i in range(1,n+1,1):
    b=input("城市"+str(i)+"的名字")
    city_name[i] = b
# print(city_name)

# 求解

tsp = TSP(distance, city_name)

shortest_path, shortest_length = tsp.solve()

# 显示结果

print("最短环为%s，其总长度为%d" % (shortest_path, shortest_length))

说明

本实验完成于大二上学期（2021下半年），所使用语言为Python