八数码问题(A*&&双向BFS)---zoj_1217

题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=217

????? 首先说一下八数码问题的可解性。

?????? 1.互换2个非零位置，状态的逆序奇偶性将保持不变。

?????? 2.互换0和另一个非零位置，状态的逆序奇偶性将发生颠倒。

?????? 3.因此，如果目标状态和起始状态的逆序奇偶性相同，问题可解，否则不可解。所以对于八数码问题的一个目标状态有9!/2种可解状态

?????? 逆序奇偶性可以这样来求，将状态转化了数列，然后去掉X位，然后对于每一位，计算在它之前小于它的个数，每一位对应的值之和就是逆序奇偶数。

????? A*算法具体不多说了，它的精髓在于f(n)=g(n)+h(n),中估值函数h(n)的设计。值的注意的是：

????? 如果估价值h(n)<= n（到目标节点的实际步长），这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

　　如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

???? 因此在实际使用的时候应该更具需要来设计h(n)

???? 在zoj_1217中，为了不TLE，选择h(n)=20*dis(欧几里德距离)，但是得不到最优解

zoj_1217:

?双向BFS：
?
?
?