国家集训队2009论文集spfa算法的优化及应用

1、SPFA算法的优化与应用,广东中山纪念中学 姜碧野,常见问题：,1、在负权图上判断是否存在负环,2、解决有环的动态规划转移方程,这些问题该如何解决？,引入,SPFA,内容概要,第一部分 简要介绍SPFA的基本实现,第二部分 提出SPFA一种新的实现方式,第三部分 介绍如何灵活使用SPFA解题,在本文中将看到：,SPFA 全称 Shortest Path Faster Algorithm 基本应用为快速求解单源最短路,灵活多变,相比其他同类算法有什么优点呢？,让我们来一起领略！,简洁优美,适用面广,Relax(u,v) If F(v)F(u)+W_Cost(u,v) then F(v)=F(u)+W_Cost (u,v); ,SPFA的核心正是松弛操作：,但松弛操作直接得出的Bellman-Ford算法效率低下 For Time=1 to N For (u,v)E Relax(u,v),上图数据中，总运算量高达N2 而边(S, A1)虽然被调用N次。 但实际有用的只有一次,SPFA则使用队列进行了优化！,思想： 只保存被更新但未扩展的节点。 减少了大量无用的计算，效率大大提高！,在上图的

2、例子中，每个节点只进队一次，只需N次运算。 相比Bellman-Ford优势明显。,但有负环时依然退化为O(NM),在1000000个点，2000000条边的随机数据中 SPFA甚至比使用堆优化的Dijkstra还要快。,能够改进吗？,长期以来基于队列的SPFA并未取得突破,传统的队列实现:,缺点：NewNode需要之前的元素全部出队后才能扩展 中断了迭代的连续性,猜想： 能否把NewNode放在Head后面进行下一次扩展？,Tail,New Node,尝试新的实现方法！,猜想,程序,图论中的基本算法 ：深度优先搜索 基本数据结构：栈,SPFA_Dfs(Node) For (Node,v) E If disv disNode+w(Node,v) then disv=disNode+w(Node,v); SPFA_Dfs (v); ,核心思想: 每次从刚刚被更新的节点 开始递归进行下一次迭代！,后进先出！,判断存在负环的条件： 重新经过某个在 当前搜索栈中的节点,相比队列，深度优先有着先天优势： 在环上走一圈，回到已遍历过 的点即有负环。 绝大多数情况下时间为O(M)级别。,实战:Wor

3、dRings (ACM-ICPC Centrual European2005) 676个点，100000条边，查找负环。 DFS只需219ms！,一个简洁的数据结构和算法 在一定程度上解决了大问题。,优美的SPFA！,最坏情况下需要KM次运算,优化：随机调整边的顺序 则期望k+mLogk,优化无止境！,还有不足吗？,让我们结合一道题目来进行探讨,最短路问题其实只是SPFA迭代思想在图论 中的一个特例，在其他各类动态规划，迭代法解 方程，不等式等问题中往往也能发挥奇效！,苹果争夺战 两个人A,B在一个5*6的矩阵里抢夺苹果。矩阵包含空地，4棵苹果树和障碍物，每个苹果树上有3个苹果。A先行动，然后两人轮流操作，每一回合每人可以向四周移动一格或停留在一棵苹果树下，如果苹果树非空可以摘下一个苹果。 两人不能移动到矩阵外，障碍物上或是对方的位置，且两人绝顶聪明。 问A最多可以抢到多少个苹果。,A,B,此时B不能再向左移动 而A可以逐步摘下3棵树的所有苹果,A,B,开始时A无法移动,之后B一直不动， A无法得到任何苹果,问题分析: 经典的博弈模型，数据规模比较小，考虑动态规划,FX,Y,K表示轮到

4、A行动， A的位置为X，B的位置为Y， 苹果树状态为K(使用状态压缩的4位4进制表示）时 A最多获得多少苹果。 GX,Y,K类似表示轮到B行动时，A最少获得的苹果数。,状态数为30*30*256*2 500000 可以承受,转移方程也简单，直接枚举5种行动,FX,Y,K=Max(GX,Y,K+Apple) GX,Y,K=Min(FX,Y,K),但是.,A,B,单纯的状态转移会出现环，怎么办呢？,解决存在环的动态规划，常规思路:,一：利用标号法 通过已经得出最优解的状态递推出其他状态。,值最大的？但G 可能被其他较小的F 更新， 并不是最优解。,值最小的？ F 同样可能被其他更大的G 更新，,因此标号法并不适用,类似于在负权图上使用Dijikstra,如何找出最优解？,思路二：参考负权图上求最短路的思想,通过局部的较优值一步步迭代得到最优解,可行吗？,假设当前解为：,G =,F =,5,3,5,4,之后G 得出最优解4,两种常规解法都失败了，我们需要从新的角度来思考,猜想： 能否越过状态间纷繁复杂的转移关系 直接考虑最终状态呢？,回归原方程： FX,Y,K=Max(GX,Y,K+Appl

5、e) GX,Y,K=Min(FX,Y,K),既是转移方程，也是终状态,联想：SPFA在图论求最短路中的本质：,三角不等式：最短路的终状态，对于所有边(u,v)E 有distance(s,v)=distance (s,u)+w(u,v)。 当某边三角不等式不成立时，用松弛操作调整之。,在本题中适用吗？,寻找矛盾并解决矛盾,同样：FX,Y,K=Max(GX,Y,K+Apple) 是问题的终状态 GX,Y,K=Min(FX,Y,K) 一旦方程整体不成立便重赋值！,算法： 先对边界状态赋初值为0。 使用SPFA不断考察每条转移方程是否成立， 不成立则更新。,将松弛操作推广！,假设当前解为：,G =,F =,5,3,4,5,之后G 得出最优解2,G =,4,F =MAX(G ,G ),2,特点: 赋值时考虑的是一个整体，即需要在所有与当 前节点关联的状态中取最值，保证了合法性。 G 被更新时F 还要重新考虑G 。,性质1：该算法结束时求得的解为正确解。,证明：该结论显然，算法结束意味各个方程均成立,性质2：该算法一定会结束。,证明： 把状态按照其最终值的大小分层，则可以发现 当前K层确定时，对于

6、第K+1层有： 1.G 可以从前K+1层取得最小值。 2.F 的最大值只能从前K+1层取，否则其最终值不可能为K+1。 因此状态会逐层确定并最终停止。,算法正确吗？让我们继续分析。,回顾思考过程，我们似乎感到：,最终算法完完全全建立在原方程之上，没有转弯， 没有变形，只需“简单机械”地赋值。 而与之类似的传统迭代法却并不可行。,这是偶然吗？,更新时需遍历所有相关节点 (本题算法),更新时只需考虑点对间关系(最短路迭代算法),每个节点只扩展一次 (标号法),利用标号法则使用贪心思想再优化,优化： 利用最短路问题中当前解只会成为次优解， 而不会成为非法解的性质。,不！,让我们对比几种算法。,三者的本质都是统一的，但随着算法的优化适用面逐步缩窄,优化算法是好的，但如果没有对算法 有着深刻的认识，忽略了算法的适用条件，思维的定势很容易使我们得出错误算法。,灵活运用SPFA算法解题才是关键！,总结,在查找负环中，抛开了传统的实现方式， 我们得出一种崭新的架构使效率大大提高,在动态规划中，摆脱了思维定势的影响， 我们才得出正确的解法。,SPFA并不是一个死板的经典算法，我们 只有灵活运用才能发挥其应有的奇效。,在对Bellman-Ford算法的合理优化中， 诞生了高效的SPFA算法。,灵活,谢谢大家！ 欢迎提问,

《国家集训队2009论文集spfa算法的优化及应用》由会员腾****分享，可在线阅读，更多相关《国家集训队2009论文集spfa算法的优化及应用》请在金锄头文库上搜索。