spfa算法的優(yōu)化及應用

SPFA算法的優(yōu)化與應用廣東中山紀念中學姜碧野常見問題：1、在負權圖上判斷是否存在負環(huán)2、解決有環(huán)的動態(tài)規(guī)劃轉(zhuǎn)移方程這些問題該如何解決？引入SPFA內(nèi)容概要第一部分簡要介紹SPFA的基本實現(xiàn)第二部分提出SPFA一種新的實現(xiàn)方式第三部分介紹如何靈活使用SPFA解題在本文中將看到：SPFA全稱ShortestPathFasterAlgorithm基本應用為快速求解單源最短路靈活多變相比其他同類算法有什么優(yōu)點呢？讓我們來一起領略！簡潔優(yōu)美適用面廣Relax(u,v){ IfF(v)>F(u)+W_Cost(u,v)then F(v)=F(u)+W_Cost(u,v);}SPFA的核心正是松弛操作：.......A1TAnS但松弛操作直接得出的Bellman-Ford算法效率低下

ForTime=1toN For(u,v)∈E Relax(u,v)上圖數(shù)據(jù)中，總運算量高達N^2而邊(S,A1)雖然被調(diào)用N次。但實際有用的只有一次SPFA則使用隊列進行了優(yōu)化！思想：只保存被更新但未擴展的節(jié)點。減少了大量無用的計算，效率大大提高！A1A2…….A4An-1A3AnHeadTail當前待擴展元素在上圖的例子中，每個節(jié)點只進隊一次，只需N次運算。相比Bellman-Ford優(yōu)勢明顯。.......A1TAnS但有負環(huán)時依然退化為O(NM)在1000000個點，2000000條邊的隨機數(shù)據(jù)中SPFA甚至比使用堆優(yōu)化的Dijkstra還要快。能夠改進嗎？A1TAnS…….長期以來基于隊列的SPFA并未取得突破傳統(tǒng)的隊列實現(xiàn):缺點：NewNode需要之前的元素全部出隊后才能擴展 中斷了迭代的連續(xù)性猜想：能否把NewNode放在Head后面進行下一次擴展？A1A2…….A4An-1A3AnHeadTailNewNode嘗試新的實現(xiàn)方法！猜想程序圖論中的基本算法：深度優(yōu)先搜索

基本數(shù)據(jù)結(jié)構：棧SPFA_Dfs(Node){For(Node,v)∈E Ifdis[v]>dis[Node]+w(Node,v)then dis[v]=dis[Node]+w(Node,v); SPFA_Dfs(v);}}核心思想:每次從剛剛被更新的節(jié)點開始遞歸進行下一次迭代！后進先出！判斷存在負環(huán)的條件：重新經(jīng)過某個在當前搜索棧中的節(jié)點A1TAnS…….相比隊列，深度優(yōu)先有著先天優(yōu)勢：在環(huán)上走一圈，回到已遍歷過的點即有負環(huán)。絕大多數(shù)情況下時間為O(M)級別。實戰(zhàn):WordRings(ACM-ICPCCentrualEuropean2005)676個點，100000條邊，查找負環(huán)。DFS只需219ms！一個簡潔的數(shù)據(jù)結(jié)構和算法在一定程度上解決了大問題。優(yōu)美的SPFA！SA1A2AkAk-1…......B1…….B2BmT+∞最壞情況下需要KM次運算優(yōu)化：隨機調(diào)整邊的順序

則期望k+mLogk優(yōu)化無止境！還有不足嗎？讓我們結(jié)合一道題目來進行探討

最短路問題其實只是SPFA迭代思想在圖論中的一個特例，在其他各類動態(tài)規(guī)劃，迭代法解方程，不等式等問題中往往也能發(fā)揮奇效！蘋果爭奪戰(zhàn)兩個人A,B在一個5*6的矩陣里搶奪蘋果。矩陣包含空地，4棵蘋果樹和障礙物，每個蘋果樹上有3個蘋果。A先行動，然后兩人輪流操作，每一回合每人可以向四周移動一格或停留在一棵蘋果樹下，如果蘋果樹非空可以摘下一個蘋果。兩人不能移動到矩陣外，障礙物上或是對方的位置，且兩人絕頂聰明。問A最多可以搶到多少個蘋果。AB此時B不能再向左移動而A可以逐步摘下3棵樹的所有蘋果AB開始時A無法移動之后B一直不動，A無法得到任何蘋果問題分析:

經(jīng)典的博弈模型，數(shù)據(jù)規(guī)模比較小，考慮動態(tài)規(guī)劃F[X,Y,K]表示輪到A行動，A的位置為X，B的位置為Y，蘋果樹狀態(tài)為K(使用狀態(tài)壓縮的4位4進制表示）時A最多獲得多少蘋果。G[X,Y,K]類似表示輪到B行動時，A最少獲得的蘋果數(shù)。狀態(tài)數(shù)為30*30*256*2≈500000可以承受轉(zhuǎn)移方程也簡單，直接枚舉5種行動F[X,Y,K]=Max(G[X’,Y’,K’]+Apple)G[X,Y,K]=Min(F[X’,Y’,K’])但是….AB單純的狀態(tài)轉(zhuǎn)移會出現(xiàn)環(huán)，怎么辦呢？解決存在環(huán)的動態(tài)規(guī)劃，常規(guī)思路:一：利用標號法通過已經(jīng)得出最優(yōu)解的狀態(tài)遞推出其他狀態(tài)。值最大的？但G[]可能被其他較小的F[]更新，并不是最優(yōu)解。

值最小的？F[]同樣可能被其他更大的G[]更新，因此標號法并不適用類似于在負權圖上使用Dijikstra如何找出最優(yōu)解？思路二：參考負權圖上求最短路的思想通過局部的較優(yōu)值一步步迭代得到最優(yōu)解可行嗎？假設當前解為：

G[]=F[]=5354之后G[]得出最優(yōu)解4直接用較優(yōu)解更新會導致非法解。問題所在：F[]和G[]的最優(yōu)化目標不同兩種常規(guī)解法都失敗了，我們需要從新的角度來思考猜想：能否越過狀態(tài)間紛繁復雜的轉(zhuǎn)移關系直接考慮最終狀態(tài)呢？回歸原方程：

F[X,Y,K]=Max(G[X’,Y’,K’]+Apple)G[X,Y,K]=Min(F[X’,Y’,K’])既是轉(zhuǎn)移方程，也是終狀態(tài)聯(lián)想：SPFA在圖論求最短路中的本質(zhì)：三角不等式：最短路的終狀態(tài)，對于所有邊(u,v)∈E

有distance(s,v)<=distance(s,u)+w(u,v)。當某邊三角不等式不成立時，用松弛操作調(diào)整之。在本題中適用嗎？尋找矛盾并解決矛盾同樣：F[X,Y,K]=Max(G[X’,Y’,K’]+Apple)

是問題的終狀態(tài)

G[X,Y,K]=Min(F[X’,Y’,K’])一旦方程整體不成立便重賦值！算法： 先對邊界狀態(tài)賦初值為0。使用SPFA不斷考察每條轉(zhuǎn)移方程是否成立，不成立則更新。

將松弛操作推廣！假設當前解為：

G[]=F[]=5345之后G[]得出最優(yōu)解2G’[]=4F[]=MAX(G[],G’[])2

特點:

賦值時考慮的是一個整體，即需要在所有與當前節(jié)點關聯(lián)的狀態(tài)中取最值，保證了合法性。

G[]被更新時F[]還要重新考慮G’[]。性質(zhì)1：該算法結(jié)束時求得的解為正確解。證明：該結(jié)論顯然，算法結(jié)束意味各個方程均成立性質(zhì)2：該算法一定會結(jié)束。證明：把狀態(tài)按照其最終值的大小分層，則可以發(fā)現(xiàn)當前K層確定時，對于第K+1層有：

1.G[]可以從前K+1層取得最小值。

2.F[]的最大值只能從前K+1層取，否則其最終值不可能為K+1。因此狀態(tài)會逐層確定并最終停止。

算法正確嗎？讓我們繼續(xù)分析?；仡櫵伎歼^程，我們似乎感到：眾里尋他千百度，驀然回首，那人卻在燈火闌珊處

最終算法完完全全建立在原方程之上，沒有轉(zhuǎn)彎，沒有變形，只需“簡單機械”地賦值。而與之類似的傳統(tǒng)迭代法卻并不可行。這是偶然嗎？更新時需遍歷所有相關節(jié)點(本題算法)更新時只需考慮點對間關系(最短路迭代算法)每個節(jié)點只擴展一次(標號法)利用標號法則使用貪心思想再優(yōu)化優(yōu)化：利用最短路問題中當前解只會成為次優(yōu)解，而不會成為非法解的性質(zhì)。不！讓我們對比幾種算法。

三者的本質(zhì)都是統(tǒng)一的，但隨著算法的優(yōu)化適用面逐步縮窄

優(yōu)化算法是好的，但如果沒有對算法有著深刻的認識，忽略了算法的適用條件，思維的定勢很容易使我們得出錯誤算法。靈活運用SPFA算法解題才