用宽度、深度、a*搜索分别求解其搜索路径,并给出对应的open表和closed表-九游游戏app官方
第一张图是问题,第二张图是回答格式,拜托了拜托了
最新回答(1条回答)
由于没有具体指定问题,本文以八数码问题为例,给出用宽度、深度、a*搜索分别求解其搜索路径,并给出对应的open表和closed表的示例。八数码问题是一种经典的搜索问题,其目标是将3x3的拼图按照指定的顺序排列,并且只能通过交换数字来移动拼图,目标状态如下:1 2 3 4 5 6 7 8 其中数字0代表空格,可以与其它数字交换位置。我们以初始状态如下的拼图为例:8 7 6 5 4 3 2 1 0 三种搜索算法的具体流程如下。宽度优先搜索:1. 将初始状态s加入open表;2. 如果open表为空,则搜索失败;3. 否则,取出open表中的第一个状态,将其加入closed表,并展开该状态,生成其所有可能的子状态;4. 对于每个子状态,如果它等于目标状态t,则搜索成功,并输出路径;否则将其加入open表;5. 回到步骤2。宽度优先搜索的open表和closed表的示例如下:open表:| 状态 | 到达时间 | 父节点 | |----------|----------|---------|| 8 7 6 5 4 3 2 1 0 | t = 0 | null |closed表:| 状态 | 到达时间 | 父节点 ||----------|----------|----------|| 8 7 6 5 4 3 2 1 0 | t = 0 | null |深度优先搜索:1. 将初始状态s加入open表;2. 如果open表为空,则搜索失败;3. 否则,取出open表中的最后一个状态,将其加入closed表,并展开该状态,生成其所有可能的子状态;4. 对于每个子状态,如果它等于目标状态t,则搜索成功,并输出路径;否则将其加入open表;5. 回到步骤2。深度优先搜索的open表和closed表的示例如下:open表:| 状态 | 到达时间 | 父节点 | |----------|----------|---------|| 8 7 6 5 4 3 2 1 0 | t = 0 | null |closed表:| 状态 | 到达时间 | 父节点 ||----------|----------|----------|| 8 7 6 5 4 3 2 1 0 | t = 0 | null |a*搜索:1. 将初始状态s加入open表,其估价函数值f(s)=g(s) h(s),其中g(s)表示从初始状态到s的路径长度,h(s)表示从s到目标状态t的最小估价路径长度;2. 如果open表为空,则搜索失败;3. 否则,取出open表中f值最小的状态smin,将其加入closed表,并展开该状态,生成其所有可能的子状态;4. 对于每个子状态,如果它等于目标状态t,则搜索成功,并输出路径;否则计算其估价函数值f和实际路径长度g,并将其加入open表;5. 如果open表中已经存在某个状态s',且它到达的路径长度更短,则更新open表中该状态的估价函数值和父节点;6. 回到步骤2。a*搜索的open表和closed表的示例如下:open表:| 状态 | 到达时间 | g(s) | h(s) | f(s) | 父节点 | |----------|----------|-------|-------|-------|---------|| 8 7 6 5 4 3 2 1 0 | t = 0 | 0 | 17 | 17 | null |closed表:| 状态 | 到达时间 | g(s) | h(s) | f(s) | 父节点 ||----------|----------|-------|-------|-------|----------|| 8 7 6 5 4 3 2 1 0 | t = 0 | 0 | 17 | 17 | null |