A-star和第k短路和次小生成树和Yen和MPS寻路算法.doc

A*算法A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为： f(n)=g(n)+h(n), 其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。估价值与实际值越接近，估价函数取得就越好。例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt(dx-nx)*(dx-nx)+(dy-ny)*(dy-ny)；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。conditions of heuristicOptimistic (must be less than or equal to the real cost)As close to the real cost as possible主要搜索过程：创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,-算X的估价值-While(OPEN!=NULL)从OPEN表中取估价值f最小的节点n;if(n节点=目标节点) break;elseif(X in OPEN) 比较两个X的估价值f /注意是同一个节点的两个不同路径的估价值if( X的估价值小于OPEN表的估价值 )更新OPEN表中的估价值; /取最小路径的估价值if(X in CLOSE) 比较两个X的估价值 /注意是同一个节点的两个不同路径的估价值if( X的估价值小于CLOSE表的估价值 )更新CLOSE表中的估价值; 把X节点放入OPEN /取最小路径的估价值if(X not in both)求X的估价值;并将X插入OPEN表中; /还没有排序将n节点插入CLOSE表中;按照估价值将OPEN表中的节点排序; /实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：f(n) = g(n) + h(n) 这里，f(n)是估价函数，g(n)是起点到终点的最短路径值，h(n)是n到目标的最断路经的启发值。由于这个f(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g(n)，但 g(n)=g(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h(n)，但h(n)=h(n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。哈。你懂了吗？肯定没懂。接着看。举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的A*算法。再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。次短路径次短路径可以看作是k短路径问题的一种特殊情况，求k短路径有Yen算法等较为复杂的方法，对于次短路径，可以有更为简易的方法。下面介绍一种求两个顶点之间次短路径的解法。我们要对一个有向赋权图(无向图每条边可以看作两条相反的有向边)的顶点S到T之间求次短路径，首先应求出S的单源最短路径。遍历有向图，标记出可以在最短路径上的边，加入集合K。然后枚举删除集合K中每条边，求从S到T的最短路径，记录每次求出的路径长度值，其最小值就是次短路径的长度。在这里我们以为次短路径长度可以等于最短路径长度，如果想等，也可以看作是从S到T有不止一条最短路径。如果我们规定求从S到T大于最短路径长度的次短路径，则答案就是每次删边后大于原最短路径的S到T的最短路径长度的最小值。用Dijkstra+堆求单源最短路径，则每次求最短路径时间复杂度为O(N*log(N+M) + M)，所以总的时间复杂度为O(N*M*log(N+M) + M2)。该估计是较为悲观的，因为一般来说，在最短路径上的边的条数要远远小于M，所以实际效果要比预想的好。次小生成树类比上述次短路径求法，很容易想到一个“枚举删除最小生成树上的每条边，再求最小生成树”的直观解法。如果用Prim+堆，每次最小生成树时间复杂度为O(N*log(N+M) + M)，枚举删除有O(N)条边，时间复杂度就是O(N2*log(N+M) + N*M)，当图很稠密时，接近O(N3)。这种方法简易直观，但我们有一个更简单，而且效率更高的O(N2+M)的解法，下面介绍这种方法。首先求出原图最小生成树，记录权值之和为MinST。枚举添加每条不在最小生成树上的边(u,v)，加上以后一定会形成一个环。找到环上权值第二大的边(即除了(u,v)以外的权值最大的边)，把它删掉，计算当前生成树的权值之和。取所有枚举修改的生成树权值之和的最小值，就是次小生成树。具体实现时，更简单的方法是从每个节点i遍历整个最小生成树，定义Fj为从i到j的路径上最大边的权值。遍历图求出Fj的值，然后对于添加每条不在最小生成树中的边(i,j)，新的生成树权值之和就是MinST + w(i,j) - Fj，记录其最小值，则为次小生成树。该算法的时间复杂度为O(N2 + M)。由于只用求一次最小生成树，可以用最简单的Prim，时间复杂度为O(N2)。算法的瓶颈不在求最小生成树，而在O(N2+M)的枚举加边修改，所以用更好的最小生成树算法是没有必要的。次短路径与次小生成树的例题HAOI 2005 路由选择问题直接求次短路径。pku 3255 Roadblocks稍微特殊的次短路径，允许边重复走。Ural 1416 Confidential求次小生成树的问题、pku 1679 The Unique MST判断最小生成树是否唯一。对于 前K短路径问题 和 A*算法 的一些小小总结我很懒的 2007-12-08 10:37 首先，为了说话方便，列出一些术语： 在启发式搜索中，对于每个状态 x，启发函数 f(x) 通常是这样的形式：f(x) = g(x) + h(x) 其中 g(x) 是从初始状态走到 x 所花的代价；h(x) 是从 x 走到目标状态所需要的代价的估计值。 相对于 h(x)，还有一个概念叫 h*(x)，表示从 x 走到目标状态所需要的实际最小代价（当然，这个值有时我们是事先无法知道的）。 如果在你的启发函数里，能保证 h(x) = h*(x)，也就是说，你不能高估了从 x 走到目标状态所需要的代价，那就可以说这个搜索是 A* 算法（这里的“*”，英文就读作 star）。 A* 算法的特点是，如果存在从初始状态走到目标状态的最小代价的解，那么用 A* 算法搜索时，第一个找到的解就一定是最小代价的。这就是所谓的可采纳（admissible）。1. 求前 K 短的 可以带环的 路径（的长度） 1.1. 典型的启发式搜索 设起点为 s；终点为 t；对于一个点 v，dt(v) 表示从 v 走到 t 的最短路径的长度（可以在初始化的时候全都算好）。 网友 richard 教会了我，可以用最典型的启发式搜索来解这个问题。一个状态 x 表示的是从 s 走到某个点的一条路径，把这个点记作 x.v，把这条路径的长度记作 x.len。接着，我们可以使用以下启发函数：g(x) = x.len; h(x) = dt(x.v); f(x) = g(x) + h(x) = x.len + dt(x.v) 初始状态中， x.v = s； x.len = 0。然后每次让优先队列（所谓的 Open 表）中 f(x) 值最小的状态 x 出队，再跟据图中所有从 x.v 出发的边发展下一层状态，让它们进队列。优先队列中不存在判重复的问题，因为每个状态所代表的路径肯定是不一样的。 不难想通，这是一个 A* 算法，因为这里的 h(x) 本身就是 h*(x)，当然满足 h(x) x.v 就称作 Px 的偏离边（deviation edge）； Px 上从 x.pre 到 t 的这一段子路径就称为 Px 的偏离路径（deviation path）。为什么叫作偏离路径，看到后面都明白了。 先求出从 s 到 t 的最短路径，它就是初始状态 x1 所要代表的路径。设它的第一条边是 s - a，则 x1.v = a； x1.len = w(s, a) （w(s, a) 表示边 s - a 的长度）； x1.pre = s，也就是说，规定 Px1 的偏离边是 s - a。 把 x1 放进优先队列。接下来，每当进入最大的循环的第 i 轮，从优先队列里出队的状态（启发值最小的，也就是路径长度目前最短的状态，记作 xi）就代表了第 i 短的解。第一轮出队的当然是前面定义的初始状态 x1。下面要从它发展新的状态，作为可能的第 2 短的解，放进优先队列。发展的方法如下： 对于 Px1 的偏离路径上的每一条边（设它为 u - v），都要找出另一条边 u - v，满足在所有从点 u 出发的边当中， w(u, v) + dt(v) 仅仅高于 w(u, v) + dt(v) （或与它相同）；也就是说，从 u 出发，走 u - v 这条边到终点是最近的，走 u - v 这条边是第 2 近的（或者一样近）。从每一条 u - v，我们都可以发展出一个新状态 x： x.v = v； x.len = w(Psu) + w(u, v)； x.pre = u，也就是说 Px 的偏离边就是 u - v。图 1 图 1 给出了一个例子。假设图中蓝色和黑色的边组成的路径就是 Px1，蓝色边是它的偏离路径；那些红色的边就是前面说的那些 u - v；红色的虚线就代表了从每个 v 到 t 的最短路径。可见，每条 Px 都是从 u - v 开始从 Px1 “身上”偏离出来的，因此把 从偏离边到终点 的这一段路径称为 Px 的偏离路径。 注意，由于本问题中求的路径是可以带环的，所以走到终点以后还可以回头再走。因此，在图 1 中可以看到在点 t 后面也发展了一条偏离路径。这条偏离路径显然不再需要是第 2 短的，而是从 t 出发再回到 t 的最短的路径。 上面讲的是从 x1 发展状态的情况。从之后的 xi 发展状态的时候还有一点要注意：在我们寻找偏离边 u - v 的时候，如果 u = xi.pre （也就是当 要找的偏离边 和 xi 的偏离边 是从同一点出发时），则要注意 u - v 不仅要和 u - xi.v 不同，而且要和 xi 的所有祖先状态中从点 u 出发的那条边都不同，不然新发展的状态岂不是和 xi 的祖先状态重复了。图 2 图 2 给出了一个例子。假设蓝色路径是从黑色路径中发展出的偏离路径；当从蓝色路径发展偏离路径时，要找的是除了蓝色和黑色的边以外，能以最短的距离走到 t 的那条边，假设这里我们找到的是红色的那条边；当从红色路径发展偏离路径时，要找的是除了红色、蓝色和黑色的边以外，能以最短的距离走到 t 的那条边，假设这里我们找到的是绿色的那条边。 如此一来，可能有很多偏离路径都是从同一点偏离出来的，但是它们的偏离边都不相同。要在程序中实现这一点，可以在每个状态中记录下所有祖先状态的偏离边。 显然 Yen 算法也是一个 A* 算法，但是它有一个特点，前面已经说过了，就是最大的那个循环最多只要做 K 次，因为每当一个状态出队列时，我们就找到了一个解。因此基本上可以估计出算法的时间复杂度： 设图中有 N 个点，那么一条偏离路径上最多只有 N 条边（因为它是一条边 加上 从某一点到终点的最短路径），也就是说，从一个状态最多发展出 N + 1 个新状态（偏离路径上的每条边发展出一个，从点 t 再发展出一个）。 寻找一条偏离路径时，需要扫描从一个点出发的所有边，暂且假设从一个点出发的边最多也是 N 条，那么这一步要花 O(N) 的时间。 可以想象优先队列（Open 表）里最多有 O(K * N) 个元素，所以每次维护优先队列的时间差不多是 O( lg (K * N) )。 因此，总的时间复杂度，在最差情况下，差不多就是 O( K * ( N2 + lg(K * N) ) )。当然这只是我个人估计一下，不要太拿它当回事。 1.3. MPS 算法 同样是在The K shortest paths problem这篇文章中，还介绍了作者自已发明的 MPS 算法（MPS 是该文章的三位作者的名字缩写）。它的框架和 Yen 算法相同，但是有一个优化，可以加快寻找偏离边的速度。方法就是把从每个点出发的所有边，都按照从该条边走向 t 的最短距离 升序排序（最好用邻接链表描述图）。图 3 图 3 给出了一个例子。图中从点 s 出发的边有红、蓝和绿三条，延着它们到达终点 t 的最短距离分别为 3、 2 和 4。因此把从 s 出发的边排序为 (蓝, 红, 绿)。 这样一来，寻找偏离边的时间就只有 O(1) 了。因为我们从某一点第一次发展偏离边时，只要选它的邻接链表中的第一条边；下一次再从该点发展时，只要选第二条边再也不用一一扫描所有边了，也不用担心会和祖先状态的偏离边重复了。 假设图中有 N 个点，从每个点出发的边最多也是 N 条。那么排序一个点的邻接链表需要 O(N * lg N) 的时间，排序整个邻接链表的时间就是 O(N2 * lgN)；搜索的时间由 Yen 算法的 O(K * N2) 降至 O(K * N)。因此，整个算法在最差情况下的时间复杂度大约就是 O(N2 * lgN + K * N)。（从数字上看，好像也没有比 Yen 算法快到哪去但是实际试下来确实是快的。）2. 求前 K 短的 无环 路径（的长度） 2.1. 典型的启发式搜索 网友 richard 在他的这篇文章里介绍了，把 1.1 节中的算法稍加修改，就可以用来求无环的前 K 短路径。修改方法就是在每个状态中保存 Psv 所经过的点；当从一个状态发展新状态时，下一步走的点不能出现在 Psv 中（如果点比较少的话，用位运算就可以很快地对此进行判断。）。这样一来，最终求出的路径就无环了。图 4 这个算法在大多数情况下确实很好用，但是在 2006 年横滨赛区的最后一题中，就有一组阴险的数据可以让这个算法超时。如图 4 所示，从点 s 出发只有两条边：蓝色的很短，红色的非常长（既使把图中所有边的长度都加起来，也没有它长）；能走向点 t 的只有一条边，它的起点正是蓝色边的终点；图的其它部分有很多点，它们两两之间都有边（图 4 中只是象征性地画了一下，实际上有更多点）。可以想象，只要第一步走了蓝色的边，那么能到达点 t 的无环的路径只有一条，那就是 s - 蓝色的点 - t。从第 2 短的解开始，都必须走红色的边。 但是启发式搜索一定会先走蓝色的边，然后尝试其后的所有路径。直到实在走投无路径时，才会回过头来走红色的边，因为从长度来看，红色边的优先级实在太低了（虽然它才是正解）。假设图中有 N 个点，可以想象，启发式搜索会先尝试 O(N!) 条错误的路径，那就太可怕了。 我曾经想过下面一些优化的方案，但是好像都行不通： 如果在一个我们想要发展的新状态 x 中，从 s 到 x.v 的路径 和 从 x.v 到 t 的最短路径上有重复的点（前者的点集被保存在 x 中；后者的点集可以在初始化所有最短路径时记录下来），则不让它进优先队列（Open 表）？ 这样做是不对的。因为虽然从 x.v 到 t 的最短路径不能构成无环的解，但是这并不代表从 x.v 到 t 的稍长一点的路径就不可能构成无环的解。因此，这样的状态还是必须得发展下去，否则就可能错过了一些解。 在优先队列（Open 表）里只保存前 K 个最优的状态，比较差的状态就不进队列了？ 这样做更加是不对的。因为图 4 这个例子就已经明确地说明了，启发值比较优先的状态并不一定能通向正解，而启发值较差的状