网站开发z亿玛酷1流量订制,如何避免网站模板侵权,wordpress4.9漏洞利用,网站魔板大全任务描述
本关任务#xff1a;八数码问题是在一个33的棋盘上有1−8位数字随机分布#xff0c;以及一个空格#xff0c;与空格相连的棋子可以滑动到空格中#xff0c;问题的解是通过空格滑动#xff0c;使得棋盘转化为目标状态#xff0c;如下图所示。
为了简化问题的输…任务描述
本关任务八数码问题是在一个3×3的棋盘上有1−8位数字随机分布以及一个空格与空格相连的棋子可以滑动到空格中问题的解是通过空格滑动使得棋盘转化为目标状态如下图所示。
为了简化问题的输入首先将空格用数字0表示然后将3×3的棋盘用9位长的字符串表示则上图的初始状态为724506831目标状态为012345678本关卡所有目标状态均为012345678也保证初始状态到目标状态有解。
对于上图的初始状态将数字2移动到空格称之为u操作空格上移将数字3移动到空格称之为d操作空格下移将数字5移动到空格称之为l操作空格左移将数字6移动到空格称之为r操作空格右移则一个合法移动路径为lurdrdllurrdllurrulldrrull。 相关知识
为了完成本关任务你需要掌握1.评估函数2.贪婪最佳优先搜索3.A*搜索缩小总评估代价4.求解思路。
评估函数
在有信息搜索 Informed Search 策略中常使用的是最佳优先搜索 Best First Search 它的结点扩展是基于评估函数值f(n)选择的。评估函数被看做是代价估计因此代价最低的结点最先被选择扩展。
对f(n)的选择决定了搜索策略大部分的最佳优先搜索算法的f(n)由启发式函数h(n)构成
h(n)结点n到目标的最小代价路径的代价估计值
贪婪最佳优先搜索
贪婪最佳优先搜索 Greedy Best-First Search 试图扩展距离目标结点最近的结点原因是这种策略可能可以非常快的找到解因此贪婪最佳优先搜索只使用启发式信息即f(n)h(n)。
A*搜索缩小总评估代价
A* 搜索A 星搜索是最广为人知的最佳优先搜索它对结点n的代价评估结合了g(n)即到达此结点n已经花费的路径代价和h(n)即从该结点n到目标结点所花代价。
f(n)g(n)h(n)
由于g(n)是从开始结点到结点n的路径代价而h(n)是从结点n到目标结点的最小路径代价的估计值因此
f(n)经过结点n的最小代价解的估计代价
所以要寻找最小代价的解首先扩展的是g(n)h(n)值最小的结点。可以发现A* 搜索算法与一致代价搜索算法类似区别是 A* 搜索算法使用g(n)h(n)而不是g(n)。
求解思路
该问题是将与空格相连的数字移动到空格的位置上也就相当于将空格移动到与之相连的位置因此以空格为当前结点扩展结点可能为上下左右四个相连的位置若使用一般的搜索算法可能陷入无限搜索中永远搜不到目标解而 A* 搜索算法则能非常好的将搜索过程导向求解目标。
问题给的是字符串数据724506831可以还原成如下形式 那么空格的l移动操作即为下标4和下标3上所对应的数字的交换分别为0和5交换后的新的状态为 以此类推空格的lrud各操作均可用以上的交换过程表达。
A* 算法的重中之重就是启发式函数h(n)的设计不同的设计方法可能产生不同的求解路径。在这里可以选择欧氏距离作为评估函数值除0之外各个数字在当前状态的下标与目标状态的下标的绝对值之和。例如当前状态为123456780目标状态为012345678数字1的下标分别为0和1数字2的下标分别为1和2...数字8的下标分别为7和8则当前状态与目标状态的评估值为h(n)abs(1−2)abs(2−3)⋯abs(7−8)8。
编程要求
本关的编程任务是补全右侧代码片段 salvePuzzle 、 calcDistH 和 moveMap 中 Begin 至 End 中间的代码具体要求如下 在 salvePuzzle 中根据输入参数init初始状态如724506831和targ目标状态均为012345678实现 A* 搜索算法返回八数码问题的移动路径如上图的移动路径lurdrdllurrdllurrulldrrull。 在 calcDistH 中计算当前状态参数srcmap如724506831到目标状态参数destmap如012345678的启发式函数值h(n)并返回h(n)。 在 moveMap 中实现行动转换并返回下一个状态例如当前状态为参数curmap724506831当前 8 数码状态curmap中空格 0 的位置索引i4移动空格到位置j3则返回的新状态为newmap724056831。
测试说明
平台将自动编译补全后的代码并生成若干组测试数据接着测试程序会调用上述函数并判断函数返回的路径是否为合法解若是则输出 Accepted 表示程序正确否则程序错误。
以下是平台的测试样例
测试输入 724506831
预期输出 Accepted
代码
# -*- coding:utf-8 -*-class Solution:def salvePuzzle(self, init, targ): 求解8数码问题参数init - 初始状态 例如123046758targ - 目标状态 均为012345678返回值clf - 由udlr组成的移动路径字符串#请在这里补充代码完成本关任务#********** Begin **********#clf # 初始化移动路径字符串state_open [] # 初始化开放列表state_close [] # 初始化关闭列表state_open.append([init,99,test,init,0]) # 将初始状态加入开放列表fn 2 # 初始化启发式函数的权重flag 1 # 初始化标志位while True:cur_state state_open.pop(0) # 取出开放列表中的第一个状态state_close.append(cur_state) # 将当前状态加入关闭列表if cur_state[0] targ: # 如果当前状态等于目标状态while 1:clf cur_state[2] # 将当前状态的移动方向加入移动路径字符串if cur_state[3] init: # 如果当前状态的父状态等于初始状态breakfor id,item in enumerate(state_close[1:]): # 遍历关闭列表中的状态if item[0] cur_state[3]: # 如果找到父状态cur_state item # 更新当前状态为父状态return clf[::-1] # 返回逆序的移动路径字符串i cur_state[0].find(0) # 找到空格0的位置索引flag 1 # 重置标志位if str(i) not in 036: # 如果空格0不在第一行、第三行和第六行tmp_map self.moveMap(cur_state[0],i,i-1) # 尝试将空格0向左移动if tmp_map not in [tmp[0] for tmp in state_close]: # 如果新状态不在关闭列表中for id,item in enumerate(state_open): # 遍历开放列表中的状态if item[0] tmp_map: # 如果找到新状态if item[1] item[4] self.calcDistH(tmp_map,targ) cur_state[4] fn: # 如果新状态的代价大于当前状态的代价state_open[id] [tmp_map,self.calcDistH(tmp_map,targ),l,cur_state[0],cur_state[4]fn] # 更新开放列表中的状态flag 0 # 设置标志位为0breakbreakif flag 1: # 如果标志位为1state_open.append([tmp_map,self.calcDistH(tmp_map,targ),l,cur_state[0],cur_state[4]fn]) # 将新状态加入开放列表flag 1 # 重置标志位if str(i) not in 258: # 如果空格0不在第二行、第五行和第八行tmp_map self.moveMap(cur_state[0],i,i1) # 尝试将空格0向右移动if tmp_map not in [tmp[0] for tmp in state_close]: # 如果新状态不在关闭列表中for id,item in enumerate(state_open): # 遍历开放列表中的状态if item[0] tmp_map: # 如果找到新状态if item[1] item[4] self.calcDistH(tmp_map,targ) cur_state[4] fn: # 如果新状态的代价大于当前状态的代价state_open[id] [tmp_map,self.calcDistH(tmp_map,targ),r,cur_state[0],cur_state[4]fn] # 更新开放列表中的状态flag 0 # 设置标志位为0breakbreakif flag 1: # 如果标志位为1state_open.append([tmp_map,self.calcDistH(tmp_map,targ),r,cur_state[0],cur_state[4]fn]) # 将新状态加入开放列表flag 1 # 重置标志位if i-30: # 如果空格0不在最左边的三列tmp_map self.moveMap(cur_state[0],i,i-3) # 尝试将空格0向上移动if tmp_map not in [tmp[0] for tmp in state_close]: # 如果新状态不在关闭列表中for id,item in enumerate(state_open): # 遍历开放列表中的状态if item[0] tmp_map: # 如果找到新状态if item[1] item[4] self.calcDistH(tmp_map,targ) cur_state[4] fn: # 如果新状态的代价大于当前状态的代价state_open[id] [tmp_map,self.calcDistH(tmp_map,targ),u,cur_state[0],cur_state[4]fn] # 更新开放列表中的状态flag 0 # 设置标志位为0breakbreakif flag 1: # 如果标志位为1state_open.append([tmp_map,self.calcDistH(tmp_map,targ),u,cur_state[0],cur_state[4]fn]) # 将新状态加入开放列表flag 1 # 重置标志位if i38: # 如果空格0不在最右边的三列tmp_map self.moveMap(cur_state[0],i,i3) # 尝试将空格0向下移动if tmp_map not in [tmp[0] for tmp in state_close]: # 如果新状态不在关闭列表中for id,item in enumerate(state_open): # 遍历开放列表中的状态if item[0] tmp_map: # 如果找到新状态if item[1] item[4] self.calcDistH(tmp_map,targ) cur_state[4] fn: # 如果新状态的代价大于当前状态的代价state_open[id] [tmp_map,self.calcDistH(tmp_map,targ),d,cur_state[0],cur_state[4]fn] # 更新开放列表中的状态flag 0 # 设置标志位为0breakbreakif flag 1: # 如果标志位为1state_open.append([tmp_map,self.calcDistH(tmp_map,targ),d,cur_state[0],cur_state[4]fn]) # 将新状态加入开放列表state_open.sort(keylambda x : x[1] x[4]) # 根据代价对开放列表进行排序#********** End **********#def calcDistH(self, src_map, dest_map):启发式函数h(n)参数src_map - 当前8数码状态dest_map - 目标8数码状态返回值clf - 当前状态到目标状态的启发式函数值#请在这里补充代码完成本关任务#********** Begin **********#if src_map is None or dest_map is None:return 0 clf 0for i in range(9):clf abs(int(src_map[i])-int(dest_map[i]))return clf#********** End **********#def moveMap(self, cur_map, i, j):状态转换交换位置i和j参数cur_map - 当前8数码状态i - 当前8数码状态中空格0的位置索引j - 将空格0的位置i移动到位置j位置j移动到位置i返回值clf - 新的8数码状态#请在这里补充代码完成本关任务#********** Begin **********#if ij:i,jj,itmp_i cur_map[i]tmp_j cur_map[j]tmp_map cur_map[:i]tmp_jcur_map[i1:j]tmp_icur_map[j1:]return tmp_map#********** End **********#
