基于多頭絨泡菌模型的圖論關(guān)鍵問題研究
本文關(guān)鍵詞:基于多頭絨泡菌模型的圖論關(guān)鍵問題研究 出處:《西南大學(xué)》2016年博士論文 論文類型:學(xué)位論文
更多相關(guān)文章: 變形蟲算法 多頭絨泡菌 啟發(fā)式算法 最短路徑問題 最大流問題
【摘要】:圖論問題是數(shù)學(xué)研究中與應(yīng)用領(lǐng)域有密切聯(lián)系的一個分支,其中一些經(jīng)典問題已經(jīng)有幾十年的研究歷史,且依然不斷取得進步。由于這些經(jīng)典問題的解決是實現(xiàn)許多現(xiàn)實應(yīng)用的基礎(chǔ),而對這些問題解法的任何有益改進,都會對相應(yīng)的應(yīng)用領(lǐng)域有巨大的助益。比如最短路徑問題和最大流問題,它們在路由、交通、決策、優(yōu)化等方面的理論和應(yīng)用中都有很重要的地位。這兩類問題的傳統(tǒng)算法已經(jīng)很久沒有取得實質(zhì)性的突破。在單源最短路徑樹問題中,若不存在負(fù)權(quán)邊,經(jīng)典的Dijkstra算法的時間復(fù)雜度達到O(m+n log n),是該問題最快的算法之一。而當(dāng)網(wǎng)絡(luò)中存在負(fù)權(quán)邊時,最好的強多項式算法是Bellman-Ford算法,時間復(fù)雜度達到O(nm),最好的弱多項式算法是縮放算法,時間復(fù)雜度達到O(√nm log U)。對于最大流問題,比較常用的算法為Dinic算法,時間復(fù)雜度為O(n2m)。該問題存在一個被稱為流分解障礙的O(nm)時間界,任何利用增載軌的算法都無法突破這個障礙。許多優(yōu)秀算法的時間復(fù)雜度已達到或突破這個界限,但實現(xiàn)起來非常復(fù)雜,實際效率也不高,限制了它們在實踐中的應(yīng)用。Dinic算法通過動態(tài)樹優(yōu)化可將時間復(fù)雜度降為O(nm log n),但動態(tài)樹是十分復(fù)雜的數(shù)據(jù)結(jié)構(gòu),實現(xiàn)起來非常困難,實際性能也很差。1998年Goldberg和Rao首次獲得突破流分解障礙的二分長度阻塞流算法,將時間復(fù)雜度刷新為O min n2/3,m1/2m log(n2/m)log U。該算法同樣用到了動態(tài)樹并且包含了大量的網(wǎng)絡(luò)變換的操作,因此算法很復(fù)雜,實現(xiàn)起來比較困難,實際效率不高。解決圖論問題的傳統(tǒng)算法一般是基于對圖的遍歷,此類算法基本已經(jīng)達到優(yōu)化的極限。蟻群算法、遺傳算法等啟發(fā)式算法為我們提供了新的思路,那就是基于全局涌現(xiàn)的計算。啟發(fā)式算法在傳統(tǒng)算法無法解決的NP問題中有許多重要的運用,但在最短路徑和最大流問題上始終無法取代傳統(tǒng)算法,因為它們往往不是確定性算法,無法在確定的時間內(nèi)得到準(zhǔn)確的最優(yōu)解,而且收斂速度也難以與傳統(tǒng)算法相比。2000年,Tero等人揭示了多頭絨泡菌生成迷宮中最優(yōu)路徑的特殊能力。多頭絨泡菌是一種大型單細(xì)胞黏菌生物,按生物學(xué)分類歸為變形蟲門黏菌綱中的絨泡黏菌屬,其營養(yǎng)構(gòu)造,運動和攝食方式和原生動物中的變形蟲相似。2007年他們又建立了多頭絨泡菌的數(shù)學(xué)模型,該模型可以解決兩點之間的最短路徑問題,但效率并不穩(wěn)定。本文在此基礎(chǔ)上將原始的模型改進為具有穩(wěn)定效率和確定結(jié)果的算法,稱為變形蟲算法,并運用到單源最短路徑、最大流問題和一些實際問題中。該算法已經(jīng)達到甚至超過了目前最好的傳統(tǒng)算法。變形蟲算法是一種通過正反饋的演化規(guī)則建立的非線性動態(tài)系統(tǒng),通過不斷演化涌現(xiàn)出最終結(jié)果。針對不同的問題,研究和制定不同的規(guī)則和限制條件,得到相應(yīng)的結(jié)果。變形蟲算法在每次迭代中需要解一個系數(shù)矩陣為拉普拉斯矩陣的線性方程組,目前求解線性方程組借助快速矩陣乘法的方法,可以達到O n2.X的時間復(fù)雜度,其中2.X=2.3728639,且還在不斷進步,有望充分接近O(n2 log n)。同時,針對系數(shù)矩陣為拉普拉斯矩陣的特殊線性方程組,可以更快的求解,時間復(fù)雜度為O(m log n)。所以變形蟲算法的時間復(fù)雜度的一般形式為O(km log n),k為迭代次數(shù)。本文將重點研究和改進變形蟲算法來解決單源最短路徑和最大流問題,以及在一些現(xiàn)實問題中的應(yīng)用,創(chuàng)新的研究成果有以下幾個方面:1、證明了多頭絨泡菌數(shù)學(xué)模型的收斂性和正確性,以及它的收斂速度,并將多頭絨泡菌的數(shù)學(xué)模型進行改進和離散化,形成原始的變形蟲算法。對于2007年提出的多頭絨泡菌模型,其收斂過程一直未得到充分的研究和證明。本文在原始模型的基礎(chǔ)上稍作完善,并通過不變集理論證明了它在權(quán)值為正數(shù),初始狀態(tài)非0時,一定收斂于最短路徑的解,同時,其收斂速度與網(wǎng)絡(luò)的結(jié)構(gòu)有關(guān)。我們將這一模型離散化,形成變形蟲算法的原始版本,通過實驗驗證,原始變形蟲算法是一個解決單源最短路徑問題的偽多項式算法,對于整數(shù)問題,它的時間復(fù)雜度可以寫為O U m log2n。原始變形蟲算法只是搭建了一個解決問題的算法框架,體現(xiàn)了多頭絨泡菌模型的正反饋機制。而針對不同問題,算法還需要進行相應(yīng)的改進和優(yōu)化。2、在原始變形蟲算法基礎(chǔ)上,通過擴展改進,形成解決帶負(fù)權(quán)的單源最短路徑問題的變形蟲算法,并分析和比較它的求解效率,該算法優(yōu)于Bellman-Ford算法,同時還具有檢測、定位和消除網(wǎng)絡(luò)中所有的負(fù)權(quán)環(huán)的能力。Bellman-Ford算法可以在O(nm)時間內(nèi)求解帶負(fù)權(quán)的單源最短路徑,并判斷網(wǎng)絡(luò)中是否存在負(fù)環(huán)。本文在原始變形蟲算法基礎(chǔ)上,針對負(fù)權(quán)網(wǎng)絡(luò)的單源最短路徑問題提出改進和優(yōu)化方案,得到時間復(fù)雜度為O(√nm log n)的算法。對于可能存在負(fù)權(quán)環(huán)的網(wǎng)絡(luò),Bellman-Ford算法需要到最后一次迭代結(jié)束才能判定存在負(fù)環(huán),對應(yīng)于算法的最壞情況,而變形蟲算法可以在O n0.Zm log n內(nèi)檢測、定位和消除網(wǎng)絡(luò)中的所有負(fù)權(quán)環(huán),并且不破壞網(wǎng)絡(luò)的連通性,這是其他算法都無法做到的,其中0.Z≈0.65。3、針對最大流問題模型,改進變形蟲算法解決最大流問題,并分析和比較它的求解效率,該算法優(yōu)于Dinic算法,同時還能得到網(wǎng)絡(luò)的所有最小割。目前網(wǎng)絡(luò)最大流問題的算法時間復(fù)雜度的精確下界還沒有被找到,而流分解障礙O(nm)作為該問題中某一類算法的時間復(fù)雜度下界,在很長一段時間都沒有被突破。直到1998年首次得到O min n2/3,m1/2m log(n2/m)log U的算法。但所有達到或突破O(nm)時間界的算法都需要實現(xiàn)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)或者網(wǎng)絡(luò)變換操作,實際效率并不高,不具有實用性,較常用的算法仍然是具有O(n2m)時間復(fù)雜度的Dinic算法等。本文針對最大流問題設(shè)計的變形蟲算法時間復(fù)雜度為O(log(nU)m log n),且易于實現(xiàn),沒有額外的開銷。它是第二個突破流分解障礙的算法,并將該問題的時間復(fù)雜度一舉拉低到?O(m)程度,且在實際效率上也優(yōu)于Dinic算法,具有理論和實用價值。同時,它在迭代過程中,將網(wǎng)絡(luò)自然的按最小割分割成幾個部分,在獲得最大流的同時也得到網(wǎng)絡(luò)中的所有最小割。
[Abstract]:The problem of graph theory is a branch which is closely related to the field of application in mathematical research , some of the classical problems have been studied in several decades , and progress has been made . In 2000 , it is difficult to solve the shortest path problem by using heuristic algorithms such as ant colony algorithm and genetic algorithm . At the same time , the time complexity is O ( m log n ) for the special linear equations of the Laplace matrix for the coefficient matrix . This paper presents an algorithm for solving the shortest path problem of a single source . The algorithm is better than the Bellman - Ford algorithm . The algorithm is better than the Bellman - Ford algorithm . In order to solve the problem of maximum flow problem , the algorithm is better than the Dinic algorithm , and the algorithm is better than the Dinic algorithm . But all the algorithms that achieve or break O ( nm ) time limit need to implement complex data structure or network transform operation .
【學(xué)位授予單位】:西南大學(xué)
【學(xué)位級別】:博士
【學(xué)位授予年份】:2016
【分類號】:O157.5
【相似文獻】
相關(guān)期刊論文 前10條
1 徐翠霞;;無環(huán)網(wǎng)絡(luò)中的最短路徑問題研究[J];科技廣場;2007年03期
2 校景中;肖麗;;最短路徑問題的優(yōu)化算法研究[J];西南民族大學(xué)學(xué)報(自然科學(xué)版);2012年03期
3 張森;;改進蟻群算法求解最短路徑問題[J];電子世界;2013年16期
4 張濤;陳忠;呂一兵;;求解最短路徑問題的一種改進的人工蜂群算法[J];青海師范大學(xué)學(xué)報(自然科學(xué)版);2013年01期
5 余金山;;最短路徑問題的解答圖算法[J];華僑大學(xué)學(xué)報;1984年02期
6 柴登峰,張登榮;前N條最短路徑問題的算法及應(yīng)用[J];浙江大學(xué)學(xué)報(工學(xué)版);2002年05期
7 畢亞軍;王曉威;鄧鳳茹;;網(wǎng)絡(luò)圖任意兩點間最短路徑問題的計算機實現(xiàn)[J];科技資訊;2006年31期
8 馮震;劉佳;李靖;曹延飛;;復(fù)雜網(wǎng)絡(luò)中最短路徑問題的求解算法研究[J];自動化技術(shù)與應(yīng)用;2010年03期
9 伍建華,祁文青,晏伯武;單匯最短路徑問題的一種算法[J];黃石高等?茖W(xué)校學(xué)報;2001年02期
10 莫忠息;;網(wǎng)絡(luò)中含有負(fù)圈的最短路徑問題[J];武漢大學(xué)學(xué)報(自然科學(xué)版);1993年05期
相關(guān)會議論文 前4條
1 崔嵐;阮秋琦;;結(jié)點有擁塞的動態(tài)最短路徑問題的算法研究[A];第十二屆全國信號處理學(xué)術(shù)年會(CCSP-2005)論文集[C];2005年
2 劉翔;袁俊江;;改進遺傳算法在不確定性最短路徑問題的應(yīng)用[A];第六屆中國不確定系統(tǒng)年會論文集[C];2008年
3 王海梅;周獻中;;直線優(yōu)化A*算法在最短路徑問題中的高效實現(xiàn)[A];全國第19屆計算機技術(shù)與應(yīng)用(CACIS)學(xué)術(shù)會議論文集(下冊)[C];2008年
4 易正俊;黃華;張業(yè)亭;;模糊最短路徑問題及標(biāo)號法的實現(xiàn)[A];第五屆中國不確定系統(tǒng)年會論文集[C];2007年
相關(guān)重要報紙文章 前1條
1 于剛;走最近的路還是走最快的路?[N];中國國防報;2006年
相關(guān)博士學(xué)位論文 前4條
1 王慶;基于多頭絨泡菌模型的圖論關(guān)鍵問題研究[D];西南大學(xué);2016年
2 俞峰;復(fù)雜動態(tài)隨機網(wǎng)絡(luò)最短路徑問題研究[D];浙江大學(xué);2009年
3 張鐘;大規(guī)模圖上的最短路徑問題研究[D];中國科學(xué)技術(shù)大學(xué);2014年
4 李杰;鄰域可視性相關(guān)的路徑規(guī)劃問題研究[D];中國科學(xué)技術(shù)大學(xué);2011年
相關(guān)碩士學(xué)位論文 前10條
1 于汶雨;K最短路徑問題的研究與應(yīng)用[D];南京郵電大學(xué);2016年
2 蔣騰飛;網(wǎng)絡(luò)最短路徑問題與應(yīng)用研究[D];南京郵電大學(xué);2013年
3 朱學(xué)智;基于遺傳算法的最短路徑問題研究[D];中國科學(xué)技術(shù)大學(xué);2015年
4 梁娟;網(wǎng)絡(luò)最短路徑問題的研究與應(yīng)用[D];南京郵電大學(xué);2015年
5 邱釗;K最短路徑算法及其應(yīng)用研究[D];電子科技大學(xué);2014年
6 劉佳;復(fù)雜網(wǎng)絡(luò)中最短路徑問題的優(yōu)化算法研究[D];太原科技大學(xué);2007年
7 王東旭;基于KEGG的代謝通路最短路徑問題的研究[D];哈爾濱工業(yè)大學(xué);2007年
8 吳虎發(fā);蟻群優(yōu)化算法在求解最短路徑問題中的研究與應(yīng)用[D];安徽大學(xué);2012年
9 崔樹林;求解不確定馬爾克夫決策問題[D];吉林大學(xué);2006年
10 方志斌;蟻群算法及其在路徑優(yōu)化問題中的研究[D];東華理工大學(xué);2012年
,本文編號:1379849
本文鏈接:http://sikaile.net/shoufeilunwen/jckxbs/1379849.html