数学建模

#数学建模| 来源: 网络整理| 查看: 265

2020.06.20更新了一下走过路径的判断，之前的代码考虑不周，产生覆盖现象，欢迎各位指导交流。 A*算法简介这里就不多说了传送门

author：xiao黄缓慢而坚定的生长

题目：假设采用一层金属布线，那么已经布线的方格被锁定，不允许其它线路穿过，否则会形成短路。图1所示为采用一层金属的通道布线例子，布线空间为4x7，空间上下沿的数字分别对应方格的引脚编号，编号相同的引脚需要连接起来。请针对此一层金属的“通道布线”问题完成建模和求解，并回答如下问题：在何种情况下，一层金属通道布线问题无解。测试例子：在这里插入图片描述

代码：

#需要进行抽象化的有：节点（属性有：x y坐标父节点 g及h ）地图（属性有高度宽度数据(数据中有可通行路径与障碍两种)） #A_star : # open_list (存放待测试的点，刚开始有start加入list，后面每一个current的相邻点（不能位于colse_list中且不是终点）要放到open_list中) 表示已经走过的点 # close_list(存放已测试的点，已经当过current的点，就放到close_list中) 存放已经探测过的点，不必再进行探测 # current 现在正在测试的点，要计算current周围的点的代价f 经过current后要放到close_list中将openlist代价f最小的node当作下一个current # start_point end_point #初始化地图 openlist closelist node #将start点放入openlist中 #while（未达到终点）： #取出 openlist 中的点将这个点设置为current 并放入closelist中 #for node_near in（current的临近点） #if（current的临近点 node_near 不在closelist中且不为障碍）： #计算 node_near 的f（f=g+h）大小 # if( node_near 不在 openlist 中) # 将 node_near 放入 openlist，并将其父节点设置为current 然后将f值设置为计算出的f值 # else if( node_near 在 openlist 中) # if（计算出的f大于在openlist中的f） # 不动作 # else if（计算出的f小于等于在openlist中的f） # 将 openlist 中的 node_near 的f值更新为计算出的新的更小的f值并将父节点设置为current #返回并继续循环 import sys #将地图中的点抽象化成类 class Point: def __init__(self, x, y): self.x = x self.y = y def __eq__(self, other): #函数重载 if((self.x == other.x )and (self.y == other.y)): return 1 else: return 0 #通过列表实现的地图的建立 class map_2d: def __init__(self,height,width): self.height = height self.width = width self.data = [] self.data = [[0 for i in range(width)] for j in range(height)] def map_show(self): # 显示 for i in range(self.height): for j in range(self.width): print(self.data[i][j], end=' ') print() def obstacle(self,obstacle_x,obstacle_y): # 设置障碍 self.data[obstacle_x][obstacle_y]=1 def end_draw(self,point,mark): # 这里要改 mark self.data[point.x][point.y] = mark #A*算法的实现 class A_star: # 设置node class Node: def __init__(self, point, endpoint, g): self.point = point # 自己的坐标 self.endpoint = endpoint # 自己的坐标 self.father = None # 父节点 self.g = g # g值 self.h = (abs(endpoint.x - point.x) + abs(endpoint.y - point.y)) * 10 # 计算h值 self.f = self.g + self.h #寻找临近点 def search_near(self,ud,rl): # up down right left nearpoint = Point(self.point.x + rl, self.point.y + ud) nearnode = A_star.Node(nearpoint, self.endpoint, self.g + 1) return nearnode def __init__(self,start_point,end_point,map):#需要传输到类中的，在此括号中写出 self.path=[] self.close_list=[] #存放已经走过的点 self.open_list=[] #存放需要进行探索的点 self.current = 0 #现在的node self.start_point=start_point self.end_point=end_point self.map = map #所在地图 def select_current(self): min=10000000 node_temp = 0 for ele in self.open_list: if ele.f

【本文地址】

数学建模

数学建模

今日新闻

推荐新闻