資源描述：
《算法合集之《SPFA算法的優(yōu)化及應(yīng)用》.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、2009ThesisSPFA的優(yōu)化與應(yīng)用姜碧野迭代求解的利器--------SPFA算法的優(yōu)化與應(yīng)用廣東中山紀(jì)念中學(xué)姜碧野【摘要】SPFA算法,全稱ShortestPathFasterAlgorithm,是Bellman-Ford算法的改進(jìn)版。該算法以三角不等式為基礎(chǔ)，實(shí)現(xiàn)時(shí)借助隊(duì)列或棧不斷進(jìn)行迭代以求得最優(yōu)解。具有效率高、實(shí)現(xiàn)簡(jiǎn)潔、擴(kuò)展性強(qiáng)等優(yōu)點(diǎn)。三角不等式的普適性及其類似搜索的實(shí)現(xiàn)方式，使其應(yīng)用并不只局限于圖論中的最短路徑，更可以在動(dòng)態(tài)規(guī)劃、迭代法解方程中發(fā)揮出巨大的作用，解決一些非常規(guī)問(wèn)題；還可根據(jù)具體問(wèn)題進(jìn)行各種各樣的優(yōu)化。本文將對(duì)其進(jìn)行全面的分析、測(cè)試和深
2、入的討論?！娟P(guān)鍵詞】迭代SPFA深度優(yōu)先搜索最優(yōu)性動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程-第1頁(yè)共37頁(yè)-2009ThesisSPFA的優(yōu)化與應(yīng)用姜碧野【目錄】SPFA算法簡(jiǎn)介............................................................................................31.1SPFA算法的基本實(shí)現(xiàn)....................................................................31.2活學(xué)活用：SPFA的深度優(yōu)先實(shí)現(xiàn)及其優(yōu)化........
3、.......................51.2.1:基于Dfs的SPFA的基本原理.................................................51.2.2:基于Dfs的SPFA的相關(guān)優(yōu)化.................................................71.3SPFA算法實(shí)際效果測(cè)試及比較....................................................8*1.4Johnson算法介紹..................................
4、......................................122.SPFA算法在實(shí)際應(yīng)用中的優(yōu)化...........................................................132.1如何使用SPFA快速查找負(fù)(正)環(huán)...............................................132.2注意對(duì)無(wú)用狀態(tài)的裁剪...............................................................173.SPFA算法的應(yīng)用..........
5、........................................................................193.1差分約束系統(tǒng)...............................................................................193.2在一類狀態(tài)轉(zhuǎn)移階段性不明顯的動(dòng)態(tài)規(guī)劃中的應(yīng)用...............203.3探討SPFA在解方程中的應(yīng)用......................................................233.4一類狀態(tài)
6、轉(zhuǎn)移存在“后效性”的動(dòng)態(tài)規(guī)劃中的應(yīng)用...................285附錄........................................................................................................335.1例題原題.......................................................................................335.2源程序&例題測(cè)試數(shù)據(jù).............................
7、...................................376.參考文獻(xiàn)...............................................................................................377.鳴謝........................................................................................................37-第2頁(yè)共37頁(yè)-2009ThesisSPFA的優(yōu)化與應(yīng)用姜碧野【正
