算法研究系列：精选24个经典的算法一、A*搜索算法 -July/编写=博主说明：1、此经典算法研究系列，第一、二篇文章写的不够好之处，还望见谅。2、本经典算法研究系列，系我参考资料，一篇一篇原创所作，转载必须注明作者本人July及出处。3、本经典算法研究系列，会永久更新，希望，尽我所能，阐述尽可能多的世界经典算法。欢迎，各位，与我一同学习探讨，交流研究。有误之处，不吝指正。- 一、A* 搜寻算法1968年，的一篇论文，“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968”。从此，一种精巧、高效的算法-A*算法横空出世了，并在相关领域得到了广泛的应用。DFS和BFS在展开子结点时均属于盲目型搜索，也就是说，它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中，均需要试探完整个解集空间, 显然，只能适用于问题规模不大的搜索问题中。 那么，作为启发式算法中的A*算法，又比它们高效在哪里呢？ 首先要来谈一下什么是启发式算法。所谓启发式搜索，与DFS和BFS这类盲目型搜索最大的不同，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数来进行选择，选择代价最少的结点作为下一步搜索结点而跳转其上（遇到有一个以上代价最少的结点，不妨选距离当前搜索点最近一次展开的搜索点进行下一步搜索）。一个经过仔细设计的启发函数，往往在很快的时间内就可得到一个搜索问题的最优解，对于NP问题，亦可在多项式时间内得到一个较优解。 是的，关键就是如何设计这个启发函数。 A*算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。而A*算法最为核心的部分，就在于它的一个估值函数的设计上： f(n)=g(n)+h(n) 其中f(n)是每个可能试探点的估值，它有两部分组成：一部分为g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。另一部分，即h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值，h(n)设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。 一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是：1)搜索树上存在着从起始点到终了点的最优路径。2)问题域是有限的。3）所有结点的子结点的搜索代价值0。4）h(n)=h*(n) （h*(n)为实际问题的代价值）。 当此四个条件都满足时，一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法，并一定能找到最优解。（1P89给出了相关的证明） 对于一个搜索问题，显然，条件1,2,3都是很容易满足的，而条件4)： h(n)=h*(n)是需要精心设计的，由于h*(n)显然是无法知道的，所以，一个满足条件4）的启发策略h(n)就来的难能可贵了。不过，对于图的最优路径搜索和八数码问题，有些相关策略h(n)不仅很好理解，而且已经在理论上证明是满足条件4)的，从而为这个算法的推广起到了决定性的作用。不过h(n)距离h*(n)的呈度不能过大，否则h(n)就没有过强的区分能力，算法效率并不会很高。对一个好的h(n)的评价是：h(n)在h*(n)的下界之下，并且尽量接近h*(n). 二、继续深入之前，再来看下维基百科对本A*搜索算法的解释：A*搜寻算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。 在此算法中，g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离。因此，A*算法的公式为：f(n)=g(n)+h(n)。这个公式遵循以下特性：如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法 如果h(n)=n到目标的实际距离，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低。 三、ok，来看下，此A*搜寻算法的算法实现：closedset := the empty set /已经被估算的节点集合 openset := set containing the initial node /将要被估算的节点集合 g_scorestart := 0 /g(n) h_scorestart := heuristic_estimate_of_distance(start, goal) /f(n) f_scorestart := h_scorestart while openset is not empty x := the node in openset having the lowest f_score value if x = goal return reconstruct_path(came_from,goal) remove x from openset add x to closedset for each y in neighbor_nodes(x) if y in closedset continue tentative_g_score := g_scorex + dist_between(x,y) if y not in openset add y to openset tentative_is_better := true else if tentative_g_score V1，V2，V3，V4，V5的路径之和。即好比一个人从V0点出发，要达到V1.V5，五个点。图中达到过的点，可以作为到达其它点的连通桥。下面的问题，即是求此最短路径。/是的，图片是引用rickone 的。 与结点写在一起的数值表示那个结点的价值f(n)，当OPEN表为空时CLOSE表中，即求得了从V0到其它所有结点的最短路径。考虑到算法性能，外循环中每次从OPEN表取一个元素，共取了n次（共n个结点），每次展开一个结点的后续结点时，需O(n)次，同时再对OPEN表做一次排序，OPEN表大小是O(n)量级的，若用快排就是O(nlogn)，乘以外循环总的复杂度是O(n2logn)，如果每次不是对OPEN表进行排序，因为总是不断地有新的结点添加进来，所以不用进行排序，而是每次从OPEN表中求一个最小的，那只需要O(n)的复杂度，所以总的复杂度为O(n*n)，这相当于Dijkstra算法。 在这个算法基础之上稍加改进就是Dijkstra算法。OPEN表中常出现这样的表项：(Vk,fk1)(Vk,fk2)(Vk,fk3)，而从算法上看，只有fk最小的一个才有用，于是可以将它们合并，整个OPEN表表示当前的从V0到其它各点的最短路径，定长为n，且初始时为V0可直接到达的权值（不能到达为INFINITY），于是就成了Dijkstra算法。本文完。 本文来自CSDN博客，转载请标明出处：http:/blog.csdn.net/v_JULY_v/archive/2010/12/23/6093380.aspx算法系列：精选24个经典的算法二、Dijkstra 算法 -July编写 =本文主要参考：算法导论 第二版、维基百科。-