若干組合優(yōu)化問題的算法研究.pdf

1、組合優(yōu)化(Combinatorial optimization)是一門古老而又年輕的學科，著名數(shù)學家Fermat，Euler等都為其形成和發(fā)展做出過重要貢獻。二十世紀后半葉，伴隨著工業(yè)科技革命和現(xiàn)代管理科學的發(fā)展，特別是計算機技術的突飛猛進和在各行業(yè)的廣泛應用，組合優(yōu)化己壯大成為計算機科學與運籌學的一個獨立分支，一些數(shù)百年前數(shù)學家們偶然想到的問題和方法，已在網(wǎng)絡通信、物流管理、交通規(guī)劃等行業(yè)發(fā)揮了重要的作用，這是他們當時所不曾想到的。這

2、從另一方面寓示了這一學科的巨大前景。
　　 組合優(yōu)化問題的目標是從組合問題的可行解集中求出最優(yōu)解，通?？擅枋鰹椋毫瞀?{s1，s2，…，sn}為所有狀態(tài)構成的解空間，C(si為狀態(tài)si對應的目標函數(shù)值，要求尋找最優(yōu)解s*，使得對于所有的si∈Ω，有C(s*))=min{C(si)}。
　　 典型的組合優(yōu)化問題有旅行商問題、背包問題、裝箱問題、最小度生成樹問題、集合覆蓋問題等。這些問題描述非常簡單，并且有很強的工程代表性，

3、但最優(yōu)化求解很困難，其主要原因是求解這些問題的算法需要極長的運行時間與極大的存儲空間，以致根本不可能在現(xiàn)有計算機上實現(xiàn)，即所謂的“組合爆炸”。正是這些問題的代表性和復雜性激起了人們對組合優(yōu)化理論與算法的研究興趣。
　　 組合優(yōu)化問題中有一些是P類問題，人們可以分析利用其組合性質，發(fā)掘深層次的結構，進而設計出有效的算法求出問題的最優(yōu)解。不幸的是，許多重要問題是NP-hard，很難精確求解。當問題規(guī)模超過一定大小之后，即使超級計算機

4、也無能為力。這也是計算機算法和復雜度研究的長期課題，其有效求解直接影響到國民經(jīng)濟和國防建設的許多領域。因此，尋找求解這類問題的快速而有效的算法具有深刻的理論意義和普遍的實用價值。
　　 對于NP-hard問題，人們常常把研究的重點轉向在較短時間(多項式時間)內求一個可行的次優(yōu)解。事實上，關于啟發(fā)式算法有大量的文獻，并有著廣泛的應用。啟發(fā)式算法致命的弱點是對所求的解的質量沒有任何保障。事實上,對任何一個啟發(fā)函數(shù)，總有一些實例使其失

5、效，也就是說，所求解偏離最優(yōu)解甚遠。近似算法(Approximation Algorithm)彌補了啟發(fā)式算法的不足，它能夠界定所求解的質量。近似算法也是一類啟發(fā)式算法，但它給出了近似解與最優(yōu)解之比值的上界。
　　 另一方面，由于NP-hard問題的結構難以被解析的了解，人們常常在算法中引入隨機化技術，許多求解NP-hard問題的算法都可以看做是隨機算法。一般的說，隨機算法就是指計算過程受到隨機數(shù)影響的算法，它是對傳統(tǒng)確定性算法

6、設計思想的突破，目前已被廣泛應用在數(shù)論、計算幾何、圖論、并行處理和網(wǎng)絡路由等多個領域中。
　　 本文討論低度網(wǎng)絡設計問題、集合覆蓋問題和路徑規(guī)劃問題的算法與復雜度，設計它們的新求解算法。三個計算問題均以網(wǎng)絡與通信領域的實踐活動為應用背景，路經(jīng)規(guī)劃問題還直接用于機器人控制研究中。本文的主要研究工作和創(chuàng)新點：
　　 1.提出了有向無環(huán)圖上最小度生成樹(MDST)問題的一種精確算法。
　　 在設計通訊網(wǎng)絡時，常常會出現(xiàn)

7、這樣的情況，要求構建一個連接多個客戶終端的網(wǎng)絡，而可用的軟硬件設施往往對網(wǎng)絡的拓撲結構施加額外的約束。比如，計算機網(wǎng)絡領域中往往會碰到這樣的問題：給定一定數(shù)量的客戶端，它們通過某種特定的通訊協(xié)議進行互相通訊，這種協(xié)議對每一個客戶端可以同時打開的連接數(shù)目具有一定的約束。用圖論中的術語來描述，客戶端對應于圖中的頂點，網(wǎng)絡連接對應于圖中的邊。這種約束條件就轉化為對圖中頂點的最大度的限制。這種情形可以建模成最小度生成樹問題。給定一個無向圖G=(

8、V,E)，我們要求一棵生成樹T,使得T中頂點的最大度最小。該問題是哈密爾頓路問題的推廣，因此是NP-hard。本文給出了該問題在有向無環(huán)圖上的一種精確算法，并將該算法應用到最短時間廣播問題，改進了其近似比。
　　 2.提出了有向無環(huán)圖上帶度約束的最小生成樹問題的一個近似算法。
　　 與最小度生成樹問題密切相關的是最小度最小生成樹(MDMST)問題。在該問題中，圖的每條邊都有一個非負權值，或稱為費用，要求一棵最小生成樹T,

9、使得T的度在所有最小生成樹中最小。該問題在網(wǎng)絡設計、VLSI中都有廣泛應用。在構建通訊網(wǎng)絡時，往往不僅要降低每個節(jié)點的負載(節(jié)點的度)，同時也要降低網(wǎng)絡的構建費用(邊的權值)。MDMST問題自然而然的建模了這兩種互斥的要求。
　　 帶度約束的最小生成樹(BDMST)問題是MDMST問題的預算版本。我們給定一個度的界B≥1，要求一棵最小生成樹T,使得T的度不超過B。
　　 上述問題，對于無向版本，已有大量文獻。對于有向版本

10、，問題無疑復雜得多，這方面的研究成果也比較少，本文一部分工作正是致力于這類問題的有向圖情況。在該問題中，度和費用的要求是互斥的，我們給出了一個將度和費用進行折中的近似算法。
　　 3.提出了集合覆蓋問題的一種隨機近似算法。
　　 集合覆蓋問題在實踐中具有重要價值，多年來作為計算機算法研究的核心問題而被廣泛研究。與傳統(tǒng)的“確定”算法不同，本文給出了帶權集合覆蓋問題的一種“隨機”算法，并給出了算法期望意義下的近似比。由于算法

11、的隨機性，每次運行輸出的覆蓋集合都可能不同，因此，可以多次運行該算法得到一系列覆蓋，從中選擇費用最小的，該覆蓋很可能接近最優(yōu)解，甚至可能就是最優(yōu)解。又因為該算法的時間復雜度是線性的，這為算法的多次運行奠定了基礎。
　　 4.提出了規(guī)劃問題的一種狀態(tài)空間削減算法。
　　 作為人工智能的核心領域之一，規(guī)劃在航天技術、航線安排、商業(yè)策略、醫(yī)療優(yōu)化、自動控制、工程設計等眾多領域有著巨大的作用。
　　 狀態(tài)空間搜索是人工智

12、能的一個基本的普遍使用的技術。狀態(tài)空間一般被定義為一個有向圖。圖中的每條邊都有一個權值，或者叫做費用，搜索是指找一條由初始狀態(tài)到目標狀態(tài)的路徑，使得其總費用最小。
　　 傳統(tǒng)的狀態(tài)空間搜索算法的性能主要依賴于啟發(fā)函數(shù)的精度。然而，最近的研究表明，即使使用近乎完美的啟發(fā)函數(shù)，啟發(fā)式搜索仍然具有指數(shù)的時間復雜度。因此，改進搜索算法不能完全寄希望于設計更好的啟發(fā)函數(shù)，而應該另辟途徑。本文提出一種狀態(tài)空間削減技術，我們稱之為核心擴展方法

13、。該技術可以將原狀態(tài)空間圖削減成一個較小的狀態(tài)空間圖，同時保持了完全性和最優(yōu)性。而且，核心擴展方法可以與傳統(tǒng)的搜索算法結合使用，從而達到進一步加速搜索的目的。
　　 本文的進一步工作主要包括：
　　 1.一般有向圖上的低度網(wǎng)絡設計問題的算法研究。對于低度網(wǎng)絡設計問題，我們主要集中研究了有向無環(huán)圖上的情況，一般的有向圖情況將是我們進一步研究的方向之一。
　　 2.集合覆蓋問題的各種變體以及其對偶問題的隨機算法研究。