本文關(guān)鍵詞：基于多頭絨泡菌模型的圖論關(guān)鍵問題研究　出處：《西南大學(xué)》2016年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 變形蟲算法 多頭絨泡菌 啟發(fā)式算法 最短路徑問題 最大流問題

【摘要】：圖論問題是數(shù)學(xué)研究中與應(yīng)用領(lǐng)域有密切聯(lián)系的一個(gè)分支,其中一些經(jīng)典問題已經(jīng)有幾十年的研究歷史,且依然不斷取得進(jìn)步。由于這些經(jīng)典問題的解決是實(shí)現(xiàn)許多現(xiàn)實(shí)應(yīng)用的基礎(chǔ),而對(duì)這些問題解法的任何有益改進(jìn),都會(huì)對(duì)相應(yīng)的應(yīng)用領(lǐng)域有巨大的助益。比如最短路徑問題和最大流問題,它們?cè)诼酚�、交通、決策、優(yōu)化等方面的理論和應(yīng)用中都有很重要的地位。這兩類問題的傳統(tǒng)算法已經(jīng)很久沒有取得實(shí)質(zhì)性的突破。在單源最短路徑樹問題中,若不存在負(fù)權(quán)邊,經(jīng)典的Dijkstra算法的時(shí)間復(fù)雜度達(dá)到O(m+n log n),是該問題最快的算法之一。而當(dāng)網(wǎng)絡(luò)中存在負(fù)權(quán)邊時(shí),最好的強(qiáng)多項(xiàng)式算法是Bellman-Ford算法,時(shí)間復(fù)雜度達(dá)到O(nm),最好的弱多項(xiàng)式算法是縮放算法,時(shí)間復(fù)雜度達(dá)到O(√nm log U)。對(duì)于最大流問題,比較常用的算法為Dinic算法,時(shí)間復(fù)雜度為O(n2m)。該問題存在一個(gè)被稱為流分解障礙的O(nm)時(shí)間界,任何利用增載軌的算法都無(wú)法突破這個(gè)障礙。許多優(yōu)秀算法的時(shí)間復(fù)雜度已達(dá)到或突破這個(gè)界限,但實(shí)現(xiàn)起來非常復(fù)雜,實(shí)際效率也不高,限制了它們?cè)趯?shí)踐中的應(yīng)用。Dinic算法通過動(dòng)態(tài)樹優(yōu)化可將時(shí)間復(fù)雜度降為O(nm log n),但動(dòng)態(tài)樹是十分復(fù)雜的數(shù)據(jù)結(jié)構(gòu),實(shí)現(xiàn)起來非常困難,實(shí)際性能也很差。1998年Goldberg和Rao首次獲得突破流分解障礙的二分長(zhǎng)度阻塞流算法,將時(shí)間復(fù)雜度刷新為O min n2/3,m1/2m log(n2/m)log U。該算法同樣用到了動(dòng)態(tài)樹并且包含了大量的網(wǎng)絡(luò)變換的操作,因此算法很復(fù)雜,實(shí)現(xiàn)起來比較困難,實(shí)際效率不高。解決圖論問題的傳統(tǒng)算法一般是基于對(duì)圖的遍歷,此類算法基本已經(jīng)達(dá)到優(yōu)化的極限。蟻群算法、遺傳算法等啟發(fā)式算法為我們提供了新的思路,那就是基于全局涌現(xiàn)的計(jì)算。啟發(fā)式算法在傳統(tǒng)算法無(wú)法解決的NP問題中有許多重要的運(yùn)用,但在最短路徑和最大流問題上始終無(wú)法取代傳統(tǒng)算法,因?yàn)樗鼈兺皇谴_定性算法,無(wú)法在確定的時(shí)間內(nèi)得到準(zhǔn)確的最優(yōu)解,而且收斂速度也難以與傳統(tǒng)算法相比。2000年,Tero等人揭示了多頭絨泡菌生成迷宮中最優(yōu)路徑的特殊能力。多頭絨泡菌是一種大型單細(xì)胞黏菌生物,按生物學(xué)分類歸為變形蟲門黏菌綱中的絨泡黏菌屬,其營(yíng)養(yǎng)構(gòu)造,運(yùn)動(dòng)和攝食方式和原生動(dòng)物中的變形蟲相似。2007年他們又建立了多頭絨泡菌的數(shù)學(xué)模型,該模型可以解決兩點(diǎn)之間的最短路徑問題,但效率并不穩(wěn)定。本文在此基礎(chǔ)上將原始的模型改進(jìn)為具有穩(wěn)定效率和確定結(jié)果的算法,稱為變形蟲算法,并運(yùn)用到單源最短路徑、最大流問題和一些實(shí)際問題中。該算法已經(jīng)達(dá)到甚至超過了目前最好的傳統(tǒng)算法。變形蟲算法是一種通過正反饋的演化規(guī)則建立的非線性動(dòng)態(tài)系統(tǒng),通過不斷演化涌現(xiàn)出最終結(jié)果。針對(duì)不同的問題,研究和制定不同的規(guī)則和限制條件,得到相應(yīng)的結(jié)果。變形蟲算法在每次迭代中需要解一個(gè)系數(shù)矩陣為拉普拉斯矩陣的線性方程組,目前求解線性方程組借助快速矩陣乘法的方法,可以達(dá)到O n2.X的時(shí)間復(fù)雜度,其中2.X=2.3728639,且還在不斷進(jìn)步,有望充分接近O(n2 log n)。同時(shí),針對(duì)系數(shù)矩陣為拉普拉斯矩陣的特殊線性方程組,可以更快的求解,時(shí)間復(fù)雜度為O(m log n)。所以變形蟲算法的時(shí)間復(fù)雜度的一般形式為O(km log n),k為迭代次數(shù)。本文將重點(diǎn)研究和改進(jìn)變形蟲算法來解決單源最短路徑和最大流問題,以及在一些現(xiàn)實(shí)問題中的應(yīng)用,創(chuàng)新的研究成果有以下幾個(gè)方面:1、證明了多頭絨泡菌數(shù)學(xué)模型的收斂性和正確性,以及它的收斂速度,并將多頭絨泡菌的數(shù)學(xué)模型進(jìn)行改進(jìn)和離散化,形成原始的變形蟲算法。對(duì)于2007年提出的多頭絨泡菌模型,其收斂過程一直未得到充分的研究和證明。本文在原始模型的基礎(chǔ)上稍作完善,并通過不變集理論證明了它在權(quán)值為正數(shù),初始狀態(tài)非0時(shí),一定收斂于最短路徑的解,同時(shí),其收斂速度與網(wǎng)絡(luò)的結(jié)構(gòu)有關(guān)。我們將這一模型離散化,形成變形蟲算法的原始版本,通過實(shí)驗(yàn)驗(yàn)證,原始變形蟲算法是一個(gè)解決單源最短路徑問題的偽多項(xiàng)式算法,對(duì)于整數(shù)問題,它的時(shí)間復(fù)雜度可以寫為O U m log2n。原始變形蟲算法只是搭建了一個(gè)解決問題的算法框架,體現(xiàn)了多頭絨泡菌模型的正反饋機(jī)制。而針對(duì)不同問題,算法還需要進(jìn)行相應(yīng)的改進(jìn)和優(yōu)化。2、在原始變形蟲算法基礎(chǔ)上,通過擴(kuò)展改進(jìn),形成解決帶負(fù)權(quán)的單源最短路徑問題的變形蟲算法,并分析和比較它的求解效率,該算法優(yōu)于Bellman-Ford算法,同時(shí)還具有檢測(cè)、定位和消除網(wǎng)絡(luò)中所有的負(fù)權(quán)環(huán)的能力。Bellman-Ford算法可以在O(nm)時(shí)間內(nèi)求解帶負(fù)權(quán)的單源最短路徑,并判斷網(wǎng)絡(luò)中是否存在負(fù)環(huán)。本文在原始變形蟲算法基礎(chǔ)上,針對(duì)負(fù)權(quán)網(wǎng)絡(luò)的單源最短路徑問題提出改進(jìn)和優(yōu)化方案,得到時(shí)間復(fù)雜度為O(√nm log n)的算法。對(duì)于可能存在負(fù)權(quán)環(huán)的網(wǎng)絡(luò),Bellman-Ford算法需要到最后一次迭代結(jié)束才能判定存在負(fù)環(huán),對(duì)應(yīng)于算法的最壞情況,而變形蟲算法可以在O n0.Zm log n內(nèi)檢測(cè)、定位和消除網(wǎng)絡(luò)中的所有負(fù)權(quán)環(huán),并且不破壞網(wǎng)絡(luò)的連通性,這是其他算法都無(wú)法做到的,其中0.Z≈0.65。3、針對(duì)最大流問題模型,改進(jìn)變形蟲算法解決最大流問題,并分析和比較它的求解效率,該算法優(yōu)于Dinic算法,同時(shí)還能得到網(wǎng)絡(luò)的所有最小割。目前網(wǎng)絡(luò)最大流問題的算法時(shí)間復(fù)雜度的精確下界還沒有被找到,而流分解障礙O(nm)作為該問題中某一類算法的時(shí)間復(fù)雜度下界,在很長(zhǎng)一段時(shí)間都沒有被突破。直到1998年首次得到O min n2/3,m1/2m log(n2/m)log U的算法。但所有達(dá)到或突破O(nm)時(shí)間界的算法都需要實(shí)現(xiàn)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)或者網(wǎng)絡(luò)變換操作,實(shí)際效率并不高,不具有實(shí)用性,較常用的算法仍然是具有O(n2m)時(shí)間復(fù)雜度的Dinic算法等。本文針對(duì)最大流問題設(shè)計(jì)的變形蟲算法時(shí)間復(fù)雜度為O(log(nU)m log n),且易于實(shí)現(xiàn),沒有額外的開銷。它是第二個(gè)突破流分解障礙的算法,并將該問題的時(shí)間復(fù)雜度一舉拉低到?O(m)程度,且在實(shí)際效率上也優(yōu)于Dinic算法,具有理論和實(shí)用價(jià)值。同時(shí),它在迭代過程中,將網(wǎng)絡(luò)自然的按最小割分割成幾個(gè)部分,在獲得最大流的同時(shí)也得到網(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é)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 徐翠霞;;無(wú)環(huán)網(wǎng)絡(luò)中的最短路徑問題研究[J];科技廣場(chǎng);2007年03期

2 校景中;肖麗;;最短路徑問題的優(yōu)化算法研究[J];西南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年03期

3 張森;;改進(jìn)蟻群算法求解最短路徑問題[J];電子世界;2013年16期

4 張濤;陳忠;呂一兵;;求解最短路徑問題的一種改進(jìn)的人工蜂群算法[J];青海師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年01期

5 余金山;;最短路徑問題的解答圖算法[J];華僑大學(xué)學(xué)報(bào);1984年02期

6 柴登峰,張登榮;前N條最短路徑問題的算法及應(yīng)用[J];浙江大學(xué)學(xué)報(bào)(工學(xué)版);2002年05期

7 畢亞軍;王曉威;鄧?guó)P茹;;網(wǎng)絡(luò)圖任意兩點(diǎn)間最短路徑問題的計(jì)算機(jī)實(shí)現(xiàn)[J];科技資訊;2006年31期

8 馮震;劉佳;李靖;曹延飛;;復(fù)雜網(wǎng)絡(luò)中最短路徑問題的求解算法研究[J];自動(dòng)化技術(shù)與應(yīng)用;2010年03期

9 伍建華,祁文青,晏伯武;單匯最短路徑問題的一種算法[J];黃石高等�？茖W(xué)校學(xué)報(bào);2001年02期

10 莫忠息;;網(wǎng)絡(luò)中含有負(fù)圈的最短路徑問題[J];武漢大學(xué)學(xué)報(bào)(自然科學(xué)版);1993年05期

相關(guān)會(huì)議論文 前4條

1 崔嵐;阮秋琦;;結(jié)點(diǎn)有擁塞的動(dòng)態(tài)最短路徑問題的算法研究[A];第十二屆全國(guó)信號(hào)處理學(xué)術(shù)年會(huì)（CCSP-2005）論文集[C];2005年

2 劉翔;袁俊江;;改進(jìn)遺傳算法在不確定性最短路徑問題的應(yīng)用[A];第六屆中國(guó)不確定系統(tǒng)年會(huì)論文集[C];2008年

3 王海梅;周獻(xiàn)中;;直線優(yōu)化A*算法在最短路徑問題中的高效實(shí)現(xiàn)[A];全國(guó)第19屆計(jì)算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會(huì)議論文集（下冊(cè)）[C];2008年

4 易正俊;黃華;張業(yè)亭;;模糊最短路徑問題及標(biāo)號(hào)法的實(shí)現(xiàn)[A];第五屆中國(guó)不確定系統(tǒng)年會(huì)論文集[C];2007年

相關(guān)重要報(bào)紙文章 前1條

1 于剛;走最近的路還是走最快的路？[N];中國(guó)國(guó)防報(bào);2006年

相關(guān)博士學(xué)位論文 前4條

1 王慶;基于多頭絨泡菌模型的圖論關(guān)鍵問題研究[D];西南大學(xué);2016年

2 俞峰;復(fù)雜動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)最短路徑問題研究[D];浙江大學(xué);2009年

3 張鐘;大規(guī)模圖上的最短路徑問題研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

4 李杰;鄰域可視性相關(guān)的路徑規(guī)劃問題研究[D];中國(guó)科學(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];中國(guó)科學(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年

，

本文編號(hào)：1379849