tsp/X3.py

# -*- coding: utf-8 -*-
# Time : 2023/10/30 15:49
# Author : lirunsheng
# User : l'r's
# Software: PyCharm
# File : X3.py

from collections import Counter
···
class Solve ():
    def node_dfs(self):  # 遍历 深度优先算法
        self.start = time.time()  # 记录开始时间
        self.way_sum = 0
        self.ans.clear()  # 初始化答案列表
        E.edge_del_all(1)  # 两点间仅保留距离最短路径
        for edge in d.Edges:  # 清空标记
            edge[4] = False
        i = 0  # 起始点
        flag = [0] * len(d.Nodes)  # 初始化已经过点
        cur = i  # 初始化起始点
        flag[cur] = 1  # 将起始点标记为已经过
        l = len(d.Nodes)
        distances = [[math.inf for _ in range(l)]
                     for _ in range(l)]
        result = d.node_coordinate(l)
        for j in d.Edges:  # 每一步选择当前最短的链接加到路径中去
            if j[0] >= len(result):
                break
            else:
                if j[6] < 99 and j[7] < 99:
                    distances[result[j[0]][0]][
                        result[j[0]][1]] = j[6]
                    distances[result[j[0]][1]][
                        result[j[0]][0]] = j[6]
        cost, ways = self.dfs(distances)
        print(self.way_sum)
        self.ans = ways.copy()
        if len(ways) != l + 1:
            tk.messagebox.askokcancel(title='结果',
                                message='该图不存在dfs路径')
            # print(ways)
            for way in range(len(ways) - 1):  # 标记一条路径
                d.Edges[G.way_node_edge(ways[way],
                                ways[way + 1])][4] = True
            self.end = time.time()  # 记录结束时间
            self.ans.clear()
            return -1
        for way in range(len(ways) - 1):  # 标记一条路径
            d.Edges[G.way_node_edge(ways[way],
                                ways[way + 1])][4] = True
        tk.messagebox.askokcancel(title='结果',
                                message='dfs算法路径')
        self.end = time.time()  # 记录结束时间
    def greedy(self, distances):
        num_cities = len(distances)
        visited = [False] * num_cities
        path = [0]  # 起始城市为0
        visited[0] = True
        for _ in range(num_cities - 1):
            curr_city = path[-1]
            min_distance = float('inf')
            next_city = None

            for city in range(num_cities):
                if not visited[city] and distances[curr_city][city] \
                        < min_distance and distances[curr_city][
                    city] != 0:
                    min_distance = distances[curr_city][city]
                    next_city = city
                    self.way_sum += 1  # 遍历路径的数目加一

            if next_city is not None:
                path.append(next_city)
                visited[next_city] = True
        if distances[path[-1]][0] != np.inf:
            path.append(0)  # 回到起始城市形成闭合路径
        # print(path)
        return path
if __name__ == '__main__':
    ···编程[11.2]与编程[11.5]主函数
    s. node_greedy ()  # 开始遍历搜索合法路径