![](https://csdnimg.cn/release/download_crawler_static/85845530/bg1.jpg)
1.启发式搜索算法 A
启发式搜索算法 A,一般简称为 A 算法,是一种典型的启
发式搜索算法。其基本思想是:定义一个评价函数 f,对当前的
搜索状态进行评估,找出一个最有希望的节点来扩展。
评价函数的形式如下:
f(n)=g(n)+h(n)
其中 n 是被评价的节点。
f(n)、g(n)和 h(n)各自表述什么含义呢?我们先来定义下
面几个函数的含义,它们与 f(n)、g(n)和 h(n)的差别是
都带有一个"*"号。
g*(n):表示从初始节点 s 到节点 n 的最短路径的耗散值;
h*(n):表示从节点 n 到目标节点 g 的最短路径的耗散值;
f*(n)=g*(n)+h*(n):表示从初始节点 s 经过节点 n 到目标节点 g
的最短路径的耗散值。
而 f(n)、g(n)和 h(n)则分别表示是对 f*(n)、g*
(n)和 h*(n)三个函数值的的估计值。是一种预测。A 算法
就是利用这种预测,来达到有效搜索的目的的。它每次按照 f(n)
值的大小对 OPEN 表中的元素进行排序,f 值小的节点放在前面,
而 f 值大的节点则被放在 OPEN 表的后面,这样每次扩展节点时,
都是选择当前 f 值最小的节点来优先扩展。