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

1、圖論問題是數(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ì)性的突破。
　　在單源最短路徑樹問題中，若不存在負權(quán)邊，經(jīng)典的Dijks

2、tra算法的時間復(fù)雜度達到O(m+n log n)，是該問題最快的算法之一。而當(dāng)網(wǎng)絡(luò)中存在負權(quán)邊時，最好的強多項式算法是Bellman-Ford算法，時間復(fù)雜度達到O(nm)，最好的弱多項式算法是縮放算法，時間復(fù)雜度達到O(√nm log U)。對于最大流問題，比較常用的算法為Dinic算法，時間復(fù)雜度為O(n2m)。該問題存在一個被稱為流分解障礙的O(nm)時間界，任何利用增載軌的算法都無法突破這個障礙。許多優(yōu)秀算法的時間復(fù)雜度已達到

3、或突破這個界限，但實現(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/2}m log(n2/m) log U)。該算法同樣用到了動態(tài)樹并且包含了大量的網(wǎng)絡(luò)變換的操作，因此算法

4、很復(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等人揭示了

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

6、法。
　　變形蟲算法是一種通過正反饋的演化規(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ù)矩陣為拉普拉斯矩陣的特殊線性方

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

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

9、不同問題，算法還需要進行相應(yīng)的改進和優(yōu)化。
　　2、在原始變形蟲算法基礎(chǔ)上，通過擴展改進，形成解決帶負權(quán)的單源最短路徑問題的變形蟲算法，并分析和比較它的求解效率，該算法優(yōu)于Bellman-Ford算法，同時還具有檢測、定位和消除網(wǎng)絡(luò)中所有的負權(quán)環(huán)的能力。Bellman-Ford算法可以在O(nm)時間內(nèi)求解帶負權(quán)的單源最短路徑，并判斷網(wǎng)絡(luò)中是否存在負環(huán)。本文在原始變形蟲算法基礎(chǔ)上，針對負權(quán)網(wǎng)絡(luò)的單源最短路徑問題提出改進和優(yōu)化方案，

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

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