python 编程练习——旅行售货员问题 (Traveling Salesman Problem,TSP)

Python YX ⋅ 于 2020-05-10 18:45:09 ⋅ 最后回复由 karb0n 2020-05-19 23:58:20 ⋅ 470 阅读
根据下图,用python写出例7最近邻点和最小插入法代码

file
file

参考文献

中学数学建模与赛题集锦

file

成为第一个点赞的人吧 :bowtie:
回复数量: 6
  • karb0n 突然发现,我发的帖子全是软件安装方法
    2020-05-11 02:20:19

    这是个很经典的算法题!可以练习好多种算法 :laughing:

  • YX MOD
    2020-05-11 17:01:11

    @karb0n
    你来先写一个,用python

  • 热心市民小杨
    2020-05-18 18:03:27
    '''
    采用最近邻法求最短路径和距离
    '''
    
    def find_spath(start_point):
        row = path_matrix[start_point]
        copy_row = row.copy()
        path_points.append(start_point)
        walked_points = []
        for i in path_points:
            walked_points.append(copy_row[i])
        for point in walked_points:
            copy_row.remove(point)
        if len(path_points) < 6:
            next_path_length = min(copy_row)
            next_point = row.index(next_path_length)
            path_length.append(next_path_length)
            find_spath(next_point)
        else:
            next_path_length = path_matrix[start_point][path_points[0]]
            path_points.append(path_points[0])
            path_length.append(next_path_length)
        return path_points, path_length
    
    def print_spath(path_points, path_length):
        path = ''
        for i, num in enumerate(path_points):
            path += path_dict[num]
            if i == 6:
                break
            path += '->'
        print('以{}为起点的最短路径为:{}'.format(path_dict[path_points[0]], path))
        print('此路径的最短距离为:{}km'.format(sum(path_length)))
        return path, sum(path_length)
    
    if __name__ == '__main__':
        path_matrix = [[0, 8943, 5582, 344, 8164, 9588],
                       [8943, 0, 3363, 9212, 12475, 11319],
                       [5582, 3363, 0, 5850, 11012, 10872],
                       [344, 9212, 5850, 0, 8238, 9739],
                       [8164, 12475, 11012, 8238, 0, 2103],
                       [9588, 11319, 10872, 9739, 2103, 0]]
        path_dict = {0: 'L', 1: 'M', 2: 'N', 3: 'P', 4: 'B', 5: 'T'}
        row_path_matrix = len(path_matrix)
        path_save = []
        sum_save = []
        for i in range(row_path_matrix):
            path_points = []
            path_length = []
            path_points_new, path_length_new = find_spath(i)
            path, sum_path = print_spath(path_points_new, path_length_new)
            path_save.append(path)
            sum_save.append(sum_path)
        print('#' * 30)
        print('所以我们可得最短路径和最短距离为:')
        min_path = min(sum_save)
        for i, num in enumerate(sum_save):
            if num == min_path:
                print('最短路径为:{},其最短距离为:{}km'.format(path_save[i], min_path))
        print('#' * 30)
  • 热心市民小杨
    2020-05-18 18:03:55

    以L为起点的最短路径为:L->P->N->M->T->B->L
    此路径的最短距离为:31143km
    以M为起点的最短路径为:M->N->L->P->B->T->M
    此路径的最短距离为:30949km
    以N为起点的最短路径为:N->M->L->P->B->T->N
    此路径的最短距离为:33863km
    以P为起点的最短路径为:P->L->N->M->T->B->P
    此路径的最短距离为:30949km
    以B为起点的最短路径为:B->T->L->P->N->M->B
    此路径的最短距离为:33723km
    以T为起点的最短路径为:T->B->L->P->N->M->T
    此路径的最短距离为:31143km
    ##############################
    所以我们可得最短路径和最短距离为:
    最短路径为:M->N->L->P->B->T->M,其最短距离为:30949km
    最短路径为:P->L->N->M->T->B->P,其最短距离为:30949km
    ##############################

  • 姜姜
    2020-05-19 16:02:10

    """
    Functions:
    find_path:
    Data structures:
    path_vertexs:保存遍历过的顶点,防止重复遍历
    path_length:保存遍历过的每条边的权值
    """

    def find_path(j):
        path_vertexs.append(j)  # 把该节点标记为已走过
        row = c[j]
        # 创建copy_row,删除row中已走过的顶点,防止直接在row上操作.
        copy_row = [value for value in row]
        walked_vertex = []
    
        for i in path_vertexs:  # 已走过的顶点
            walked_vertex.append(copy_row[i])
        for vertex in walked_vertex:
            copy_row.remove(vertex)
    
        # 寻找row中的未遍历过的最短边
        if len(path_vertexs) < 6:
            min_e = min(copy_row)
            next_vertex = row.index(min_e)
            path_length.append(min_e)
            find_path(next_vertex)
        else:
            min_e = c[j][path_vertexs[0]]
            path_vertexs.append(path_vertexs[0])
            path_length.append(min_e)
        return path_vertexs, path_length
    
    def print_spath(path_vertexs, path_length):
        path = ''
        for i, vertex in enumerate(path_vertexs):
            path += str(vertex)
            if i == 6:
                break
            path += '->'
        print('以{}为起点的最短路径为:{}'.format(path_map[path_vertexs[0]], path))
        print('此路径的最短距离为:', sum(path_length), 'km')
        return path, sum(path_length)
    
    if __name__ == '__main__':
        c = [[0, 8943, 5582, 344, 8164, 9588],
             [8943, 0, 3363, 9212, 12475, 11319],
             [5582, 3363, 0, 5850, 11012, 10872],
             [344, 9212, 5850, 0, 8238, 9739],
             [8164, 12475, 11012, 8238, 0, 2103],
             [9588, 11319, 10872, 9739, 2103, 0]]
        path_map = {0: 'L', 1: 'M', 2: 'N', 3: 'P', 4: 'B', 5: 'T'}
        row_c = len(c)
        path_save = []
        sum_save = []
        for i in range(row_c):
            path_vertexs = []
            path_length = []
            path_vertexs_next, path_length_next = find_path(i)
            path, sum_path = print_spath(path_vertexs_next, path_length_next)
            path_save.append(path)
            sum_save.append(sum_path)
  • karb0n 突然发现,我发的帖子全是软件安装方法
    2020-05-19 23:58:20

    回溯法求解旅行商问题

    回溯法和最近邻法的区别是,回溯法可以求得全局最优解,而最近邻法求得的是近似优解。
    不过,由于回溯法的时间复杂度为O(n²),所以城市数量非常多时仍然不太适用。
    代码:

    # -*- coding: utf-8 -*-
    
    # 回溯法求解旅行商问题
    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__':
        # 记录两个城市之间距离的邻接矩阵
        distance = [[0, 8943, 5582, 344, 8164, 9588],
                    [8943, 0, 3363, 9212, 12475, 11319],
                    [5582, 3363, 0, 5850, 11012, 10872],
                    [344, 9212, 5850, 0, 8238, 9739],
                    [8164, 12475, 11012, 8238, 0, 2103],
                    [9588, 11319, 10872, 9739, 2103, 0]]
        # 城市名字
        city_name = {1: 'L', 2: 'M', 3: 'N', 4: 'P', 5: 'B', 6: 'T'}
        # 求解
        tsp = TSP(distance, city_name)
        shortest_path, shortest_length = tsp.solve()
        # 显示结果
        print("最短环为%s,其总长度为%d" % (shortest_path, shortest_length))

    计算结果:

    最短环为LNMTBPL,其总长度为30949
暂无评论~~
  • 请注意单词拼写,以及中英文排版,参考此页
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`, 更多语法请见这里 Markdown 语法
  • 支持表情,使用方法请见 Emoji 自动补全来咯,可用的 Emoji 请见 :metal: :point_right: Emoji 列表 :star: :sparkles:
  • 上传图片, 支持拖拽和剪切板黏贴上传, 格式限制 - jpg, png, gif
  • 发布框支持本地存储功能,会在内容变更时保存,「提交」按钮点击时清空
Ctrl+Enter