启发式搜索算法（A*算法）

A算发：在bfs算法中，若对每个状态n都设定估价函数f(n)=g(n)+h(n)，并且每次从开启列表中选节点

进行扩展时，都选取f值最小的节点，则该搜索算法为启发式搜索算法，又称A算法。

g(n):从起始状态到当前状态n的代价。

A算法的例子——八数码

2 6 3 1 2 3 1 8 -----> 8 4 7 4 5 7 6 5定义估价函数f(n)=g(n)+h(n)初始节点 g(n):为从初始节点到当前节点的步数。 h(n):为当前节点“不在位”的方块数。h计算举例

2 6 31 2 3 1 8 ------> 8 4 7 4 57 6 5 2,6,1,8,4,5 都不在位，因此h=6

A*算法A算法中的估价函数若选取不当，则可能找不到解，或找到的解也不是最优。因此，需要对估价函数做一些限制，使算发确保找到最优解（步数，即状态转移次数最少的解）。A*算法即为估价函数做了特定限制，且确保找到最优解的A算法。A* 算法 f*(n)=g*(n)+h*(n)f*(n)：从初始节点s0出发，经过节点n到达目标节点的最小步数（真实值）g*(n):从s0出发，到达n的最少步数（真实值）h*(n):从n出发，到达目标节点的最少步数（真实值）估价函数f(n)则是f*(n)的估计值

A*算法 f(n)=g(n)+h(n),且满足以下限制： g(n)是从s0到n的真实步数（未必是最优的），因此g(n)>0且g(n)>=g*(n) h(n)是从n到目标的估计步数，估计总是过于乐观的 即h(n)<=h*(n) 且h(n)相容，则A算法就转变为A*算法。

A*算法 h(n)的相容：如果h函数对任意状态s1和s2还满足：h(s1)<=h(s2)+c(s1,s2) C(s1,s2)是s1转移到s2的步数，则称h是相容的。h相容能确保随着一步步往前走，f递增，这样A*能高效找到最优解。 h相容=> g(s1)+h(s1)<=g(s1)+h(s2)+c(s1,s2)=g(s2)+h(s2)=>f(s1)<=f(s2) 即f是递增的。

A*算法的搜索效率很大程度上取决于估价函数h(n),一般说来，在满足h(n)<=h*(n)的前提下，h(n)的值越大越好 八数码问题： 方案一：h(n)为不在位的数字个数 方案二：h(n)为不在位的数字到其该呆的位置的曼哈顿距离和 后者优于前者 A*算法解决八数码问题 hdu oj 1043 题解:/xiaosshhaa/article/details/54315981

poj :1376 1324 1084 2449 1475