# -*- coding: utf-8 -*- # Time : 2023/10/30 15:49 # Author : lirunsheng # User : l'r's # Software: PyCharm # File : X4.py from tkinter import Tk import random import math import time import tkinter as tk from tkinter import * from tkinter import ttk from tkinter import messagebox import numpy as np import networkx as nx from PIL import Image, ImageTk MODE = 0 BLUE = "#0080FF" BLACK = "#000000" RED = "#FFAAAA" YELLOW = "#FFFACD" LINE = '#c8d2c8' GREY = '#070b19' GREEN = '#5ba585' NODE = '#33a8cd' ZERO = 'gold' MARK_NODE = 0 Specify_Nodes = '' Edges_list = [] NAME = [] CLICK = [0, 0, 0] List_Image = [] class Data: def __init__(self, source: int, num: int, mold: int): global NAME if num <= 0 or num > 10: raise ValueError("num must be a positive integer") self.styple = mold self.edgeinfo = 1 # 是否显示详情 self.nodes_num = num # 节点个数 self.ang = 360 / self.nodes_num # 圆心顶点角度 self.R = 300 # 外接圆半径 self.bc = 2 * self.R * math.sin(math.pi / self.nodes_num) # 节点之间的正多边形距离 self.canvas_len = int(2 * self.R + 80) # 画布边长 self.center = ((self.canvas_len+220) // 2, (self.canvas_len+230) // 2) # 画布中心点坐标 self.drop = [] self.index = 0 if source == 3 or source == 2: # 指定删除 # name = [str(i) for i in range(1, num + 2)] # print(name) if source == 2: NAME.pop() else: # print(Specify_Nodes) NAME.remove(Specify_Nodes) self.name = NAME self.coordinate = self.coord_creat() # 纯节点坐标 self.Nodes = self.nodes_creat() # 创建节点列表 # print(self.Nodes) self.Edges = self.edges_delete(source) # 创建第一条连接 else: if source == 1: name = str(int(NAME[-1])+1) # print(name) NAME.append(name) else: NAME = [str(i) for i in range(1, num + 1)] # print(NAME) self.name = NAME self.coordinate = self.coord_creat() # 纯节点坐标 self.Nodes = self.nodes_creat() # 创建节点列表 # print(self.Nodes) self.Edges = self.edges_creat(source) # 创建第一条连接 self.edge_add(2, source) # 创建第2条连接 self.edge_add(3, source) # 创建第3条连接 def nodes_creat(self, n_sum=None): if n_sum == None: n_sum = self.nodes_num nodes = [] # 初始化node表 # 设置画布中心点坐标x0,y0 x0 = self.center[0] y0 = self.center[1] for i in range(n_sum): # 通过几何运算得到多边形各个顶点坐标 rad = math.radians(i * self.ang) # 计算第i个点的弧度 x = int(math.cos(rad) * self.R) # 计算第i个顶点x坐标 y = int(math.sin(rad) * self.R) # 计算第i个顶点y坐标 # name = '' + str(i + 1) # 给第i个顶点命名 name = '' + self.name[i] mark = 0 # 节点为未标记 dominator = 1 # 设置为必经节点 nodes.append([i, name, mark, (x0 + x, y0 + y), dominator]) # 将当前节点加入node中 return nodes def edges_delete(self, source): edges = [] # 初始化所有链接集合 ser = 0 # print(str(int(Specify_Nodes) + 1)) for list_edge in Edges_list: # print(list_edge) edges.append([ser, list_edge[1], list_edge[2],list_edge[3], list_edge[4],list_edge[5], list_edge[6], list_edge[7], list_edge[8]]) # 将连接加入到边的集合中 nox = [int(num) for num in edges[ser][5].split('-')] # print(nox) if len(nox) == 2: ss = edges[ser][5] else: ss = edges[ser][5][:-2] # print(ss) if source == 2: if str(len(self.Nodes)+1) in ss: # print(edges[ser]) edges.pop() ser -= 1 else: if Specify_Nodes in ss: # print(edges[ser]) edges.pop() ser -= 1 ser += 1 return edges def edges_creat(self, source): edges = [] # 初始化所有链接集合 ser = 0 # 初始化链接对象编号 nodes = self.Nodes.copy() # 复制节点对象 nodes1 = self.Nodes.copy() # 复制节点对象 # print(nodes1) self.drop = [] for node in nodes: # 遍历节点对象 if node in nodes1: # 删除nodes1中当期遍历的节点信息 nodes1.remove(node) # print(nodes1) for node1 in nodes1: # 遍历删除后的节点信息 n1 = node[0] # 节点对象编号1 n2 = node1[0] # 节点对象编号2 if self.styple == 1: dist_c = random.randint(1, 99) # 随机生成距离成本 time_c = random.randint(1, 99) # 随机生成链接的时间 else: if self.drop.count(n2) > 3 or self.drop.count(n1) > 3: dist_c = random.randint(101, 120) # 随机生成距离成本 time_c = random.randint(101, 120) # 随机生成链接的时间 else: dist_c = random.randint(10, 120) # 随机生成距离成本 time_c = random.randint(10, 120) # 随机生成链接的时间 seq = 1 # 链接序号 mark = False # 连接是否标记 tag = f"{NAME[n1]}-{NAME[n2]}" # 链接标签 enable = 1 # 连接是否可用 if dist_c >= 100 or time_c >= 100: # 设置某些节点为不显示 enable = 0 else: self.drop.append(n1) self.drop.append(n2) if source == 1: # print(n2, len(self.Nodes)) if n2 == len(self.Nodes)-1: # print('进来了') edges.append([ser, int(NAME[n1])-1, int(NAME[n2])-1, enable, mark, tag, dist_c, time_c, seq]) # 将连接加入到边的集合中 else: # print(self.index) edges.append([ser, Edges_list[self.index][1], Edges_list[self.index][2], Edges_list[self.index][3], Edges_list[self.index][4], Edges_list[self.index][5],Edges_list[self.index][6], Edges_list[self.index][7], Edges_list[self.index][8]]) # 将连接加入到边的集合中 self.index += 1 else: edges.append([ser, int(NAME[n1])-1, int(NAME[n2])-1, enable, mark, tag, dist_c, time_c, seq]) # 将连接加入到边的集合中 ser += 1 # 计数加一 return edges def edge_add(self, no, source): nodes = self.Nodes.copy() # 复制节点对象 nodes1 = self.Nodes.copy() # 复制节点对象 for node in nodes: # 遍历节点对象 if node in nodes1: # 删除nodes1中当期遍历的节点信息 nodes1.remove(node) for node1 in nodes1: # 遍历删除后的节点信息 ser = len(self.Edges) # 链接序号 n1 = node[0] # 节点对象编号1 n2 = node1[0] # 节点对象编号2 show = 0 # 设置为不显示 mark = False # 连接是否标记 tag = f"{NAME[n1]}-{NAME[n2]}-{no}" # 链接标签 dist_c = random.randint(30, 100) # 距离成本 time_c = random.randint(1, 30) # 链接的时间 enable = no # 连接是否可用 if source == 1: if n2 == len(self.Nodes)-1: # print('进来了') self.Edges.append([ser, int(NAME[n1])-1, int(NAME[n2])-1, show, mark, tag, dist_c, time_c, enable]) # 将连接加入到边的集合中 else: # print(no ,self.index) self.Edges.append([ser, Edges_list[self.index][1], Edges_list[self.index][2], Edges_list[self.index][3], Edges_list[self.index][4], Edges_list[self.index][5], Edges_list[self.index][6], Edges_list[self.index][7], Edges_list[self.index][8]]) # 将连接加入到边的集合中 self.index += 1 else: self.Edges.append([ser, int(NAME[n1])-1, int(NAME[n2])-1, show, mark, tag, dist_c, time_c, enable]) def coord_creat(self): '''返回每个节点的坐标''' coordinate = [] x0 = self.center[0] y0 = self.center[1] for i in range(self.nodes_num): rad = math.radians(i * self.ang) x = int(math.cos(rad) * self.R) y = int(math.sin(rad) * self.R) coordinate.append((x0 + x, y0 + y)) return coordinate def node_co(self, key): # 通过节点编号返回编号的坐标 """通过节点编号返回编号的坐标""" nodes = self.Nodes for n in nodes: if n[1] == str(key + 1): return n[3] def node_no(self, key): # 通过节点编号返回编号的坐标 """通过节点编号返回编号的坐标""" nodes = self.Nodes for n in nodes: if n[1] == str(key + 1): return n[0] def node_coordinate(self, n): # 通过节点编号返回矩阵的坐标 result = [] for i in range(n): for j in range(i + 1, n): result.append((i, j)) return result # G = Graph() # print(1) nodes = 6 # 设置初始节点数量 d = Data(0, nodes, 0) class Graph: # Graph定义 def edge_info(self, cv: tk.Canvas, info: str, n1: tuple, n2: tuple): # 显示路径信息 if d.edgeinfo == 0: # 若设置为不显示则直接返回 return # print(n1) # print(n2) x = (n1[0] - n2[0]) // 2 + n2[0] # 计算中点x坐标 y = (n1[1] - n2[1]) // 2 + n2[1] # 计算中点y坐标 if (n2[1] - n1[1]) != 0: # 斜率为非0度时的显示 reat = math.atan((n2[0] - n1[0]) / (n2[1] - n1[1])) # 根据斜率计算弧度 ang = round(math.degrees(reat)) + 90 # 根据弧度转角度 if ang > 89: # 斜度大于90度调整坐标 text_x, text_y = x + 15, y else: # 斜度大于90度调整坐标 text_x, text_y = x, y + 15 else: # 斜率为0度时的显示 ang = round(math.degrees(0)) # 根据弧度转角度 text_x, text_y = x - 30, y + 10 # print(info.split(' ')[-1]) cv.create_text(text_x, text_y, text=f'{info.split()[-2]}', fill="black", font=('微软雅黑', 12), angle=ang) # 根据信息显示文字 def draw(self): cv.delete('all') # 清空画布 cv.create_image(0, 0, image=List_Image[40], anchor=tk.NW) dis, tim = self.edges_show(cv, d.Edges) # 绘制边 self.lab_show(frame_top, len(d.Nodes), tim, dis) # 显示边信息 self.nodes_show(cv) # 绘制点 cv.update() # 更新画布 def lab_show(self, frame: tk.Frame, nodes: int, time: int, distance: int): labs = ["节点数目", "时间", "距离(成本)"] x0 = d.canvas_len // 3 for i in range(len(labs)): lab1 = tk.Label(frame, text=labs[i], fg=BLACK, bg='white', font=('微软雅黑', 12)) if i == 0: lab2 = tk.Label(frame, text=f"{nodes}", bg='#F8F8FF', fg=BLACK, font=('微软雅黑', 12)) elif i == 1: lab2 = tk.Label(frame, text=f"{time}", bg='#F8F8FF', fg=BLACK, font=('微软雅黑', 12)) else: lab2 = tk.Label(frame, text=f"{distance}", bg='#F8F8FF', fg=BLACK, font=('微软雅黑', 12)) lab1.place(x=10 + x0 * i, y=10, width=80, height=30) lab2.place(x=10 + x0 * i + 80, y=10, width=80, height=30) lab1 = tk.Label(frame, text='分钟', fg=BLACK, bg='white', font=('微软雅黑', 12)) lab1.place(x=170 + x0, y=10, width=50, height=30) lab1 = tk.Label(frame, text='千米', fg=BLACK, bg='white', font=('微软雅黑', 12)) lab1.place(x=170 + x0 * 2, y=10, width=50, height=30) def nodes_show(self, cv: tk.Canvas): COL = NODE # 初始化节点颜色 for i in d.Nodes: # 遍历每一个节点 x, y = i[3] # 记录该节点坐标 if i[2] == 1 or i[2] == 2: # 如果节点被标记，则将节点标为红色 COL = RED elif i[0] == 0: # 如果节点为起始节点，则将节点标记为特殊颜色 COL = ZERO elif i[2] == 5: # 如果节点已经被访问，则将节点标记（用户路径功能） COL = 'gold' else: # 否则则使用初始颜色 COL = NODE if i[4] == 1: # 如果是必经节点，则加黑色边框 w = 1 else: # 如果是非必经节点，则没有边框 w = 0 # 根据坐标，圆的颜色与是否有边框绘制圆圈来表示节点 cv.create_oval(x - 20, y - 20, x + 20, y + 20, fill=COL, width=w, ) # outline='#ee28a3') cv.create_text(x, y, text=f'{i[1]}', fill=GREY, font=('华文楷体', 18)) cv.update() def edges_show(self, cv: tk.Canvas, edges: d.Edges): """ 显示链接 :param cv: tkcanvas对象 :return: """ distance = 0 # 初始化被标记的线的总路径 time1 = 0 # 初始化被标记的线的总时间 for edge in edges: node_1 = d.node_co(edge[1]) # 链接线编号对应的坐标1 node_2 = d.node_co(edge[2]) # 链接线编号对应的坐标2 # print(node_1,node_2) if edge[8] == 2 and edge[3] == 1: # 若该链接为两点间第二条连线 self.more_edge_show(2, edge) elif edge[8] == 3 and edge[3] == 1: # 若为两点间第3条连线 self.more_edge_show(3, edge) if edge[8] == 1 and edge[3] == 1: # 若为两点间第1条连线且该连接存在 self.edge_info(cv, f'{edge[5]} {edge[6]} {edge[7]}', node_1, node_2) point = [node_1, node_2] if edge[4] == 1 and edge[8] == 1 and edge[3] == 1: # 如果路径被标记，则用绿色绘制 if MODE == 1: cv.create_line(point, fill=RED, width=4) elif MODE == 2: cv.create_line(point, fill=BLUE, width=4) else: cv.create_line(point, fill=GREEN, width=4) distance += edge[6] # 更新总路径 time1 += edge[7] # 更新总时间 elif edge[8] == 1 and edge[3] == 1: # 如果是节点之间的第一条线，则用正常颜色标记 cv.create_line(point, fill=LINE, width=2) if d.Nodes[d.node_no(edge[2])][2] + d.Nodes[d.node_no(edge[2])][2] == 3: # 若该线被用户选中，则用蓝色虚线标记 cv.create_line(point, fill=BLUE, width=5, dash=(4, 14)) return (distance, time1) # 返回标记路径的总时间与路程 # def node_edge(self, a, b): # 根据点的编号找边的编号 # if a > b: # x = a # a = b # b = x # return int(a * (2 * len(d.Nodes) - a - 3) / 2 + b - 1) def node_edge(self, a, b): # 根据点的编号找边的编号 for edge in d.Edges: if a == edge[1] and b == edge[2]: return edge[0] if b == edge[1] and a == edge[2]: return edge[0] def way_node_edge(self, a, b): # 根据点的编号找边的编号 way = [] for node in d.Nodes: way.append(int(node[1])) # print(way) # print(a, b) x, y = way[a]-1, way[b]-1 for edge in d.Edges: if x == edge[1] and y == edge[2]: return edge[0] if y == edge[1] and x == edge[2]: return edge[0] def delete_all(self): cv.delete('all') # 清空画布 cv.create_image(0, 0, image=List_Image[40], anchor=tk.NW) self.lab_show(frame_top, 0, 0, 0) # 显示边信息 W.user_way = [0] window(2) class Edge: def __init__(self): self.mark = [] # 记录已标记的节点数目（连接操作） self.user_cur = 0 # 记录用户所在点 def node_edge(self, no, n1, n2): # 根据节点返回编号 if n1 > n2: n = n1 n1 = n2 n2 = n for e in d.Edges: if e[1] == n1 and e[2] == n2 and e[8] == no: return e[0] return -1 def edge_del_all(self, mode): # mode = 1:优先最短路径 # mode = 2:优先最短时间 # cur1 = node_edge() if mode == 1: for e in d.Edges: if (e[8] == 2 and e[3] == 1) or (e[8] == 3 and e[3] == 1): self.edge_merge_cost(e[1], e[2]) else: for e in d.Edges: if (e[8] == 2 and e[3] == 1) or (e[8] == 3 and e[3] == 1): self.edge_merge_time(e[1], e[2]) G.draw() def edge_merge_cost(self, n1, n2): cur1 = node_edge(n1, n2) # 初始化三条可能的边的编号 cur2 = node_edge(n1, n2, 2) # 初始化三条可能的边的编号 cur3 = node_edge(n1, n2, 3) # 初始化三条可能的边的编号 edges = [(cur1, d.Edges[cur1][6]), (cur2, d.Edges[cur2][6]), (cur3, d.Edges[cur3][6])] # 提出编号与路径花费 valid_edges = [(edge, cost) for edge, cost in edges if d.Edges[edge][3] == 1] # 过滤出存在的边 valid_edges.sort(key=lambda x: x[1]) # 按照 cost 排序，保留 cost 最小的边 for idx, (edge, _) in enumerate(valid_edges): d.Edges[edge][8] = idx + 1 # 设置边的优先级 d.Edges[edge][0] = edge # 确保边的索引正确 for edge, _ in valid_edges[1:]: # 对于非最优边，设置其为不显示 d.Edges[edge][3] = 0 def edge_merge_time(self, n1, n2): cur1 = node_edge(n1, n2) # 初始化三条可能的边的编号 cur2 = node_edge(n1, n2, 2) # 初始化三条可能的边的编号 cur3 = node_edge(n1, n2, 3) # 初始化三条可能的边的编号 edges = [(cur1, d.Edges[cur1][7]), (cur2, d.Edges[cur2][7]), (cur3, d.Edges[cur3][7])] # 提出编号与路径花费 valid_edges = [(edge, cost) for edge, cost in edges if d.Edges[edge][3] == 1] # 过滤出存在的边 valid_edges.sort(key=lambda x: x[1]) # 按照 cost 排序，保留 cost 最小的边 for idx, (edge, _) in enumerate(valid_edges): d.Edges[edge][8] = idx + 1 # 设置边的优先级 d.Edges[edge][0] = edge # 确保边的索引正确 for edge, _ in valid_edges[1:]: # 对于非最优边，设置其为不显示 d.Edges[edge][3] = 0 class Solve: def __init__(self): self.ans = [] # 记录答案 self.mutians = [] # 若有多个最短路，则保存在mutians中 self.way_sum = 0 # 记录遍历的路径数目 self.minn = float("inf") # 初始化最小值为正无穷 self.start = 0 # 起始点 self.end = 0 # 终点 self.mark = [] # 记录该点是否已经经过 self.user_cur = 0 # 记录用户所在点 self.cura = -1 # 记录用户选择的第一个点 self.curb = -1 # 记录用户选择的第二个点 self.con = 0 # 记录必经的节点数目 def node_greedy(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 flag = [0] * len(d.Nodes) # 初始化已经过点 cur = 0 # 初始化起始点 flag[cur] = 1 # 将起始点标记为已经过 l = len(d.Nodes) # print(l) 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[3] == 1: distances[result[j[0]][0]][result[j[0]][1]] = j[6] distances[result[j[0]][1]][result[j[0]][0]] = j[6] # print(distances) ways = self.greedy(distances) self.ans = ways.copy() # 如果找到的路径不合法，则表示贪心法无法求解得到合法路径 print(self.way_sum) # for i in distances: # print(i) if len(ways) != l+1 : tk.messagebox.askokcancel(title='结果', message='该图不存在贪心算法路径') print(ways) for way in range(len(ways) - 1): # 标记一条路径 d.Edges[G.way_node_edge(ways[way], ways[way + 1])][4] = True self.ans.clear() self.end = time.time() # 记录结束时间 return -1 for way in range(len(ways) - 1): # 标记一条路径 d.Edges[G.way_node_edge(ways[way], ways[way + 1])][4] = True # print(ways[len(ways) - 1], i) # d.Edges[G.way_node_edge(ways[len(ways) - 1], i)][4] = True # 标记起点终点形成环线 # print(ways) tk.messagebox.askokcancel(title='结果', message='贪心算法路径') 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 def tsp_backtracking(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 flag = [0] * len(d.Nodes) # 初始化已经过点 cur = 0 # 初始化起始点 flag[cur] = 1 # 将起始点标记为已经过 l = len(d.Nodes) # print(l) 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[3] == 1: distances[result[j[0]][0]][result[j[0]][1]] = j[6] distances[result[j[0]][1]][result[j[0]][0]] = j[6] # print(distances) ways = self.backtracking(distances) print(self.way_sum) if ways: # 判断路径是否存在 self.ans = ways.copy() 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='回溯算法路径') self.end = time.time() # 记录结束时间 else: tk.messagebox.askokcancel(title='结果', message='该图不存在回溯算法路径') self.end = time.time() # 记录结束时间 return -1 def backtracking(self, distances): num_cities = len(distances) path = [0] # 起始城市为0 visited = [False] * num_cities visited[0] = True min_distance = float('inf') shortest_path = None def backtrack(curr_city, curr_distance, visited, path): nonlocal min_distance, shortest_path if len(path) == num_cities: # 到达所有城市，更新最短路径 if curr_distance + distances[curr_city][0] < min_distance: min_distance = curr_distance + distances[curr_city][0] shortest_path = path + [0] else: for next_city in range(num_cities): if not visited[next_city]: # 选择下一个未访问的城市 visited[next_city] = True path.append(next_city) new_distance = curr_distance + distances[curr_city][next_city] self.way_sum += 1 # 遍历路径的数目加一 # 剪枝条件：当前路径已经大于最短路径，不继续搜索 if new_distance < min_distance: backtrack(next_city, new_distance, visited, path) # 回溯 visited[next_city] = False path.pop() backtrack(0, 0, visited, path) return shortest_path def auto_solve(self, number): global MODE, MARK_NODE MARK_NODE = 0 MODE = 2 if number == 1: # 回溯 self.tsp_backtracking() elif number == 2: self.node_greedy() # 贪心 else: # 深度优先算法 self.node_dfs() window(1) G.draw() 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[3] == 1: 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 dfs_tsp(self,graph, start, current, path, visited, cost, min_cost, min_path): if len(path) == len(graph) and graph[ current][start] != np.inf: path.append(start) cost += graph[current][start] if cost < min_cost[0]: min_cost[0] = cost min_path[0] = path.copy() path.pop() cost -= graph[current][start] return for next_node in range(len(graph)): if graph[current][next_node] != np.inf and \ not visited[next_node]: visited[next_node] = True path.append(next_node) cost += graph[current][next_node] self.way_sum += 1 # 遍历路径的数目加一 self.dfs_tsp(graph, start, next_node, path, visited, cost, min_cost, min_path) visited[next_node] = False path.pop() cost -= graph[current][next_node] def dfs(self, graph): n = len(graph) min_cost = [float('inf')] min_path = [[]] for start_node in range(n): visited = [False] * n path = [start_node] cost = 0 visited[start_node] = True self.dfs_tsp(graph, start_node, start_node, path, visited, cost, min_cost, min_path) return min_cost[0], min_path[0] def find_hamiltonian_cycles(self,start, distances): n = len(distances) path = [start] cycles = [] def is_valid(node, position): if distances[path[position - 1]][node] == np.inf: return False if node in path: return False return True def find_paths(node): for next_node in range(n): if is_valid(next_node, len(path)): path.append(next_node) if len(path) < n: find_paths(next_node) elif len(path) == n and distances[path[-1]][start] != np.inf: cycles.append(path + [start]) path.pop() find_paths(start) return cycles def check(self): 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] all_hamiltonian_cycles = self.find_hamiltonian_cycles(0, np.array(distances)) l = len(all_hamiltonian_cycles) if l: for cycles in all_hamiltonian_cycles: dis_ans = 0 for i in range(d.nodes_num): dis_ans += d.Edges[G.way_node_edge(cycles[i], cycles[i + 1])][6] print(cycles,dis_ans) if all_hamiltonian_cycles: tk.messagebox.askokcancel(title='结果', message=f'该图存在 {len(all_hamiltonian_cycles)} 条路径\n') else: tk.messagebox.askokcancel(title='结果', message='该图不能完全互通') def node_edge(n1, n2, no=1): # 根据点的编号找边的编号 if n1 > n2: # 为了防止充分编号，让n1小于n2 n1, n2 = n2, n1 for e in d.Edges: # 遍历所有路径，找到符合要求的返回 if e[1] == n1 and e[2] == n2 and e[8] == no: return e[0] return -1 # 若找不到，则返回-1 class Ways(): def __init__(self): self.user_way = [0] # 记录用户路径 self.user_cur = 0 # 记录用户所在点 self.user_flag = set() # 记录用户已经过的点 def auto_ways(self): # 标记用户路径 for w in d.Edges: # 清空路径标记 w[4] = 0 for N in d.Nodes: # 清空节点标记 N[2] = 0 for w in self.user_way: # 标记用户已选的点 d.Nodes[w][2] = 5 # 标记用户经过的路径 for w in range(len(self.user_way) - 1): d.Edges[G.node_edge(self.user_way[w],self.user_way[w + 1])][4] = 1 # 如果已经访问所有节点，自动回到初始节点 if len(set(self.user_way)) == len(d.Nodes): d.Edges[G.node_edge(self.user_way[len(self.user_way) - 1], 0)][4] = 1 G.draw() # 按照标记重新绘制图形 def check_user_best(self): # 检查用户路径是不是最佳路径 s.node_dfs() if not len(s.ans): return -1, 0 # 长度不一样肯定不匹配 if not len(self.user_way) == len(s.ans): return 0, 0 dis_user = 0 dis_ans = 0 num = len(self.user_way) for i in range(num - 1): dis_user += d.Edges[G.node_edge(self.user_way[i], self.user_way[i+1])][6] dis_ans += d.Edges[G.way_node_edge(s.ans[i], s.ans[i + 1])][6] return dis_ans, dis_user def show_best_ans(self, top, best, user): lab1 = tk.Label(top, text="最短路径:", fg=BLACK, font=('微软雅黑', 20)) b_way = "" # print(s.ans) for a in s.ans: b_way += d.Nodes[a][1] b_way += "->" b_way += d.Nodes[0][1] y0 = 0.05 lab2 = tk.Label(top, text=f"{b_way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab1.place(relx=0.1, rely=0.50 + y0, width=150, height=30) lab2.place(relx=0.4, rely=0.45 + y0, width=200, height=100) lab2 = tk.Label(top, text=f"最佳路径总成本：{best}\n用户路径总成本：{user}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab2.place(relx=0.4, rely=0.7 + y0, width=200, height=100) def show_BEST(self): best, user = self.check_user_best() # 计算最优路径与用户路径的总花费 if not best: lab1 = tk.Label(frame_left, text="不存在最短路径", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.3, rely=0.8, width=140, height=30) elif best == user: # 如果最优路径与用户路径的总花费相等，则说明用户路径是最短路径 lab1 = tk.Label(frame_left, text="用户路径是最短路径", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.3, rely=0.8, width=140, height=30) else: lab1 = tk.Label(frame_left, text="用户路径是不最短路径", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.3, rely=0.8, width=140, height=30) # else: # 否则说明用户路径不是最短路径 # self.servey_path_display() def servey_path_display(self): lab1 = tk.Label(frame_left, text="最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.75, width=80, height=30) # self.auto_ways() b_way = "" for a in s.ans: b_way += d.Nodes[a][1] b_way += "->" b_way = b_way[:-2] lab2 = tk.Label(frame_left, text=f"{b_way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab2.place(relx=0.1, rely=0.8, width=200, height=100) def check_user_greey(self): # 检查用户路径是不是贪心路径,不是的话返回错误点 s.node_greedy()# 计算贪心路径 if not len(s.ans): return -2 # 路径长度不一样肯定不匹配，直接返回 if not len(self.user_way) == len(s.ans): # self.auto_ways() return 0 way = [(int(node[1])-1) for node in d.Nodes] result1 = list(map(str, self.user_way)) result1 = ' '.join(result1) ways = [way[an] for an in s.ans] result2 = list(map(str, ways)) result3 = ' '.join(result2) result2.reverse() # 倒序排列列表元素 result4 = ' '.join(result2) if result4 == result1 or result3 == result1: return -1 #-1表示是贪心路径 else: x_1 = self.find_longest(result1, result4) x_2 = self.find_longest(result1, result3) return max(x_1, x_2) def find_longest(self, list1, list2): index = 0 while index < len(list1) and index < len(list2): if list1[index] != list2[index]: break index += 1 return index def show_greddy_ans(self, top): lab1 = tk.Label(top, text="贪心路径:", fg=BLACK, font=('微软雅黑', 20)) b_way = "" for a in s.ans: b_way += d.Nodes[a][1] b_way += "->" b_way += d.Nodes[0][1] y0 = 0.05 lab2 = tk.Label(top, text=f"{b_way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab1.place(relx=0.1, rely=0.50 + y0, width=150, height=30) lab2.place(relx=0.4, rely=0.45 + y0, width=200, height=100) # 对用户路径进行标记与记录 def way_route_markings(self, event): global MARK_NODE MARK_NODE = 2 # E.newedge_del_all(1) for w in frame_left.winfo_children(): w.destroy() # 清除右侧组件 left_window() self.user_way = [0] # lab = tk.Label(frame_left, text="路径操作", bg=RED, fg=BLACK, font=('微软雅黑', 20)) # lab.place(relx=0.18, rely=0.02, width=200, height=30) y0 = 0.1 global entry1,entry2,default_value # 定义默认值变量 default_value = tk.StringVar() default_value.set(self.user_way[-1]+1) laba1 = tk.Label(frame_left, text="当前节点:", bg='white', fg=BLACK, font=('微软雅黑', 15)) laba1.place(relx=0.2, rely=0.28 + y0, width=140, height=30) # 创建第一个输入框 entry1 = tk.Entry(frame_left, textvariable=default_value, bg="#F5F5F5") entry1.place(relx=0.6, rely=0.28 + y0, width=50, height=30) labb1 = tk.Label(frame_left, text="当前下一节点:", bg='white', fg=BLACK, font=('微软雅黑', 15)) labb1.place(relx=0.2, rely=0.33 + y0, width=140, height=30) # 创建第二个输入框 entry2 = tk.Entry(frame_left, bg="#F5F5F5") entry2.place(relx=0.6, rely=0.33 + y0, width=50, height=30) labb3 = tk.Label(frame_left, text="是否进行连接:", bg='white', fg=BLACK, font=('微软雅黑', 15)) labb3.place(relx=0.2, rely=0.4 + y0, width=140, height=30) # 按钮 button = tk.Button(frame_left, relief="flat", image=List_Image[38], bg='white', command=lambda: self.extract_values()) # 确定 button.place(relx=0.55, rely=0.38 + y0) button2 = tk.Button(frame_left, relief="flat", image=List_Image[36], bg='white', command=lambda: self.revoke()) # 撤销 button2.place(relx=0.18, rely=0.46 + y0) button3 = tk.Button(frame_left, relief="flat", image=List_Image[37], bg='white', command=lambda: self.clear_all_paths()) # 清除路径 button3.place(relx=0.5, rely=0.46 + y0) button4 = tk.Button(frame_left, relief="flat", image=List_Image[42], bg='white', command=lambda: self.greedy_path()) # 判断路径是否为贪心路径 button4.place(relx=0.18, rely=0.55 + y0) button5 = tk.Button(frame_left, relief="flat", image=List_Image[43], bg='white', command=lambda: self.shortest_path()) # 判断路径是否为最短路径 button5.place(relx=0.18, rely=0.62 + y0) self.user_path_display() def extract_values(self): global entry1, entry2, default_value global MARK_NODE MARK_NODE = 2 value1 = entry1.get() # 获取第一个输入框的值 value2 = entry2.get() # 获取第二个输入框的值 try: value1 = int(value1) # 将值转换为整数 value2 = int(value2) # 将值转换为整数 print("值1:", value1) print("值2:", value2) # 判断两点是否连接 if abs(value2) > 10 and abs(value1) > 10: tk.messagebox.askokcancel(title='错误', message='请重新输入正确的编号！') return else: E = 0 if value1 < value2: str_route = f'{value1}-{value2}' else: str_route = f'{value2}-{value1}' for item in d.Edges: if str_route == item[5]: if item[6] < 100 and item[7] < 100: if d.Edges[G.node_edge(value1-1, value2-1)][4]: E = 2 tk.messagebox.askokcancel(title='错误', message='城市已连接！') else: if self.user_way[-1] == (value1-1): E = 1 global MODE MODE = 1 self.user_way.append(value2 - 1) default_value.set(value2) d.Edges[G.node_edge(value1-1, value2-1)][4] = True entry1.config(textvariable=default_value) # 更新entry1的默认值 entry2.delete(0, tk.END) else: E = 3 tk.messagebox.askokcancel(title='错误', message='未连贯！') break print(E) if E == 1: G.draw() self.user_path_display() elif E == 0: tk.messagebox.askokcancel(title='错误', message='城市未连接！') except ValueError: tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！') def extract_ligature(self, n1, n2): global MARK_NODE MARK_NODE = 2 no = G.way_node_edge(n1, n2) flage = False if d.Edges[no][4]: tk.messagebox.askokcancel(title='错误', message='城市已连接！') elif d.Edges[no][3] == 0: tk.messagebox.askokcancel(title='错误', message='城市未连接！') else: if self.user_way[-1] == int(d.Nodes[n2][1]) - 1: nx = n1 n1 = n2 n2 = nx if self.user_way[-1] == int(d.Nodes[n1][1])-1: global MODE MODE = 1 self.user_way.append(int(d.Nodes[n2][1]) - 1) d.Edges[no][4] = True flage = True else: tk.messagebox.askokcancel(title='错误', message='未连贯！') if flage: G.draw() self.user_path_display() def revoke(self): global MARK_NODE MARK_NODE = 2 try: if len(self.user_way) > 1: value1 = int(self.user_way[-1]) # 将值转换为整数 value2 = int(self.user_way[-2]) # 将值转换为整数 if value1 < value2: str_route = f'{value1+1}-{value2+1}' else: str_route = f'{value2+1}-{value1+1}' # print(str_route) for item in d.Edges: # print(item) if str_route == item[5]: # print(item) global MODE global entry1, default_value MODE = 1 self.user_way.pop() print(self.user_way) d.Edges[G.node_edge(value1, value2)][4] = False default_value.set(value2+1) entry1.config(textvariable=default_value) # 更新entry1的默认值 break G.draw() self.user_path_display() else: tk.messagebox.askokcancel(title='提示', message='未进行路径建设！') except ValueError: tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！') def clear_all_paths(self): global MARK_NODE MARK_NODE = 2 try: if len(self.user_way) > 1: for i in range(len(self.user_way)-1): value1 = int(self.user_way[-1]) # 将值转换为整数 value2 = int(self.user_way[-2]) # 将值转换为整数 if value1 < value2: str_route = f'{value1 + 1}-{value2 + 1}' else: str_route = f'{value2 + 1}-{value1 + 1}' # print(str_route) for item in d.Edges: # print(item) if str_route == item[5]: # print(item) global MODE global entry1, default_value MODE = 3 self.user_way.pop() print(self.user_way) d.Edges[G.node_edge(value1, value2)][4] = False default_value.set(value2 + 1) entry1.config(textvariable=default_value) # 更新entry1的默认值 break else: tk.messagebox.askokcancel(title='提示', message='未进行路径建设！') for i in range(len(d.Edges)): d.Edges[i][4] = False G.draw() self.user_path_display() except ValueError: tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！') def greedy_path(self): g = self.check_user_greey() if g == -2: # cvx.create_text(0, 0, text="不存在贪心路径") lab1 = tk.Label(frame_left, text="不存在贪心路径", bg='white', fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.3, rely=0.8, width=180, height=30) elif g == -1: # 如果用户路径是贪心路径则显示 # cvx.create_text(0, 0, text="用户路径是贪心路径") lab1 = tk.Label(frame_left, text="用户路径是贪心路径", bg='white', fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.3, rely=0.8, width=180, height=30) # elif g: # self.servey_greedy_path() else: # print(self.user_way) # print(self.user_way[0:g]) # cvx.create_text(0, 0, text="用户路径不是是贪心路径") lab1 = tk.Label(frame_left, text="用户路径不是是贪心路径", bg='white', fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.3, rely=0.8, width=180, height=30) def servey_greedy_path(self): lab1 = tk.Label(frame_left, text="最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.75, width=80, height=30) # self.auto_ways() g_way = '' for a in s.ans: g_way += d.Nodes[a][1] g_way += "->" g_way = g_way[:-2] lab2 = tk.Label(frame_left, text=f"{g_way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab2.place(relx=0.1, rely=0.8, width=200, height=100) def shortest_path(self): best, user = self.check_user_best() # 计算最优路径与用户路径的总花费 if not best: lab1 = tk.Label(frame_left, text="不存在最短路径", bg='white', fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.33, rely=0.8, width=180, height=30) elif best == user: # 如果最优路径与用户路径的总花费相等，则说明用户路径是最短路径 lab1 = tk.Label(frame_left, text="用户路径是最短路径", bg='white', fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.33, rely=0.8, width=180, height=30) else: lab1 = tk.Label(frame_left, text="用户路径是不最短路径", bg='white', fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.33, rely=0.8, width=180, height=30) # if best == user: # 如果最优路径与用户路径的总花费相等，则说明用户路径是最短路径 # lab1 = tk.Label(frame_left, text="用户路径是最短路径", bg=RED, fg=BLACK, font=('微软雅黑', 12)) # lab1.place(relx=0.1, rely=0.8, width=180, height=30) # else: # 否则说明用户路径不是最短路径 # self.servey_path_display() # 用户路径展示 def user_path_display(self): lab1 = tk.Label(frame_left, text="用户路径:", bg='white', fg=BLACK, font=('微软雅黑', 15)) lab1.place(relx=0.15, rely=0.8, width=80, height=30) # self.auto_ways() way = "" # d_way = [] # for i in d.Nodes: # d_way.append(i[1]) for i in range(len(self.user_way)): if len(self.user_way)-i > 1: way += str(self.user_way[i]+1) way += "->" else: way += str(self.user_way[i]+1) lab2 = tk.Label(frame_left, text=f"{way}", bg='#F8F8FF', fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab2.place(relx=0.18, rely=0.84, width=300, height=100) def way_operate(self, event): global MARK_NODE for i in range(len(d.Edges)): d.Edges[i][4] = False MARK_NODE = 5 # E.newedge_del_all(1) for w in frame_left.winfo_children(): w.destroy() # 清除左侧组件 left_window() self.user_way = [0] y0 = 0.1 label1 = tk.Label(frame_left, text="节点1:", bg='white', fg=BLACK, font=('微软雅黑', 15)) label1.place(relx=0.15, rely=0.32 + y0, width=100, height=30) global entry3, entry4 # 创建第一个输入框 entry3 = tk.Entry(frame_left, bg='#F5F5F5') entry3.place(relx=0.6, rely=0.32 + y0, width=50, height=30) label2 = tk.Label(frame_left, text="节点2:", bg='white', fg=BLACK, font=('微软雅黑', 15)) label2.place(relx=0.15, rely=0.37 + y0, width=100, height=30) # 创建第二个输入框 entry4 = tk.Entry(frame_left, bg='#F5F5F5') entry4.place(relx=0.6, rely=0.37 + y0, width=50, height=30) button1 = tk.Button(frame_left, text='完全图', relief="flat", bg='#00BFFF', fg=BLACK, font=('微软雅黑', 15), command=lambda: self.complete_graph()) # 完全图 button1.place(relx=0.2, rely=0.43 + y0, width=100, height=30) button2 = tk.Button(frame_left, text='可达判断', relief="flat", bg='#00BFFF', fg=BLACK, font=('微软雅黑', 15), command=lambda: self.reachable_judgment()) # 节点可达性判断 button2.place(relx=0.6, rely=0.43 + y0, width=100, height=30) label3 = tk.Label(frame_left, text="是否进行两节点之间操作:", bg='white', fg=BLACK, font=('微软雅黑', 14)) label3.place(relx=0.15, rely=0.5 + y0, width=240, height=30) # 按钮 button3 = tk.Button(frame_left, relief="flat", image=List_Image[33], bg='white', command=lambda: self.way_add()) # 线路增加 button3.place(relx=0.2, rely=0.56 + y0) button4 = tk.Button(frame_left, relief="flat", image=List_Image[34], bg='white', command=lambda: self.way_change()) # 线路修改 button4.place(relx=0.2, rely=0.66 + y0) button5 = tk.Button(frame_left, relief="flat", image=List_Image[35], bg='white', command=lambda: self.way_delete()) # 线路删除 button5.place(relx=0.2, rely=0.76 + y0) def is_reachable(self, graph, start, target, visited): if start == target: return True visited.add(start) for neighbor in graph[start]: if neighbor not in visited: if self.is_reachable(graph, neighbor, target, visited): return True return False def complete_graph(self): l = len(d.Nodes) result = d.node_coordinate(l) for index in range(len(result)): if d.Edges[index][3] == 0: dist_c = random.randint(10, 99) # 随机生成距离成本 time_c = random.randint(10, 99) # 随机生成链接的时间 d.Edges[index][3] = 1 d.Edges[index][6] = dist_c d.Edges[index][7] = time_c G.draw() def reachable_judgment(self): try: a = int(entry3.get()) # 获取第一个输入框的值 b = int(entry4.get()) # 获取第二个输入框的值 l = len(d.Nodes) index_list = [] for i in d.Nodes: index_list.append(i[1]) dictionary = {i: [] for i in range(1, l + 1)} result = d.node_coordinate(l) # 生成无向图 for i in range(len(result)): if d.Edges[i][3] == 1: x = d.Edges[i][5].split('-')[0] y = d.Edges[i][5].split('-')[-1] dictionary[index_list.index(x)+1].append(index_list.index(y)+1) dictionary[index_list.index(y)+1].append(index_list.index(x)+1) start_node = index_list.index(str(a))+1 target_node = index_list.index(str(b))+1 visited_nodes = set() print(dictionary) flag = self.is_reachable(dictionary, start_node, target_node, visited_nodes) if flag: tk.messagebox.askokcancel(title='结果', message=f'{a}到{b}可达') else: tk.messagebox.askokcancel(title='结果', message=f'{a}到{b}不可达') except ValueError: tk.messagebox.askokcancel(title='结果', message='请输入节点') def way_add(self): global entry3, entry4 value1 = entry3.get() # 获取第一个输入框的值 value2 = entry4.get() # 获取第二个输入框的值 try: value1 = int(value1) # 将值转换为整数 value2 = int(value2) # 将值转换为整数 print("值1:", value1) print("值2:", value2) ways_list = [int(node[1]) for node in d.Nodes] # 判断两点是否连接 if abs(value2) > 10 and abs(value1) > 10: tk.messagebox.askokcancel(title='错误', message='请重新输入正确的编号！') return else: if value1 < value2: str_route = f'{value1}-{value2}' else: str_route = f'{value2}-{value1}' if d.drop.count(ways_list.index(value1)) > 4 or d.drop.count(ways_list.index(value2)) > 4: print(d.drop) tk.messagebox.askokcancel(title='提醒', message='当前节点已经到达最大连接数！') return no = 0 for item in d.Edges: if str_route == item[5]: no = G.node_edge(value1 - 1, value2 - 1) if d.Edges[no][3] == 1: tk.messagebox.askokcancel(title='提醒', message='当前路线已存在！') return top = creat_window(str_route+'路径参数配置') # 创建弹出窗口 distance_entry = create_input_box(top, "路程/公里：（1-99）", 101) # 创建一个输入框，获取卷积核大小 time_entry = create_input_box(top, "时间/h：（1-99）", 101) # 创建一个输入框，获取卷积步长 def get_input(): # 创建 # 获取输入框的内容 try: result1 = int(distance_entry.get()) result2 = int(time_entry.get()) print(result1,result2) if 100 > result1 > 0 and 0 < result2 < 100: d.Edges[no][3] = 1 d.Edges[no][6] = result1 d.Edges[no][7] = result2 top.destroy() # 关闭窗口 G.draw() else: tk.messagebox.askokcancel(title='错误', message='路程与时间范围错误！') except ValueError: tk.messagebox.askokcancel(title='错误', message='请输入正确的路程与时间！') button = tk.Button(top, text="获取信息", command=get_input) button.pack() except ValueError: tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！') def way_change(self): global entry3, entry4 value1 = entry3.get() # 获取第一个输入框的值 value2 = entry4.get() # 获取第二个输入框的值 try: value1 = int(value1) # 将值转换为整数 value2 = int(value2) # 将值转换为整数 print("值1:", value1) print("值2:", value2) ways_list = [int(node[1]) for node in d.Nodes] # 判断两点是否连接 if abs(value2) > 10 and abs(value1) > 10: tk.messagebox.askokcancel(title='错误', message='请重新输入正确的编号！') return else: if value1 < value2: str_route = f'{value1}-{value2}' else: str_route = f'{value2}-{value1}' no = 0 for item in d.Edges: if str_route == item[5]: no = G.node_edge(value1 - 1, value2 - 1) if d.Edges[no][3] == 0: tk.messagebox.askokcancel(title='提醒', message='当前路线不存在！') return top = creat_window(str_route + '路径参数修改') # 创建弹出窗口 distance_entry = create_input_box(top, "路程/公里：（1-99）", d.Edges[no][6]) # 创建一个输入框，获取卷积核大小 time_entry = create_input_box(top, "时间/h：（1-99）", d.Edges[no][7]) # 创建一个输入框，获取卷积步长 def get_input(): # 创建 # 获取输入框的内容 try: result1 = int(distance_entry.get()) result2 = int(time_entry.get()) print(result1, result2) if 100 > result1 > 0 and 0 < result2 < 100: d.Edges[no][6] = result1 d.Edges[no][7] = result2 top.destroy() # 关闭窗口 G.draw() else: tk.messagebox.askokcancel(title='错误', message='路程与时间范围错误！') except ValueError: tk.messagebox.askokcancel(title='错误', message='请输入正确的路程与时间！') button = tk.Button(top, text="获取信息", command=get_input) button.pack() except ValueError: tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！') def way_delete(self): global entry3, entry4 value1 = entry3.get() # 获取第一个输入框的值 value2 = entry4.get() # 获取第二个输入框的值 try: value1 = int(value1) # 将值转换为整数 value2 = int(value2) # 将值转换为整数 print("值1:", value1) print("值2:", value2) ways_list = [int(node[1]) for node in d.Nodes] # 判断两点是否连接 if abs(value2) > 10 and abs(value1) > 10: tk.messagebox.askokcancel(title='错误', message='请重新输入正确的编号！') return else: if value1 < value2: str_route = f'{value1}-{value2}' else: str_route = f'{value2}-{value1}' no = 0 for item in d.Edges: if str_route == item[5]: no = G.node_edge(value1 - 1, value2 - 1) if d.Edges[no][3] == 0: tk.messagebox.askokcancel(title='提醒', message='当前路线不存在！') return d.Edges[no][3] = 0 d.Edges[no][6] = 111 d.Edges[no][7] = 111 G.draw() except ValueError: tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！') class Node: # 标记节点按钮 def node_mark_display(self, event): global MARK_NODE, Specify_Nodes W.user_way = [0] MARK_NODE = 1 for w in frame_left.winfo_children(): w.destroy() # 清除右侧组件 left_window() curx = -1 y0 = 0.1 for i in d.Nodes: if i[2] == 1: curx = i[0] # lab = tk.Label(frame_left, text="节点操作", bg=RED, fg=BLACK, font=('微软雅黑', 20)) # lab.place(relx=0.18, rely=0.32, width=200, height=30) labx1 = tk.Label(frame_left, text=f"当前共有{len(d.Nodes)}个节点", bg='white', fg=BLACK, font=('微软雅黑', 20)) labx1.place(relx=0.15, rely=0.3 + y0, width=260, height=30) lab1 = tk.Label(frame_left, text="当前节点:", bg='white', fg=BLACK, font=('微软雅黑', 20)) if curx == -1: text = "未选择" else: text = f"{d.Nodes[curx][1]}" Specify_Nodes = str(d.Nodes[curx][1]) lab2 = tk.Label(frame_left, text=text, bg='#F8F8FF', fg=BLACK, font=('微软雅黑', 20)) lab1.place(relx=0.15, rely=0.4 + y0, width=160, height=50) lab2.place(relx=0.6, rely=0.4 + y0, width=100, height=50) # 按钮 button = tk.Button(frame_left, relief="flat", image=List_Image[30], bg='white', command=lambda: self.node_del_exact()) # 删除当前节点 button.place(relx=0.2, rely=0.5 + y0) button2 = tk.Button(frame_left, relief="flat", image=List_Image[32], bg='white', command=lambda: self.node_add()) # 增加一个节点 button2.place(relx=0.2, rely=0.6 + y0) button3 = tk.Button(frame_left, relief="flat", image=List_Image[31], bg='white', command=lambda: self.node_del()) # 减少一个节点 button3.place(relx=0.2, rely=0.7 + y0) def node_add(self): global d,Edges_list for i in range(len(d.Edges)): d.Edges[i][4] = False Edges_list = [] Edges_list = d.Edges # print(len(Edges_list)) # 增加一个节点 nodes = len(d.Nodes) + 1 # 如果节点数目大于五，则将连接详细信息改为不显示 if nodes > 5: d.edgeinfo = 0 if nodes > 10: tk.messagebox.askokcancel(title='错误', message='已达到最大节点') return d = Data(1, nodes, d.styple) # for i in d.Edges: # print(i) G.draw() self.node_mark_display(1) def node_del(self): global d,Edges_list for i in range(len(d.Edges)): d.Edges[i][4] = False Edges_list = [] Edges_list = d.Edges # print(len(Edges_list)) if d.nodes_num <= 2: tk.messagebox.askokcancel(title='错误', message='节点过少') return nodes = len(d.Nodes) - 1 if nodes < 6: d.edgeinfo = 1 d = Data(2, nodes, d.styple) # for i in d.Edges: # print(i) G.draw() self.node_mark_display(1) def node_del_exact(self): global d,Edges_list for i in range(len(d.Edges)): d.Edges[i][4] = False Edges_list = d.Edges if len(Specify_Nodes) == 3: tk.messagebox.askokcancel(title='错误', message='未选择节点') return if d.nodes_num <= 2:# 若删除节点以后节点过少，则直接返回并警告 tk.messagebox.askokcancel(title='错误', message='节点过少') return nodes = len(d.Nodes) - 1 if nodes < 6: d.edgeinfo = 1 d = Data(3, nodes, d.styple) # for i in d.Edges: # print(i) G.draw() self.node_mark_display(1) def refresh(): top = creat_window('路径生成') # 创建弹出窗口 distance_entry = create_input_box(top, "节点个数：（1-10）", 6) # 创建一个输入框，获取节点个数 # 创建一个下拉框，用于选择生成图类型 mode_combobox = create_dropdown_box(top, "生成图类型", ["TSP", "完全图"]) # 创建一个下拉框，用于选择生成图类型 def get_input(): # 创建 # 获取输入框的内容 try: result1 = int(distance_entry.get()) # 从下拉框中获取池化类型 result2 = mode_combobox.get() print(result1, result2) flag = 0 if result2!=None: if result2 == '完全图': flag = 1 if 10 > result1 > 0: global d if flag: d = Data(0, result1, 1) else: d = Data(0, result1, 0) top.destroy() # 关闭窗口 G.draw() # for i in d.Edges: # print(i) else: tk.messagebox.askokcancel(title='错误', message='节点数范围错误！') except ValueError: tk.messagebox.askokcancel(title='错误', message='请输入正确的节点数') button = tk.Button(top, text="获取信息", command=get_input) button.pack() def graph_init(): node = random.randint(4, 10) global d, MODE, MARK_NODE MARK_NODE = 0 MODE = 0 d = Data(0, node,0) print(node) W.user_way = [0] G.draw() window(2) def empty(): global MARK_NODE MARK_NODE = 0 G.delete_all() def auto_opera_mu(menu: tk.Menu): """TSP问题自动生成与自动求解相关""" menu_node = Menu(menu, tearoff=False) menu_node.add_command(label="自动随机产生一个TSP问题", command=lambda: graph_init()) menu_node.add_command(label="重新生成", command=lambda: refresh()) menu_node.add_command(label="清空", command=lambda: empty()) menu_node.add_command(label="自动求解最优路径-dfs遍历", command=lambda: s.auto_solve(3)) menu_node.add_command(label="自动求解优化路径-贪心", command=lambda: s.auto_solve(2)) menu_node.add_command(label="自动求解优化路径-回溯", command=lambda: s.auto_solve(1)) menu_node.add_command(label="检查是否存在路径", command=lambda: s.check()) # 在主目录菜单上新增"文件"选项，并通过menu参数与下拉菜单绑定 menu.add_cascade(label="TSP问题自动生成与自动求解相关", menu=menu_node) # 创建弹出窗口 def creat_window(title): top = tk.Toplevel(root) top.geometry("300x350") top.title(title) return top # 输入框 def create_input_box(top, text, value): box_label = tk.Label(top, text=text) box_label.pack(padx=10, pady=10) box_size = tk.IntVar(top, value=value) # 创建一个IntVar对象，并设置默认值为3 box_size_entry = tk.Entry(top, textvariable=box_size) # 关联IntVar对象 box_size_entry.pack(padx=20, pady=20) return box_size_entry # 下拉框 def create_dropdown_box(top, text, listvalues): # 创建一个下拉框，用于选择 box_mode_label = tk.Label(top, text=text) box_mode_label.pack(padx=10, pady=10) box_mode_combobox = ttk.Combobox(top) box_mode_combobox["values"] = listvalues box_mode_combobox.pack(padx=20, pady=15) return box_mode_combobox def dir2(x, y): # 计算两点间距离 return (x[0] - y[0]) * (x[0] - y[0]) + (x[1] - y[1]) * (x[1] - y[1]) def left1(event): global entry1, entry2, default_value, CLICK, entry3, entry4 # 查找鼠标左键按下时位置是否在某个节点内 n = -1 for node in d.Nodes: if dir2([event.x, event.y], [node[3][0], node[3][1]]) < 20 * 20: n = node[0] # n为点击的节点，若没有则为-1 m = mode.get() # 查看现在操作类型 if m == 1 and not n == -1: # 节点操作 # N.node_mark(n) if n >= len(d.Nodes): # 弹出对话框 tk.messagebox.askokcancel(title='错误', message='该节点不存在') return for node in d.Nodes: if node[0] == n: node[2] = 1 else: node[2] = 0 G.draw() if MARK_NODE == 1: # 限制节点操作 N.node_mark_display(1) elif MARK_NODE == 2: # 若是MARK_NODE==2，则可以进行路线画图操作 if CLICK[2] == 0: CLICK[0] = n default_value.set(d.Nodes[n][1]) entry1.config(textvariable=default_value) # 更新entry1的默认值 elif CLICK[2] == 1: CLICK[1] = n W.extract_ligature(CLICK[0], CLICK[1]) CLICK[2] = -1 CLICK[2] += 1 elif MARK_NODE == 5: # 若是MARK_NODE==5，则可以进行节点连接操作 if CLICK[2] == 0: CLICK[0] = n entry3.delete(0, tk.END) # 设置输入框的值为 节点 entry3.insert(0, d.Nodes[n][1]) elif CLICK[2] == 1: CLICK[1] = n # W.extract_ligature(CLICK[0], CLICK[1]) entry4.delete(0, tk.END) # 设置输入框的值为 节点 entry4.insert(0, d.Nodes[n][1]) CLICK[2] = -1 CLICK[2] += 1 print(n) def element_reading(): global List_Image folder_path = 'K:/work/traveler/background/' image_path = ['1_红.png', '1_绿.png', '1_蓝.png', '2_红.png', '2_绿.png', '2_蓝.png', '3_红.png', '3_绿.png', '3_蓝.png', '4_红.png', '4_绿.png', '4_蓝.png', '5_红.png', '5_绿.png', '5_蓝.png', '6_红.png', '6_绿.png', '6_蓝.png', '7_红.png', '7_绿.png', '7_蓝.png', '8_红.png', '8_绿.png', '8_蓝.png', '9_红.png', '9_绿.png', '9_蓝.png', '10_红.png', '10_绿.png', '10_蓝.png', '删除节点.png', '减少节点.png', '增加节点.png', '线路增加.png', '线路修改.png', '线路删除.png', '撤销.png', '清除路径.png', '确认.png', '编组9.png', '背景.png', '矩形.png', '判断路径是否为贪心路径.png', '判断路径是否为最短路径.png', '矩形2.png', '完全图.png', '可达判断.png'] for path in image_path[:30]: # 1-10球加载 List_Image.append(element(folder_path+path, 50, 50)) for path in image_path[30:36]: # 节点操作与连线操作功能按钮 List_Image.append(element(folder_path + path, 280, 50)) List_Image.append(element(folder_path + image_path[36], 140, 50)) # 撤销 List_Image.append(element(folder_path + image_path[37], 140, 50)) # 清除路径 List_Image.append(element(folder_path + image_path[38], 120, 50)) # 确认 List_Image.append(element(folder_path + image_path[39], 380, 100)) # 编组_9 List_Image.append(element(folder_path + image_path[40], 900, 900)) # 背景 List_Image.append(element(folder_path + image_path[41], 380, 140)) # 小矩形 List_Image.append(element(folder_path + image_path[42], 300, 50)) # 判断路径是否为贪心路径 List_Image.append(element(folder_path + image_path[43], 300, 50)) # 判断路径是否为最短路径 List_Image.append(element(folder_path + image_path[44], 380, 530)) # 大矩形 List_Image.append(element(folder_path + image_path[45], 140, 50)) # 完全图 List_Image.append(element(folder_path + image_path[46], 140, 50)) # 可达判断 def element(path, width, height): # 加载图元对应的图片文件 img = Image.open(path) # 使用resize方法调整图片 img = img.resize((width, height)) # 把Image对象转换成PhotoImage对象 img = ImageTk.PhotoImage(img) # 保存图片的引用，防止被垃圾回收 root.img = img return img def window(event): global MARK_NODE MARK_NODE = 0 for w in frame_left.winfo_children(): w.destroy() # 清除右侧组件 left_window() Label_1 = tk.Label(frame_left, text="遍历节点数目", bg='white', fg=BLACK, font=('微软雅黑', 16)) Label_1.place(x=50, y=330, width=180, height=40) Label_2 = tk.Label(frame_left, text="求解花费时间", bg='white', fg=BLACK, font=('微软雅黑', 16)) Label_2.place(x=50, y=450, width=180, height=40) Label_3 = tk.Label(frame_left, text="最短路径", bg='white', fg=BLACK, font=('微软雅黑', 16)) Label_3.place(x=50, y=570, width=140, height=40) if event == 2: lab1 = tk.Label(frame_left, text=f"{0}", bg='#F8F8FF', fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab1.place(x=80, y=370, width=300, height=60) lab2 = tk.Label(frame_left, text=f"{0}", bg='#F8F8FF', fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab2.place(x=80, y=490, width=300, height=60) lab3 = tk.Label(frame_left, text=f"{1}", bg='#F8F8FF', fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab3.place(x=80, y=610, width=300, height=140) else: lab1 = tk.Label(frame_left, text=f"{s.way_sum}", bg='#F8F8FF', fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab1.place(x=80, y=370, width=300, height=60) t = round(s.end - s.start, 4) lab2 = tk.Label(frame_left, text=f"{t}", bg='#F8F8FF', fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab2.place(x=80, y=490, width=300, height=60) g_way = '' if len(s.ans) > 0: for a in s.ans: g_way += d.Nodes[a][1] g_way += "->" g_way = g_way[:-2] else: g_way='1' lab3 = tk.Label(frame_left, text=f"{g_way}", bg='#F8F8FF', fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab3.place(x=80, y=610, width=300, height=140) def left_window(): background_button = tk.Label(frame_left, image=List_Image[39], bg='#FFFAF0') # 编组 background_button.place(x=50, y=20, width=380, height=100) background_button.bind("", window) # # 创建 Label 组件来显示背景图片 background_on = tk.Label(frame_left, bg='#FFFAF0', image=List_Image[41]) # 小矩形背景 background_on.place(x=50, y=140, width=380, height=140) if MARK_NODE == 1: background_color = [BLACK, '#DCDCDC', '#DCDCDC'] elif MARK_NODE == 5: background_color = ['#DCDCDC', BLACK, '#DCDCDC'] elif MARK_NODE == 2: background_color = ['#DCDCDC', '#DCDCDC', BLACK] else: background_color = ['#DCDCDC', '#DCDCDC', '#DCDCDC'] Label_button1 = tk.Label(frame_left, text="节点操作", bg='white', fg=background_color[0], font=('微软雅黑', 15)) Label_button1.place(x=60, y=180, width=80, height=50) Label_button1.bind("", N.node_mark_display) Label_button2 = tk.Label(frame_left, text="连接操作", bg='white', fg=background_color[1], font=('微软雅黑', 15)) Label_button2.place(x=200, y=180, width=80, height=50) Label_button2.bind("", W.way_operate) Label_button3 = tk.Label(frame_left, text="路径操作", bg='white', fg=background_color[2], font=('微软雅黑', 15)) Label_button3.place(x=340, y=180, width=80, height=50) Label_button3.bind("", W.way_route_markings) background_below = tk.Label(frame_left, bg='#FFFAF0', image=List_Image[44]) # 大矩形背景 background_below.place(x=50, y=300, width=380, height=530) if __name__ == '__main__': root = Tk() # 设置主界面 root.title("旅行商问题") # 设置标题 root.geometry("1400x900") # 设置大小 root.resizable(0, 0) # 设置不能调整显示边框 element_reading() frame_top = tk.Frame(root, bg='white', width=1400, height=50, highlightthickness=0) frame_top.place(x=0, y=0) # 绘制信息输出栏 frame_left = tk.Frame(root, bg='#FFFAF0', highlightthickness=0, width=500, height=850) # 左边栏 frame_left.place(x=0, y=50) # 左边栏 cv = tk.Canvas(root, bg='#FFFAF0', bd=0, relief="flat", width=900, height=850, highlightthickness=0) cv.place(x=500, y=50) # 放置绘图Canvas画布 cv.create_image(0, 0, image=List_Image[40], anchor=tk.NW) # 背景 G = Graph() mode = tk.IntVar(value=1) main_menu = tk.Menu(root) root.config(menu=main_menu) cv.bind('', left1) E = Edge() W = Ways() s = Solve() N = Node() auto_opera_mu(main_menu) window(2) G.lab_show(frame_top, 0, 0, 0) # 显示边信息 root.mainloop()