启发式搜索算法（A*算法）_估计函数的估计值是不是由hx决定

作者：煮酒与君饮 | 2024-06-20 06:19:52

踩

估计函数的估计值是不是由hx决定

h(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 3 1 2 3

1 8 ------> 8 4

7 4 5 7 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 题解:http://blog.csdn.net/xiaosshhaa/article/details/54315981

poj :1376 1324 1084 2449 1475

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/738876