首页 > 代码库 > A* \IDA* 分析总结
A* \IDA* 分析总结
对于空格(0)的左移/右移操作,对应序列不变(逆序数也就不变)
对于空格(0)的上移/下移操作,相当于序列的某个数字前移/后移两位,该序列的逆序数奇偶性不变。
所以求初始状态与目标状态的逆序数可作出判断
例中前者为奇,后者为偶,因此无解
利用奇偶性判断所给出的初始状态有无解.
判别方法是:
以数组为一维的举例子.
将八数码的一个结点表示成一个数组a[9],空格用0表示,设临时函数p(x)定义为:x数所在位置前面的数比x小的数的个数,
其中0空格不算在之内,那设目标状态为b[9],那r=sigma(p(x)) sigma()表示取所有的x:1-8并求和,
那对于初始状态a[9],t=sigma(p(x)),如果r和t同为奇数或者同为偶数,那么该状态有解,否则无解。
考虑到四种移动方法对sigma(p(x))的影响,左移和右移是不会影响它的值的,
更不会影响奇偶性,如果是上移或者下移就会影响:
上移:一次上移会使一个元素向前跳两个数字的位置,设这两个数字为a1,a2,
不妨设a1<a2,移的这个数字设为a0,那无非只有以下三次情况:
1,a0<a1<a2,考虑它们三者的p(x)值,p(a0)不变,p(a1)++,p(a2)++,总体增加了2
2,a1<a0<a2,p(a0)--,p(a1)不变,p(a2)++,总体不变
3,a1<a2<a0,p(a0)-=2,p(a1),p(a2)不变,总体减小了2
综合起来的结论就是不会影响sigma(p(x))的奇偶性。
A* \IDA* 分析总结
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。