启发式搜索A-Star.ppt

启发式搜索A-Star静态路网求最短路的有效方法Made by Lighthawk什么是启发式搜索???启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。与盲目搜索对比一下的话~~就是搜索具有了目的性!单向bfs、双向bfs和A*的比较:时空比较时间空间单向BFSO(K ^ d)O(K ^ d)双向BFSO(K ^ (d/2))O(K ^ (d/2))A*O((K'^ d) *logM) O(K'^ d) 初识A*A*算法的实质是一个启发函数 f (N),用来计算结点 N“前途如何”。通常把f (N) 设计成估计“一条经过N的路径”, 进而写成f (N) = g(N) +h(N) ;g(N) --- 由起点搜到 N 点时的最小步数(相当于已知条件);h(N) --- 对N到终点的接近程度的估计;强调!h(N)与搜索过程无关,仅仅是状态的函数。当然了,要满足某些条件。估值函数h(N)应该具有什么性质???可接纳性0 <= h(N) <= h*(N)以八数码为例: f1(N) = N不在目标位置的滑块数目; f2(N) = N所有数字到终点的Manhattan距离; f3(N) = N的逆序数对。只有前两个可接纳A*算法定义f(N) = g(N) + h(N) , 其中g(N)是从初始状态到N的最优路径代价,h(N)是一个可接纳的启发函数,所有边权为c(N,N') > ε> 0 , 如果把搜索边界按照f(N)从小到大排序,则修改后的搜索算法称为A*算法。结论一:如果重复结点全部保存,则A*是完全的,也是最优的。结论二:若启发函数h是单调的,则每扩展一个结点N时,就已经找到了起点到它的最优路径。结论三:设启发函数h2比h1更精确,采用h1的A*算法称为A1*,采用h2的A*算法称为A2*,则被A2*扩展的非目标结点一定会被A1*扩展。详细证明--- lrj内功心法 *算法结论一:如果重复结点全部保存,则A*是完全的,也是最优的。完全--- 如果问题有解,搜索边界上一定存在点 X,使得从