基于搜索算法解决罗马尼亚度假问题（python实现+功能代码+测试代码） |
您所在的位置：网站首页 › 罗马尼亚详细地图 › 基于搜索算法解决罗马尼亚度假问题（python实现+功能代码+测试代码） |
基于搜索算法解决罗马尼亚度假问题（python实现+功能代码+测试代码）
|
问题定义
本实验要求用广度优先算法、深度优先算法、贪婪算法和AStar算法求解“罗马尼亚度假问题”，即找到从初始地点 Arad 到目的地点 Bucharest 的一条最佳路径。 只更新不在close表里的结点 def deepFirstSearch(self): startNode = Node() endNode = Node() for i in self.graph.nodes: if i.name == self.start: startNode = i if i.name == self.end: endNode = i close = [] open = [] # 模拟堆栈 open.append(startNode) while open: city = open.pop() if city not in close: close.append(city) if city == endNode: self.close_deepth = close return for i in reversed(city.next): # 从小到大放入，因为cities表是从小到大 for j in self.graph.nodes: if i[0] == j.name: i = j if i not in close: i.prev = city open.append(i) while i.prev: for j in i.next: if j[0] == i.prev.name: i.gn = j[1] + i.prev.gn i = i.prev break break 贪婪算法从起点开始搜索每一个相邻城市，保存下前驱结点和走过的路径长度 g(n), 如果走到重复结点，则判断 g(n)的大小进行前驱结点的更新。（类似Dijkstra算法） def greedSearch(self): startNode = Node() endNode = Node() for i in self.graph.nodes: if i.name == self.start: startNode = i if i.name == self.end: endNode = i close = [] open = deque() open.append(startNode) while open: open = sorted(open, key=functools.cmp_to_key(self.compareValue)) # open.sort(key=functools.cmp_to_key(self.compareValue)) city = open.pop() if city not in close: close.append(city) if city == endNode: # print("\n贪婪搜索路径为：") # self.printPath(close) # print("贪婪搜索close表为：") # for i in close: # print(i.name, end=" ") # print("\n搜索总代价为：", close[-1].gn) self.close_greed = close return for i in city.next: for j in self.graph.nodes: if i[0] == j.name: cost = i[1] i = j if i not in open and i not in close: i.prev = city # 更新前置结点之前判断是否路径更佳，而不是简单的判断是否被访问 open.append(i) # append是浅拷贝 while i.prev: for j in i.next: if j[0] == i.prev.name: i.gn = j[1] + i.prev.gn i = i.prev break elif i.gn > (city.gn + cost): i.prev = city # 更新前置结点之前判断是否路径更佳，而不是简单的判断是否被访问 open.append(i) # append是浅拷贝 while i.prev: for j in i.next: if j[0] == i.prev.name: i.gn = j[1] + i.prev.gn i = i.prev break break A*算法通过 f ( n ) = g ( n ) + h ( n ) f(n) = g(n) + h(n) f(n)=g(n)+h(n) 这个函数来计算每个节点的优先级。 其中： •f(n)是节点n的综合优先级。当我们选择下一个要遍历的节点时，我们总会选取综合优先级最高（值最小）的节点。 •g(n) 是节点n距离起点的代价。 •h(n)是节点n距离终点的预计代价，这也就是A*算法的启发函数。 def AstarAlgorithm(self): # 计算城市图每个点到终点城市的距离,获取h(n):节点n距离终点的预计代价,也就是A*算法的启发函数 distance = {} startNode = Node() endNode = Node() for i in self.graph.nodes: distance[i.name] = math.sqrt(pow(i.point[0] - self.cities[self.end][0][0], 2) + \ pow(i.point[1] - self.cities[self.end][0][1], 2)) if i.name == self.start: startNode = i if i.name == self.end: endNode = i close = [] open = deque() open.append(startNode) while open: # 对open表排序 open = deque(sorted(open, key=functools.cmp_to_key(self.compareNode))) city = open.popleft() # city结点不在close里面则放入city表 # city结点拥有最小的fn值 if city not in close: close.append(city) if city == endNode: # print("\nA*搜索close表为：") # for i in close: # print(i.name, end=" ") # print("\nA*搜索路径为：") # self.printPath(close) # print("\n搜索总代价为：", close[-1].gn) self.close_Astar = close return else: for i in city.next: for j in self.graph.nodes: if i[0] == j.name: cost = i[1] i = j if i not in open and i not in close: # 判断是否被访问 i.prev = city # print(f"{i.name} |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |