南京网站设计平台,青岛网站开发企业,广州注册监理公司,免费虚拟空间网站一、双向广搜
双向广搜就是从起点和终点同时往中间搜的一个算法。
注意事项#xff1a;
在搜索过程中#xff0c;同一层次下的顺序应该为#xff1a;搜完一边所有的当前深度的子节点#xff0c;在搜索另一边。
队列使用
#xff08;1#xff09;合用…一、双向广搜
双向广搜就是从起点和终点同时往中间搜的一个算法。
注意事项
在搜索过程中同一层次下的顺序应该为搜完一边所有的当前深度的子节点在搜索另一边。
队列使用
1合用一个队列
2用两个队列
判断条件
若两边都搜到了某一个状态这个状态就是可行解具体情况根据具体题目加以分析。
二、A*
A*的特点就是用到了一个估价函数来剪枝。
A*是一种用优先队列的方式实现的算法不过A *算法的优先队列是判断当前节点已经行走的步数乐观估计函数较少者优先。
A*算法的模板与BFS差不多这个算法并不是去盲目的搜索而是将最有可能成为解或最优解的状态优先搜索降低了时间复杂度。
例题8数码1
分析
运用A的思想构造估价函数在这里我们可以将当前状态与目标状态的不同的元素个数来最为估价函数。但是这里我们必须把0加上
若当前状态为
1 0 3
4 2 5
6 7 8
目标状态为
1 2 3
4 7 5
6 0 8
这样若按照上述的估价函数算差别为6但其实2步就能到达。这就导致我们会剪掉一些正确的解。
正确的做法是加上0进行比较
代码
AC代码
三、IDDFS
IDDFS称为迭代加深算法关键就在于每次限制了DFS的最大深度。
好处 1.可以很好的避免DFS搜索到“无底洞”的情况。
2.虽然一层一层的加深很像广搜但是并没有用队列存储降低了空间复杂度因为每一次迭代都是从根节点开始搜这样虽然增加了一点时间但是根据测试并无大碍。
3.相比于DFS不能一次性求到最优解这个算法可以保证正确性。
四、IDA*
IDA*是IDDFS和A *的结合从代码上看类似于广搜。
IDDFS每次限制深度可以保证求到的解的最优性而A*用来剪枝降低时间复杂度。
例题
8数码2
这道题A*算法50分WAIDDSD67分TLE.
这道题加强了数据就需要用到逆序对优化了康托展开可以实现
1.向左向右移逆序对的个数不会发生变化。
2.向上向下移逆序对的个数两个两个的变。
题目给出的目标状态逆序对个数为0所以如果起始的逆序对个数模二余一则无解反之有解。
代码
AC代码
