您的当前位置是：第三章 确定性推理>>学习内容>>知识点三

三、A*算法

A*算法是一种启发式搜索算法，它利用包含问题启发式信息的估计函数对OPEN 中的节点进行排序，使搜索方向朝着最有可能找到目标并产生最优解的方向。

值得注意的是，启发式信息来自具体的问题。因此，A*算法估价函数的设计需特殊问题特殊对待。

A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。

1．几个记号

令k（n_i，n_j）表示任意两个节点n_i和n_j之间最小代价路径的实际代价（对于两节点间没有通路的节点，函数k没有定义）。

于是，从节点n到某个具体的目标节点t_i，某一条最小代价路径的代价可由k（n，t_i）给出。令h*（n）表示整个目标节点集合｛t_i｝上所有k（n，t_i）中最小的一个，因此，h*（n）就是从n到目标节点最小代价路径的代价，而且从n到目标节点能够获得h*（n）的任一路径就是一条从n到某个目标节点的最佳路径（对于任何不能到达目标节点的节点n，函数h*没有定义）。

2．估价函数的定义

定义g*为g*（n）=k（S，n）

定义函数f*，使得在任一节点n上其函数值f*（n）就是从节点S到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和，即

f*（n）=g*（n）+h*（n）

希望估价函数f是f*的一个估计，此估计可由下式给出：

f（n）=g（n）+h（n）

其中：g是g*的估计；h是h*的估计。对于g（n）来说，一个明显的选择就是搜索树中从S到n这段路径的代价，这一代价可以由从n到S寻找指针时，把所遇到的各段弧线的代价加起来给出（这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径）。这个定义包含了g（n）≥g*（n）。h*（n）的估计h（n）依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数W（n）所用的那种信息相似。把h叫做启发函数。

3．A*算法定义

定义1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f（x）=g（x）+h（x）进行的，则称该过程为A算法。

定义2 在A算法中，如果对所有的x存在h（x）≤h*（x），则称h（x）为h*（x）的下界，它表示某种偏于保守的估计。

1  2  3  4  5