资源描述：
《国家集训队2009论文集spfa算法优化及应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、SPFA算法的优化与应用广东中山纪念中学姜碧野常见问题：1、在负权图上判断是否存在负环2、解决有环的动态规划转移方程这些问题该如何解决？引入SPFA内容概要第一部分简要介绍SPFA的基本实现第二部分提出SPFA一种新的实现方式第三部分介绍如何灵活使用SPFA解题在本文中将看到：SPFA全称ShortestPathFasterAlgorithm基本应用为快速求解单源最短路灵活多变相比其他同类算法有什么优点呢？让我们来一起领略！简洁优美适用面广Relax(u,v){IfF(v)>F(u)+W_Cost(u,v)thenF(v)=F
2、(u)+W_Cost(u,v);}SPFA的核心正是松弛操作：.......A1TAnS但松弛操作直接得出的Bellman-Ford算法效率低下ForTime=1toNFor(u,v)∈ERelax(u,v)上图数据中，总运算量高达N^2而边(S,A1)虽然被调用N次。但实际有用的只有一次SPFA则使用队列进行了优化！思想：只保存被更新但未扩展的节点。减少了大量无用的计算，效率大大提高！A1A2…….A4An-1A3AnHeadTail当前待扩展元素在上图的例子中，每个节点只进队一次，只需N次运算。相比Bellman-Ford
3、优势明显。.......A1TAnS但有负环时依然退化为O(NM)在1000000个点，2000000条边的随机数据中SPFA甚至比使用堆优化的Dijkstra还要快。能够改进吗？A1TAnS…….长期以来基于队列的SPFA并未取得突破传统的队列实现:缺点：NewNode需要之前的元素全部出队后才能扩展中断了迭代的连续性猜想：能否把NewNode放在Head后面进行下一次扩展？A1A2…….A4An-1A3AnHeadTailNewNode尝试新的实现方法！猜想程序图论中的基本算法：深度优先搜索基本数据结构：栈SPFA_Dfs
4、(Node){For(Node,v)∈EIfdis[v]>dis[Node]+w(Node,v)thendis[v]=dis[Node]+w(Node,v);SPFA_Dfs(v);}}核心思想:每次从刚刚被更新的节点开始递归进行下一次迭代！后进先出！判断存在负环的条件：重新经过某个在当前搜索栈中的节点A1TAnS…….相比队列，深度优先有着先天优势：在环上走一圈，回到已遍历过的点即有负环。绝大多数情况下时间为O(M)级别。实战:WordRings(ACM-ICPCCentrualEuropean2005)676个点，1000
5、00条边，查找负环。DFS只需219ms！一个简洁的数据结构和算法在一定程度上解决了大问题。优美的SPFA！SA1A2AkAk-1…......B1…….B2BmT+∞最坏情况下需要KM次运算优化：随机调整边的顺序则期望k+mLogk优化无止境！还有不足吗？让我们结合一道题目来进行探讨最短路问题其实只是SPFA迭代思想在图论中的一个特例，在其他各类动态规划，迭代法解方程，不等式等问题中往往也能发挥奇效！苹果争夺战两个人A,B在一个5*6的矩阵里抢夺苹果。矩阵包含空地，4棵苹果树和障碍物，每个苹果树上有3个苹果。A先行动，然后两
6、人轮流操作，每一回合每人可以向四周移动一格或停留在一棵苹果树下，如果苹果树非空可以摘下一个苹果。两人不能移动到矩阵外，障碍物上或是对方的位置，且两人绝顶聪明。问A最多可以抢到多少个苹果。此时B不能再向左移动而A可以逐步摘下3棵树的所有苹果开始时A无法移动之后B一直不动，A无法得到任何苹果问题分析:经典的博弈模型，数据规模比较小，考虑动态规划F[X,Y,K]表示轮到A行动，A的位置为X，B的位置为Y，苹果树状态为K(使用状态压缩的4位4进制表示）时A最多获得多少苹果。G[X,Y,K]类似表示轮到B行动时，A最少获得的苹果数。状态
7、数为30*30*256*2≈500000可以承受转移方程也简单，直接枚举5种行动F[X,Y,K]=Max(G[X’,Y’,K’]+Apple)G[X,Y,K]=Min(F[X’,Y’,K’])但是….AB单纯的状态转移会出现环，怎么办呢？解决存在环的动态规划，常规思路:一：利用标号法通过已经得出最优解的状态递推出其他状态。值最大的？但G[]可能被其他较小的F[]更新，并不是最优解。值最小的？F[]同样可能被其他更大的G[]更新，因此标号法并不适用类似于在负权图上使用Dijikstra如何找出最优解？思路二：参考负权图上求最短路
8、的思想通过局部的较优值一步步迭代得到最优解可行吗？假设当前解为：G[]=F[]=5354之后G[]得出最优解4直接用较优解更新会导致非法解。问题所在：F[]和G[]的最优化目标不同两种常规解法都失败了，我们需要从新的角度来思考猜想：能否越过状态间纷繁复杂的转移关系直接考虑最终
