婚纱摄影网站建设,用canvas做网站,支付网站域名费会计分录怎么做,宁波制作网站企业文章目录 第1关#xff1a;搜索策略第2关#xff1a;盲目搜索第3关#xff1a;启发式搜索 - 扫地机器人最短路径搜索第4关#xff1a;搜索算法应用 - 四皇后问题 第1关#xff1a;搜索策略
什么是搜索技术 人类的思维过程可以看作是一个搜索过程。从小学到现在#xff0… 文章目录 第1关搜索策略第2关盲目搜索第3关启发式搜索 - 扫地机器人最短路径搜索第4关搜索算法应用 - 四皇后问题 第1关搜索策略
什么是搜索技术 人类的思维过程可以看作是一个搜索过程。从小学到现在你一定遇到过很多智力游戏问题如传教士和野人问题有 3 个传教士和 3 个野人来到河边准备过河河边有一条船每次最多坐 2 人。但是任何时刻在河的两边以及船上的野人数量不能超过传教士的数量不然传教士就会被吃掉。 如果让你来玩这个智力游戏在每一次过河之后都会有几种过河方案供你选择到底哪种方案才有利于在满足题目所规定的约束条件下顺利过河这就是搜索问题。
经过反复努力和试探你终于找到了一种解决办法。在高兴之余你可能马上又会想到这个方案所用的步骤是否最少也就是说它是最优的吗如果不是如何才能找到最优方案在计算机上又如何实现这样的搜索这些问题就是本关要介绍的搜索问题而求解这类搜索问题的技术称之为搜索技术。 第2关盲目搜索 编程要求 根据提示在右侧编辑器补充代码完成 PlayMazz 函数实现在迷宫里从起点走到出口的功能。其中
mazz 表示迷宫类型为字典 start 表示起点类型为字符 end 表示出口类型为字符。
测试说明 您只需完成 PlayMazz 函数中的 Begin-End 段即可平台会对你编写的代码进行测试。其中测试输入为字典的形式其中 mazz 部分表示迷宫start 部分表示迷宫起点end 部分表示迷宫出口。
测试输入{mazz:{A: [B, C],B: [D, E],C: [F],F: [G, H],D: [],E: [],G: [],H: []},start:A,end:D}
预期输出ABCD
开始你的任务吧祝你成功
def PlayMazz(mazz, start, end):走迷宫从start走到end:param mazz: 迷宫:param start: 迷宫的起点:param end: 迷宫的出口:vertex: 迷宫中正在进行广度优先搜索算法的当前位置# queue为队列当队列为空或者当前地点为H时搜索结束visited, queue set(), [start]while queue:# 从队列中出队即当前所处的地点vertex queue.pop(0)if vertex not in visited:visited.add(vertex)print(vertex, end)#********* Begin *********## 当走到出口时结束算法if vertex end:break#********* End *********##********* Begin *********## 将当前所处地点所能走到的地点放入队列for v in mazz[vertex]:if v not in visited:queue.append(v)#********* End *********#
第3关启发式搜索 - 扫地机器人最短路径搜索 编程要求 在右侧编辑器补充代码完成 A_star 函数实现从 start 走到 end 的自动寻路功能。其中
map 表示地图。 start 表示出发地类型为列表如 [1,2] 表示出发地为地图中的第 1 行第 2 列的方块。 end 表示目的地类型为列表如 [1,2] 表示目的地为地图中的第 1 行第 2 列的方块。
测试说明 您只需完成 A_star 函数中的 Begin-End 段即可平台会对你编写的代码进行测试并将您寻找到的路径打印出来。其中测试输入为字典的形式其中 map_size 部分表示地图的长和宽 start 部分表示出发地的坐标 end 部分表示目的地的坐标 obstacleList 部分表示障碍物坐标的列表。
测试输入 {‘map_size’:[10, 10], ‘start’:[1, 2], ‘end’:[6, 7], ‘obstacleList’:[[1, 1], [2, 1], [3, 1], [4, 3], [1, 3], [2, 3], [3, 3], [0, 1], [5, 1], [5, 3]]}
预期输出 start-(1,4)-(2,5)-(3,6)-(4,7)-(5,8)-(6,8)-end
开始你的任务吧祝你成功
from a_star_utils import Nodedef A_star(map, mapSize, start, end):A*算法从start走到end:param map:地图:param mapSize:地图大小例如[10,10]表示地图长10宽10:param start:表示出发地类型为列表如[1,2]表示出发地为地图中的第1行第2列的方块:param end:表示目的地类型为列表如[1,2]表示目的地为地图中的第1行第2列的方块:return:从出发地到目的地的路径openedList []closedList []#********* Begin *********## 获得出发地方块的信息并将信息保存为 node 变量startNode map[start[0]][start[1]]startNode.distanceFromOri 0startNode.allDistance startNode.distanceFromOri startNode.distanceFromDesstartNode.parent Nonenode startNode # 将当前方块保存为 node 变量#********* End *********##********* Begin *********## 将当前方块存到开启列表中openedList.append(node)node.added True#********* End *********#while len(openedList) ! 0:# 从开启列表中取出F值最小的节点node openedList.pop(0)node.closed True# 如果当前节点是终点结束搜索并回溯路径if node.y end[0] and node.x end[1]:finalPath []while node is not None:finalPath.append(node)node node.parentfinalPath.reverse()return finalPath# 开始检查邻居节点neighboursList []y, x node.y, node.xparentDistanceFromOri node.distanceFromOri# 寻找周围的邻居节点上下左右斜向for dy in (y 1, y, y - 1):if dy 0 or dy mapSize[0]:continuefor dx in (x 1, x, x - 1):if dx 0 or dx mapSize[1]:continueneedNode map[dy][dx]# 跳过障碍物或已处理过的节点if needNode.unable or needNode.closed or needNode.added:continue# 计算距离代价if abs(dy - y) abs(dx - x) 1: # 直线代价distanceFromOri parentDistanceFromOri 1else: # 对角线代价distanceFromOri parentDistanceFromOri 1.4# 更新邻居节点的G值距离起点的代价if needNode in neighboursList:if distanceFromOri needNode.distanceFromOri:needNode.distanceFromOri distanceFromOrielse:needNode.distanceFromOri distanceFromOrineighboursList.append(needNode)# 处理每个邻居节点计算F值并加入开启列表for needNode in neighboursList:needNode.parent node# 计算F值needNode.allDistance needNode.distanceFromOri needNode.distanceFromDesneedNode.added TrueopenedList.append(needNode)# 将开启列表按照F值进行排序F值小的优先处理openedList.sort(keylambda x: x.allDistance)return None
第4关搜索算法应用 - 四皇后问题
任务描述 本关任务编写一个能求解四皇后问题的 Python 程序。
相关知识 为了完成本关任务你需要掌握四皇后问题。
四皇后问题 在 n 行 n 列的国际象棋上摆放 n 个皇后使其不能互相攻击即任意两个皇后都不能处于同一行、同一列或同一斜线上。请问有多少种摆法以及如何摆放这些皇后。这就是经典的 n 皇后问题。如下图所示 编程要求 根据提示在右侧编辑器补充代码完成 FourQueens 函数实现找出所有可能的皇后摆法。其中
mark 表示皇后的位置信息例如 [0,1,3,2] 表示棋盘的第 1 行第 1 列第 2 行第 2 列第 3 行第 4 列第 4 行第 3 列放置了皇后。例如 [1, None, None, None] 表示第 1 行第 2 列放置了皇后其他行没有放置皇后。
cur 表示当前准备在第几行放置皇后例如 cur1 时表示准备在第 2 行放置皇后。
result :表示存放皇后摆放结果的列表类型为二维 list。
测试说明 您只需完成 FourQueens 函数中的 Begin-End 段即可平台会对你编写的代码进行测试并将所有皇后的摆放方式打印出来。
预期输出 XQXX XXXQ QXXX XXQX XXQX QXXX XXXQ XQXX 开始你的任务吧祝你成功
def make(mark):标记皇后的位置例如mark[0] 2, 表示第1行皇后放在第3列的位置:param mark: 皇后的位置信息:return: 拼接好的结果#初始化数组r [[X for _ in range(len(mark))] for _ in range(len(mark))]#将每一行中皇后的位置用‘Q’代替for i in range(len(mark)):r[i][mark[i]] Q#枚举将原来散的元素连接成字符串for k, v in enumerate(r):r[k] .join(v)return rdef FourQueens(mark, cur, ret):深度优先搜索的方式求解四皇后问题:param mark:表示皇后的位置信息例如[0,1,3,2]表示棋盘的第1行第1列第2行第2列第3行第4列第4行第3列放置了皇后。例如[1, None, None, None]表示第1行第2列放置了皇后其他行没有放置皇后。初始值为[None,None,None,None]:param cur:表示当前准备在第几行放置皇后例如cur1时表示准备在第2行放置皇后。初始值为0:param ret:表示存放皇后摆放结果的列表类型为列表。初始值为[]:return:无if cur len(mark):#********* Begin *********## 如果当前行是最后一行记录一个解并返回结束此次搜索ret.append(make(mark))return#********* End *********##试探处理将当前行的皇后应该在的位置遍历每一列如果满足条件递归调用处理下一行for i in range(len(mark)):mark[cur], down i, Truefor j in range(cur):# 当想在当前位置放皇后会与其他皇后冲突时不放置皇后if mark[j] i or abs(i-mark[j]) cur - j:down Falsebreakif down:# 准备在下一行找能放置皇后的位置FourQueens(mark, cur1, ret)
