最佳路径的图搜索（一）
不论采用深度优先搜索还是采用宽度优先搜索，只要在得到解之后仍继续进行搜索，把所有可能的解都得到后，就可以从中选出最佳路径的解。本节介绍利用启发式信息的图搜索方法。
1、A算法与A*算法（下面n为给的定结点）
f(n):表示估价函数。我们希望把最有希望的结点排在前面。为此对每个结点定义一个实值函数来描述“希望”的大小，这个函数称为估价函数 。
f*(n): 从初始结点通过结点n到目标结点集合的最小耗散路径的耗散值。估价
函数f(n)则为f*(n)的估计值。
f*(n)=g*(n)+h*(n)
其中g*(n)：是从初始结点到结点n的最小耗散路径的耗散值
h*(n)：是由结点n到目标集合的最小耗散路径的耗散值
同样 f(n)=g(n)+h(n)
其中g(n)是g*(n)的一个估计，h(n)是h*(n)的一个估计
A算法：如果图搜索算法中利用估价函数f(n)=g(n)+h(n)为OPEN表中的结点排序。
A*算法：h(n)是h*(n)的一个下界(即对所有的n，h(n)≤h*(n))，则称算法为A*算法。
2、A*算法的可采纳性
对于一个搜索算法，只要从初始结点到一个目标结点的路径存在，就总能到达一条最佳路径，我们就说这个算法是可采纳的。
定理1：隐含图为有限时，如果从初始结点到目标结点存在一条路径多则算法一定成功结束。
证明
定理2：隐含图为无限时，如果从初始结点s到一个目标结点存在一条路径，则A*算法必然会结束。
根据引理2-1和引理2-2，可以立即得到此定理。
定理3: A*算法是可采纳的，即如果从初始点到一个目标结点存在一条路径，则A*算法必然找到最佳路径结束。
证明
下一讲
返回主页
|