基于多頭絨泡菌模型的圖論關(guān)鍵問(wèn)題研究.pdf

1、圖論問(wèn)題是數(shù)學(xué)研究中與應(yīng)用領(lǐng)域有密切聯(lián)系的一個(gè)分支，其中一些經(jīng)典問(wèn)題已經(jīng)有幾十年的研究歷史，且依然不斷取得進(jìn)步。由于這些經(jīng)典問(wèn)題的解決是實(shí)現(xiàn)許多現(xiàn)實(shí)應(yīng)用的基礎(chǔ)，而對(duì)這些問(wèn)題解法的任何有益改進(jìn)，都會(huì)對(duì)相應(yīng)的應(yīng)用領(lǐng)域有巨大的助益。比如最短路徑問(wèn)題和最大流問(wèn)題，它們?cè)诼酚?、交通、決策、優(yōu)化等方面的理論和應(yīng)用中都有很重要的地位。這兩類(lèi)問(wèn)題的傳統(tǒng)算法已經(jīng)很久沒(méi)有取得實(shí)質(zhì)性的突破。
　　在單源最短路徑樹(shù)問(wèn)題中，若不存在負(fù)權(quán)邊，經(jīng)典的Dijks

2、tra算法的時(shí)間復(fù)雜度達(dá)到O(m+n log n)，是該問(wè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ì)于最大流問(wèn)題，比較常用的算法為Dinic算法，時(shí)間復(fù)雜度為O(n2m)。該問(wèn)題存在一個(gè)被稱(chēng)為流分解障礙的O(nm)時(shí)間界，任何利用增載軌的算法都無(wú)法突破這個(gè)障礙。許多優(yōu)秀算法的時(shí)間復(fù)雜度已達(dá)到

3、或突破這個(gè)界限，但實(shí)現(xiàn)起來(lái)非常復(fù)雜，實(shí)際效率也不高，限制了它們?cè)趯?shí)踐中的應(yīng)用。Dinic算法通過(guò)動(dòng)態(tài)樹(shù)優(yōu)化可將時(shí)間復(fù)雜度降為O(nm log n)，但動(dòng)態(tài)樹(shù)是十分復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)起來(lái)非常困難，實(shí)際性能也很差。1998年Goldberg和Rao首次獲得突破流分解障礙的二分長(zhǎng)度阻塞流算法，將時(shí)間復(fù)雜度刷新為O(min{n2/3。m1/2}m log(n2/m) log U)。該算法同樣用到了動(dòng)態(tài)樹(shù)并且包含了大量的網(wǎng)絡(luò)變換的操作，因此算法

4、很復(fù)雜，實(shí)現(xiàn)起來(lái)比較困難，實(shí)際效率不高。解決圖論問(wèn)題的傳統(tǒng)算法一般是基于對(duì)圖的遍歷，此類(lèi)算法基本已經(jīng)達(dá)到優(yōu)化的極限。蟻群算法、遺傳算法等啟發(fā)式算法為我們提供了新的思路，那就是基于全局涌現(xiàn)的計(jì)算。
　　啟發(fā)式算法在傳統(tǒng)算法無(wú)法解決的NP問(wèn)題中有許多重要的運(yùn)用，但在最短路徑和最大流問(wèn)題上始終無(wú)法取代傳統(tǒng)算法，因?yàn)樗鼈兺皇谴_定性算法，無(wú)法在確定的時(shí)間內(nèi)得到準(zhǔn)確的最優(yōu)解，而且收斂速度也難以與傳統(tǒng)算法相比。2000年，Tero等人揭示了

5、多頭絨泡菌生成迷宮中最優(yōu)路徑的特殊能力。多頭絨泡菌是一種大型單細(xì)胞黏菌生物，按生物學(xué)分類(lèi)歸為變形蟲(chóng)門(mén)黏菌綱中的絨泡黏菌屬，其營(yíng)養(yǎng)構(gòu)造，運(yùn)動(dòng)和攝食方式和原生動(dòng)物中的變形蟲(chóng)相似。2007年他們又建立了多頭絨泡菌的數(shù)學(xué)模型，該模型可以解決兩點(diǎn)之間的最短路徑問(wèn)題，但效率并不穩(wěn)定。本文在此基礎(chǔ)上將原始的模型改進(jìn)為具有穩(wěn)定效率和確定結(jié)果的算法，稱(chēng)為變形蟲(chóng)算法，并運(yùn)用到單源最短路徑、最大流問(wèn)題和一些實(shí)際問(wèn)題中。該算法已經(jīng)達(dá)到甚至超過(guò)了目前最好的傳統(tǒng)算

6、法。
　　變形蟲(chóng)算法是一種通過(guò)正反饋的演化規(guī)則建立的非線(xiàn)性動(dòng)態(tài)系統(tǒng)，通過(guò)不斷演化涌現(xiàn)出最終結(jié)果。針對(duì)不同的問(wèn)題，研究和制定不同的規(guī)則和限制條件，得到相應(yīng)的結(jié)果。變形蟲(chóng)算法在每次迭代中需要解一個(gè)系數(shù)矩陣為拉普拉斯矩陣的線(xiàn)性方程組，目前求解線(xiàn)性方程組借助快速矩陣乘法的方法，可以達(dá)到O(n2.X)的時(shí)間復(fù)雜度，其中2.X=2.3728639，且還在不斷進(jìn)步，有望充分接近O(n2 log n)。同時(shí)，針對(duì)系數(shù)矩陣為拉普拉斯矩陣的特殊線(xiàn)性方

7、程組，可以更快的求解，時(shí)間復(fù)雜度為O(m log n)。所以變形蟲(chóng)算法的時(shí)間復(fù)雜度的一般形式為O(km log n)，k為迭代次數(shù)。本文將重點(diǎn)研究和改進(jìn)變形蟲(chóng)算法來(lái)解決單源最短路徑和最大流問(wèn)題，以及在一些現(xiàn)實(shí)問(wèn)題中的應(yīng)用，創(chuàng)新的研究成果有以下幾個(gè)方面：
　　1、證明了多頭絨泡菌數(shù)學(xué)模型的收斂性和正確性，以及它的收斂速度，并將多頭絨泡菌的數(shù)學(xué)模型進(jìn)行改進(jìn)和離散化，形成原始的變形蟲(chóng)算法。對(duì)于2007年提出的多頭絨泡菌模型，其收斂過(guò)程一

8、直未得到充分的研究和證明。本文在原始模型的基礎(chǔ)上稍作完善，并通過(guò)不變集理論證明了它在權(quán)值為正數(shù)，初始狀態(tài)非0時(shí)，一定收斂于最短路徑的解，同時(shí)，其收斂速度與網(wǎng)絡(luò)的結(jié)構(gòu)有關(guān)。我們將這一模型離散化，形成變形蟲(chóng)算法的原始版本，通過(guò)實(shí)驗(yàn)驗(yàn)證，原始變形蟲(chóng)算法是一個(gè)解決單源最短路徑問(wèn)題的偽多項(xiàng)式算法，對(duì)于整數(shù)問(wèn)題，它的時(shí)間復(fù)雜度可以寫(xiě)為O(U m log2 n)。原始變形蟲(chóng)算法只是搭建了一個(gè)解決問(wèn)題的算法框架，體現(xiàn)了多頭絨泡菌模型的正反饋機(jī)制。而針對(duì)

9、不同問(wèn)題，算法還需要進(jìn)行相應(yīng)的改進(jìn)和優(yōu)化。
　　2、在原始變形蟲(chóng)算法基礎(chǔ)上，通過(guò)擴(kuò)展改進(jìn)，形成解決帶負(fù)權(quán)的單源最短路徑問(wèn)題的變形蟲(chóng)算法，并分析和比較它的求解效率，該算法優(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óng)算法基礎(chǔ)上，針對(duì)負(fù)權(quán)網(wǎng)絡(luò)的單源最短路徑問(wèn)題提出改進(jìn)和優(yōu)化方案，

10、得到時(shí)間復(fù)雜度為O(√nm log n)的算法。對(duì)于可能存在負(fù)權(quán)環(huán)的網(wǎng)絡(luò)，Bellman-Ford算法需要到最后一次迭代結(jié)束才能判定存在負(fù)環(huán)，對(duì)應(yīng)于算法的最壞情況，而變形蟲(chóng)算法可以在O(n0.Z m log n)內(nèi)檢測(cè)、定位和消除網(wǎng)絡(luò)中的所有負(fù)權(quán)環(huán)，并且不破壞網(wǎng)絡(luò)的連通性，這是其他算法都無(wú)法做到的，其中0.Z≈0.65。
　　3、針對(duì)最大流問(wèn)題模型，改進(jìn)變形蟲(chóng)算法解決最大流問(wèn)題，并分析和比較它的求解效率，該算法優(yōu)于Dinic算法，

11、同時(shí)還能得到網(wǎng)絡(luò)的所有最小割。目前網(wǎng)絡(luò)最大流問(wèn)題的算法時(shí)間復(fù)雜度的精確下界還沒(méi)有被找到，而流分解障礙 O(nm)作為該問(wèn)題中某一類(lèi)算法的時(shí)間復(fù)雜度下界，在很長(zhǎng)一段時(shí)間都沒(méi)有被突破。直到1998年首次得到O(min{n2/3。m1/2}m log(n2/m) log U)的算法。但所有達(dá)到或突破O(nm)時(shí)間界的算法都需要實(shí)現(xiàn)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)或者網(wǎng)絡(luò)變換操作，實(shí)際效率并不高，不具有實(shí)用性，較常用的算法仍然是具有O(n2 m)時(shí)間復(fù)雜度的Di