3、径(最优解)的条件,关键在于估价函数h(n)的选取。估价值h(n)<= n到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低。但能得到最优解。如果估价值>实际值, 搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。搜索中利用启发式信息,对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展,从而缩小搜索空间,更快的得到最优解,提高效率。 进一步考虑当前结点与目标结点的距离信息,令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和(不考虑中间路径),且对于目标状态有 h (
4、t ) = 0,对于17结点m和n (n 是m的子结点) 有h ( m ) – h ( n ) <= 1 = Cost ( m, n ) 满足单调限制条件。最重要的是应用了曼哈顿距离。同时可以根据深度和h值,在找最优解的时候,对超过目前最优解的地方进行剪枝,这可以导致搜索深度的急剧减少㈢主要功能利用A*算法求解八数码问题五、主要代码importcopydefinit(target):#初始化tlist,方便计算曼哈顿距离tlist=[0forainrange(9)]foriinrange(3):forjinrange(3):tl