【高级搜索】双向广搜，A*,IDDFS，IDA *算法总结 (terse版）
一、双向广搜
双向广搜就是从起点和终点同时往中间搜的一个算法。
注意事项：
在搜索过程中，同一层次下的顺序应该为：搜完一边所有的当前深度的子节点，在搜索另一边。
队列使用
（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分WA，IDDSD67分TLE.
这道题加强了数据，就需要用到逆序对优化了（康托展开可以实现）
1.向左向右移，逆序对的个数不会发生变化。
2.向上向下移，逆序对的个数两个两个的变。
题目给出的目标状态逆序对个数为0，所以如果起始的逆序对个数模二余一，则无解，反之有解。
代码：
AC代码