You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
81 lines
3.1 KiB
81 lines
3.1 KiB
# -*- 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 () # 开始遍历搜索合法路径 |