A算法和A*算法区别

A算法由f(n)=g(n)+h(n)俩个因素决定，g(n)是这一步的代价函数,h(n)是这一步的预估函数； 对于A算法来说，评判函数也是f(n)=g∗(n)+h∗(n)这个，只不过加了约束条件，g∗(n)>0，h∗(n)<=任意h(n)；
以上只不过是定义，对于一个实例来说，h(n)由很多种，h(n)只是估值函数的一个集合，有各种方法h1(n)h2(n)h3(n)…，取其中任意一个方法带入上述公式，组成评判函数，都是A算法的实现，现在取从集合中一个函数h∗(n)，使得它比集合中任意的函数都优秀，这样的算法叫A算法
[

](https://blog.csdn.net/znr1995/article/details/62235481)

如果启发函数h(n)满足单调限制条件，则 h(n)是可采纳的，即h(n)≤h*(n)成立。

image.png

判定状态S1是否可以到达状态S2

对其中任一数字n（1-8），第一行开始，每行从左往右顺序，计算（计数）n之前（或之后）所有小于 n的数字的个数，设为f(n)，对所有f(n)求和。若s1和s2求和结果均为奇数或均为偶数，则可达，否则不可达。

lis1: s1 state
lis2: s2 state
f(n): 数字n前面比n小的数字的个数
for i in range(3):
for j in range(3):
sum1 = sum(f(lis1[i][j])
sum2 = sum(f(lis2[i][j])
if (sum1 + sum2)/2==0:
可达
else:
不可达