1、SPFA算法的優(yōu)化與應(yīng)用,廣東中山紀(jì)念中學(xué) 姜碧野,常見問題：,1、在負(fù)權(quán)圖上判斷是否存在負(fù)環(huán),2、解決有環(huán)的動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程,這些問題該如何解決？,引入,SPFA,內(nèi)容概要,第一部分 簡要介紹SPFA的基本實(shí)現(xiàn),第二部分 提出SPFA一種新的實(shí)現(xiàn)方式,第三部分 介紹如何靈活使用SPFA解題,在本文中將看到：,SPFA 全稱 Shortest Path Faster Algorithm 基本應(yīng)用為快速求解單源最短路,靈活多變,相比其他同類算法有什么優(yōu)點(diǎn)呢？,讓我們來一起領(lǐng)略！,簡潔優(yōu)美,適用面廣,Relax(u,v) If F(v)F(u)+W_Cost(u,v) then F(v)=F(u)

2、+W_Cost (u,v); ,SPFA的核心正是松弛操作：,但松弛操作直接得出的Bellman-Ford算法效率低下 For Time=1 to N For (u,v)E Relax(u,v),上圖數(shù)據(jù)中，總運(yùn)算量高達(dá)N2 而邊(S, A1)雖然被調(diào)用N次。 但實(shí)際有用的只有一次,SPFA則使用隊(duì)列進(jìn)行了優(yōu)化！,思想： 只保存被更新但未擴(kuò)展的節(jié)點(diǎn)。 減少了大量無用的計(jì)算，效率大大提高！,在上圖的例子中，每個(gè)節(jié)點(diǎn)只進(jìn)隊(duì)一次，只需N次運(yùn)算。 相比Bellman-Ford優(yōu)勢明顯。,但有負(fù)環(huán)時(shí)依然退化為O(NM),在1000000個(gè)點(diǎn)，2000000條邊的隨機(jī)數(shù)據(jù)中 SPFA甚至比使用堆優(yōu)化的Di

3、jkstra還要快。,能夠改進(jìn)嗎？,長期以來基于隊(duì)列的SPFA并未取得突破,傳統(tǒng)的隊(duì)列實(shí)現(xiàn):,缺點(diǎn)：NewNode需要之前的元素全部出隊(duì)后才能擴(kuò)展 中斷了迭代的連續(xù)性,猜想： 能否把NewNode放在Head后面進(jìn)行下一次擴(kuò)展？,Tail,New Node,嘗試新的實(shí)現(xiàn)方法！,猜想,程序,圖論中的基本算法 ：深度優(yōu)先搜索 基本數(shù)據(jù)結(jié)構(gòu)：棧,SPFA_Dfs(Node) For (Node,v) E If disv disNode+w(Node,v) then disv=disNode+w(Node,v); SPFA_Dfs (v); ,核心思想: 每次從剛剛被更新的節(jié)點(diǎn) 開始遞歸進(jìn)行下一次迭代

4、！,后進(jìn)先出！,判斷存在負(fù)環(huán)的條件： 重新經(jīng)過某個(gè)在 當(dāng)前搜索棧中的節(jié)點(diǎn),相比隊(duì)列，深度優(yōu)先有著先天優(yōu)勢： 在環(huán)上走一圈，回到已遍歷過 的點(diǎn)即有負(fù)環(huán)。 絕大多數(shù)情況下時(shí)間為O(M)級(jí)別。,實(shí)戰(zhàn):WordRings (ACM-ICPC Centrual European2005) 676個(gè)點(diǎn)，100000條邊，查找負(fù)環(huán)。 DFS只需219ms！,一個(gè)簡潔的數(shù)據(jù)結(jié)構(gòu)和算法 在一定程度上解決了大問題。,優(yōu)美的SPFA！,最壞情況下需要KM次運(yùn)算,優(yōu)化：隨機(jī)調(diào)整邊的順序 則期望k+mLogk,優(yōu)化無止境！,還有不足嗎？,讓我們結(jié)合一道題目來進(jìn)行探討,最短路問題其實(shí)只是SPFA迭代思想在圖論 中的一個(gè)特

5、例，在其他各類動(dòng)態(tài)規(guī)劃，迭代法解 方程，不等式等問題中往往也能發(fā)揮奇效！,蘋果爭奪戰(zhàn) 兩個(gè)人A,B在一個(gè)5*6的矩陣?yán)飺寠Z蘋果。矩陣包含空地，4棵蘋果樹和障礙物，每個(gè)蘋果樹上有3個(gè)蘋果。A先行動(dòng)，然后兩人輪流操作，每一回合每人可以向四周移動(dòng)一格或停留在一棵蘋果樹下，如果蘋果樹非空可以摘下一個(gè)蘋果。 兩人不能移動(dòng)到矩陣外，障礙物上或是對方的位置，且兩人絕頂聰明。 問A最多可以搶到多少個(gè)蘋果。,A,B,此時(shí)B不能再向左移動(dòng) 而A可以逐步摘下3棵樹的所有蘋果,A,B,開始時(shí)A無法移動(dòng),之后B一直不動(dòng)， A無法得到任何蘋果,問題分析: 經(jīng)典的博弈模型，數(shù)據(jù)規(guī)模比較小，考慮動(dòng)態(tài)規(guī)劃,FX,Y,K表示輪到

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

7、此標(biāo)號(hào)法并不適用,類似于在負(fù)權(quán)圖上使用Dijikstra,如何找出最優(yōu)解？,思路二：參考負(fù)權(quán)圖上求最短路的思想,通過局部的較優(yōu)值一步步迭代得到最優(yōu)解,可行嗎？,假設(shè)當(dāng)前解為：,G =,F =,5,3,5,4,之后G 得出最優(yōu)解4,兩種常規(guī)解法都失敗了，我們需要從新的角度來思考,猜想： 能否越過狀態(tài)間紛繁復(fù)雜的轉(zhuǎn)移關(guān)系 直接考慮最終狀態(tài)呢？,回歸原方程： FX,Y,K=Max(GX,Y,K+Apple) GX,Y,K=Min(FX,Y,K),既是轉(zhuǎn)移方程，也是終狀態(tài),聯(lián)想：SPFA在圖論求最短路中的本質(zhì)：,三角不等式：最短路的終狀態(tài)，對于所有邊(u,v)E 有distance(s,v)=dist

8、ance (s,u)+w(u,v)。 當(dāng)某邊三角不等式不成立時(shí)，用松弛操作調(diào)整之。,在本題中適用嗎？,尋找矛盾并解決矛盾,同樣：FX,Y,K=Max(GX,Y,K+Apple) 是問題的終狀態(tài) GX,Y,K=Min(FX,Y,K) 一旦方程整體不成立便重賦值！,算法： 先對邊界狀態(tài)賦初值為0。 使用SPFA不斷考察每條轉(zhuǎn)移方程是否成立， 不成立則更新。,將松弛操作推廣！,假設(shè)當(dāng)前解為：,G =,F =,5,3,4,5,之后G 得出最優(yōu)解2,G =,4,F =MAX(G ,G ),2,特點(diǎn): 賦值時(shí)考慮的是一個(gè)整體，即需要在所有與當(dāng) 前節(jié)點(diǎn)關(guān)聯(lián)的狀態(tài)中取最值，保證了合法性。 G 被更新時(shí)F 還要

9、重新考慮G 。,性質(zhì)1：該算法結(jié)束時(shí)求得的解為正確解。,證明：該結(jié)論顯然，算法結(jié)束意味各個(gè)方程均成立,性質(zhì)2：該算法一定會(huì)結(jié)束。,證明： 把狀態(tài)按照其最終值的大小分層，則可以發(fā)現(xiàn) 當(dāng)前K層確定時(shí)，對于第K+1層有： 1.G 可以從前K+1層取得最小值。 2.F 的最大值只能從前K+1層取，否則其最終值不可能為K+1。 因此狀態(tài)會(huì)逐層確定并最終停止。,算法正確嗎？讓我們繼續(xù)分析。,回顧思考過程，我們似乎感到：,最終算法完完全全建立在原方程之上，沒有轉(zhuǎn)彎， 沒有變形，只需“簡單機(jī)械”地賦值。 而與之類似的傳統(tǒng)迭代法卻并不可行。,這是偶然嗎？,更新時(shí)需遍歷所有相關(guān)節(jié)點(diǎn) (本題算法),更新時(shí)只需考慮點(diǎn)對間關(guān)系(最短路迭代算法),每個(gè)節(jié)點(diǎn)只擴(kuò)展一次 (標(biāo)號(hào)法),利用標(biāo)號(hào)法則使用貪心思想再優(yōu)化,優(yōu)化： 利用最短路問題中當(dāng)前解只會(huì)成為次優(yōu)解， 而不會(huì)成為非法解的性質(zhì)。,不！,讓我們對比幾種算法。,三者的本質(zhì)都是統(tǒng)一的，但隨著算法的優(yōu)化適用面逐步縮窄,優(yōu)化算法是好的，但如果沒有對算法 有著深刻的認(rèn)識(shí)，忽略了算法的適用條件，思維的定勢很容易使我們得出錯(cuò)誤算法。,靈活運(yùn)用SPFA算法解題才是關(guān)鍵！,總結(jié),在查找負(fù)環(huán)中，