TSP的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計(jì)_圖文

1、大連理工大學(xué)碩士學(xué)位論文TSP的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計(jì)姓名：李強(qiáng)申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：軟件工程指導(dǎo)教師：江賀20071215大連理工大學(xué)碩士學(xué)位論文摘要旅行商問(wèn)題（）是經(jīng)典的一難解組合優(yōu)化問(wèn)題之一，在交通、網(wǎng)絡(luò)、電路設(shè)計(jì)等方面有著廣泛的應(yīng)用背景。根據(jù)計(jì)算復(fù)雜性理論可知：對(duì)于一難解問(wèn)題，除非，否則不存在多項(xiàng)式時(shí)間內(nèi)得到最優(yōu)解的精確算法。因此對(duì)于大規(guī)模的實(shí)例，求解它的高效啟發(fā)式算法設(shè)計(jì)一直是計(jì)算機(jī)科學(xué)研究的熱點(diǎn)。骨架、脂肪等作為描述結(jié)構(gòu)特征的工具，對(duì)啟發(fā)式算法設(shè)計(jì)有著重要的意義，已經(jīng)成為目前研究問(wèn)題的主要研究領(lǐng)域。本文首先對(duì)問(wèn)題的研究現(xiàn)狀進(jìn)行了介紹和分析，指出在結(jié)構(gòu)特征工具的研究上的不足之

2、處。通過(guò)構(gòu)造偏移實(shí)例的技巧，分析了問(wèn)題的脂肪計(jì)算復(fù)雜性，并首次給出了獲取的脂肪是一難解的理論證明，即在的假設(shè)下，不存在算法可以在多項(xiàng)式時(shí)間內(nèi)獲得完整脂肪。在此基礎(chǔ)上，通過(guò)分析問(wèn)題局部最優(yōu)解與脂肪的關(guān)系，給出了求解問(wèn)題新的元啟發(fā)式算法一動(dòng)態(tài)候選集搜索算法。利用該算法，本文改進(jìn)了目前求解問(wèn)題最好的算法之一的。然后，本文在分析局部最優(yōu)解與全局最優(yōu)解關(guān)系的基礎(chǔ)上，提出一種新的描述結(jié)構(gòu)特征工具擾邊。通過(guò)假設(shè)可以構(gòu)造多項(xiàng)式時(shí)間內(nèi)的算法求得擾邊，進(jìn)而引出可以在多項(xiàng)式時(shí)間內(nèi)求的問(wèn)題的最優(yōu)解，用反證法給出了求解擾邊是一難的理論證明。通過(guò)試驗(yàn)分析，發(fā)現(xiàn)通過(guò)對(duì)局部最優(yōu)解之間的相互操作，可以求得有效模擬擾邊的“近似擾

3、邊”。并在此基礎(chǔ)上，提出了基于近似擾邊的元啟發(fā)式算法框架（）。最后同樣在上對(duì)算法框架進(jìn)行了實(shí)現(xiàn)。關(guān)鍵詞：旅行商閘題；啟發(fā)式算法；脂肪；擾邊的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計(jì)始（），髓伍，鵲，刪，陽(yáng)。，（）小張，（、：；獨(dú)創(chuàng)性說(shuō)明作者鄭重聲明：本碩士學(xué)位論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫的研究成果，也不包含為獲得大連理工大學(xué)或者其他單位的學(xué)位或證書所使用過(guò)的材料。與我一同工作的同志對(duì)本研究所做的貢獻(xiàn)均已在論文中做了明確的說(shuō)明并表示了謝意。作者簽名：盜絲日期：哩：蘭：多大連理工大學(xué)碩士研究生學(xué)位論文大連理

4、工大學(xué)學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者及指導(dǎo)教師完全了解“大連理工大學(xué)碩士、博士學(xué)位論文版權(quán)使用規(guī)定”，同意大連理工大學(xué)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交學(xué)位論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)大連理工大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，也可采用影印、縮印或掃描等復(fù)制手段保存和匯編學(xué)位論文。作者躲導(dǎo)師簽名：翅墮丑業(yè)月塹目絲庫(kù)。堡月暨目大連理工大學(xué)碩士學(xué)位論文緒論（）問(wèn)題”堤為人們所廣泛研究的典型組合優(yōu)化問(wèn)題，問(wèn)題形式化描述為：給定無(wú)向加權(quán)圖（礦，丘們，為頂點(diǎn)集，礦，為邊集，睜表示邊的數(shù)目，：呻為邊權(quán)函數(shù)。實(shí)例（記為（，計(jì)）的可行解為，玨矗，其中，且對(duì)，邊

5、，可行解的目標(biāo)函數(shù)值定義為；：?！?，。），的目標(biāo)是尋求目標(biāo)函數(shù)值最小解，即滿足帕）。，（川），其中（）為中所有環(huán)路的集合。問(wèn)題與調(diào)度和劃分等問(wèn)題相關(guān)，廣泛應(yīng)用于芯片設(shè)計(jì)、電路版布局、機(jī)器人控制、車輛選路等領(lǐng)域，其廣闊的通用性使之成為組合優(yōu)化的重要代表。研究背景和課題意義組合優(yōu)化問(wèn)題的目標(biāo)是從組合問(wèn)題的可行解中求出最優(yōu)解。在現(xiàn)實(shí)世界里存在大量的組合優(yōu)化問(wèn)題，其中許多問(wèn)題（如：旅行商問(wèn)題、圖著色問(wèn)題、分配問(wèn)題、調(diào)度問(wèn)題、布線問(wèn)題及路由選擇問(wèn)題等）至今沒(méi)有找到有效地多項(xiàng)式算法，這些問(wèn)題已被證明是完全問(wèn)題。優(yōu)化問(wèn)題有三個(gè)基本要素：變量、約束和目標(biāo)函數(shù)。在求解過(guò)程中，選定的基本參數(shù)稱為變量；對(duì)變量取值的

6、限制成為約束；表示可行方案衡量標(biāo)準(zhǔn)的函數(shù)成為目標(biāo)函數(shù)。是作為最典型的難問(wèn)題之一具有古老的歷史。最早的記錄來(lái)自于年歐拉研究的騎士周游問(wèn)題，即對(duì)于象棋棋盤中的個(gè)方格，走訪每個(gè)方格一次且僅一次。公司于年首次引入問(wèn)題，公司的聲譽(yù)使得成為一個(gè)知名且流行的問(wèn)題。問(wèn)題在當(dāng)時(shí)引起注意的另一個(gè)原因，是由于線性規(guī)劃這一新方法的出現(xiàn)以及人們?cè)噲D用它求解組合優(yōu)化問(wèn)題。根據(jù)計(jì)算復(fù)雜性理論【】可知：對(duì)于難解問(wèn)題，除非，否則不存在多項(xiàng)式時(shí)問(wèn)內(nèi)得到最優(yōu)解的完全算法。由確定型圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可識(shí)別的一切語(yǔ)言的集合被稱為類語(yǔ)言。由確定型圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可解的一切判定問(wèn)題的集合稱為類問(wèn)題。由非確定型圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可識(shí)

7、別的一切語(yǔ)言稱為類語(yǔ)言。由非確定型圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可計(jì)算的判定問(wèn)題類稱做問(wèn)題類。如果對(duì)類問(wèn)題的解進(jìn)行驗(yàn)證，可在多項(xiàng)式時(shí)間內(nèi)完成。習(xí)慣上，簡(jiǎn)稱和問(wèn)題。雖然現(xiàn)在還不能證明或者，但是還有一系列的特殊問(wèn)題，這類問(wèn)題的特殊性質(zhì)使得很多人相信。這類特殊的問(wèn)題就是完全問(wèn)題（問(wèn)的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計(jì)題，代表）。問(wèn)題存在著一個(gè)共同的性質(zhì)，即如果一個(gè)問(wèn)題存在多項(xiàng)式時(shí)間的算法，則所有的問(wèn)題都可以在多項(xiàng)式時(shí)間內(nèi)求解，即成立。這是因?yàn)?，每一個(gè)問(wèn)題都可以在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化成任何一個(gè)問(wèn)題。比如前面說(shuō)的哈密爾頓回路問(wèn)題就是一個(gè)問(wèn)題。問(wèn)題的歷史并不久，在年找到了第一個(gè)問(wèn)題，此后人們又陸續(xù)發(fā)現(xiàn)很多問(wèn)題，現(xiàn)在可能已經(jīng)有

8、多個(gè)了。所以，一般認(rèn)為問(wèn)題是難解的問(wèn)題，因?yàn)樗惶赡艽嬖谝粋€(gè)多項(xiàng)式時(shí)間的算法。問(wèn)題有著廣泛的應(yīng)用背景，在文獻(xiàn)】提到的電路板鉆孔應(yīng)用相當(dāng)于，個(gè)城市的；在文獻(xiàn)】中提及的射線檢晶器例子相當(dāng)于，個(gè)城市的：而在文獻(xiàn)報(bào)道的構(gòu)造有萬(wàn)個(gè)“城市”之多。因此，研究問(wèn)題對(duì)解決現(xiàn)實(shí)中的一些問(wèn)題有著重要的意義，而且作為組合優(yōu)化問(wèn)題的典型代表，對(duì)問(wèn)題的研究對(duì)其他相關(guān)的難解問(wèn)題有著重要的借鑒和指導(dǎo)作用。國(guó)內(nèi)外研究現(xiàn)狀等人早在年就求解過(guò)的旅行商問(wèn)題最優(yōu)解。年代中期對(duì)于多面體理論的研究，產(chǎn)生了一些比較有效的不等式約束，如：子回路消去不等式（）、梳子不等式（）、團(tuán)樹不等式（等等。）在過(guò)去的幾十年里，人們又相繼研究了一些可產(chǎn)生的

9、近似解的算法，包括近鄰法（）、貪婪法（）、最近插入法（）、最遠(yuǎn)插入法（）、雙最小生成樹法（）、剝離法（）、空間填充曲線法（）以及其他由，等人提供的算法。這些算法大多假定城市與某種標(biāo)準(zhǔn)距離度量下的平面上的點(diǎn)相對(duì)應(yīng)。還有一類算法（例如、和算法）旨在進(jìn)行局部?jī)?yōu)化：通過(guò)施加局部擾動(dòng)改進(jìn)一條路徑。問(wèn)題同時(shí)也成為世紀(jì)年代和年代演化算法領(lǐng)域的一個(gè)研究目標(biāo)，并且，幾乎演化算法的每個(gè)會(huì)議都會(huì)有一些關(guān)于的論文。比較這些方法，尤其是它們所采用的表示方式和變化算子對(duì)研究問(wèn)題有著重要的意義?！繄?bào)道了在工作站的單個(gè)處理機(jī)上用小時(shí)解決了個(gè)城市的：】?jī)H在到個(gè)小時(shí)之內(nèi)解決了同樣的問(wèn)題，但采用的是包含個(gè)結(jié)點(diǎn)機(jī)的并行實(shí)現(xiàn)；】貝在一

10、臺(tái)工作站用了大約分鐘大連理工大學(xué)碩士學(xué)位論文來(lái)求解個(gè)城市的。這些描述大都缺乏最終解質(zhì)量的比較，但都表明演化算法在求解大型（例如，個(gè)以上城市）時(shí)速度太慢。它們所提供的性能結(jié)果很大程度上依賴于一些具體細(xì)節(jié)，包括種群規(guī)模、演化代數(shù)、城市數(shù)等等。并且，許多結(jié)果只適用于相對(duì)較小的（如最多個(gè)城市）。文獻(xiàn)【】中觀察所見：看起來(lái)少于個(gè)城市的例子很適合于全局優(yōu)化技術(shù)求解。但是，要考慮城市規(guī)模比這大得多的實(shí)例則需要采用啟發(fā)式算法。國(guó)外的研究現(xiàn)狀對(duì)于旅行商問(wèn)題的一些特殊情況，國(guó)外研究出一系列較為成熟的結(jié)果，如：機(jī)器排序問(wèn)題（等，）、二分圖情形（，）、平面旅行商問(wèn)題中的一些特例（，）等等。由于可解情形的結(jié)果都是成熟的

11、定理，因此嚴(yán)格來(lái)說(shuō)，已不屬于算法研究的范疇。而對(duì)于規(guī)模比較大的一般實(shí)例而言，目前國(guó)外還沒(méi)有提出最常用有效的算法求的問(wèn)題的最優(yōu)解。目前，學(xué)者認(rèn)同最簡(jiǎn)單有效的是基于算法的算法，算法是在經(jīng)典算法的基礎(chǔ)上提出的最高效局部搜索算法，是目前已知的求解問(wèn)題最好算法。如目前最大的已成功求解的例子（城市數(shù)為），其中就用到了算法。它的求解過(guò)程如下：（）用算法求的近似解，；（）用線性規(guī)劃的方法求得解的下限為，；（）證明在，和，之間不存在解。整個(gè)線性規(guī)劃求解（不包括用近似解算法求解）的過(guò)程是在工作站上完成的，折算成個(gè)人計(jì)算機(jī)（）所消耗的時(shí)間為年。國(guó)內(nèi)的研究現(xiàn)狀國(guó)內(nèi)對(duì)的研究一般多為對(duì)某種算法策略的改進(jìn)，比如對(duì)遺傳算法【

12、”、模擬退火【、禁忌搜索【等算法的局部改進(jìn)。其中比較好的是多級(jí)歸約算法【、求解問(wèn)題的并集搜索的新宏啟發(fā)算法等。多級(jí)歸約算法是一種通過(guò)對(duì)問(wèn)題的局部最優(yōu)解與全局最優(yōu)解之間關(guān)系的分析，發(fā)現(xiàn)對(duì)局部最優(yōu)解的簡(jiǎn)單的相交操作能以很高的概率得到全局最優(yōu)解的部分解。利用這些部分解可以大大縮減原問(wèn)題的搜索空間，同時(shí)也不會(huì)降低搜索的性能。再通過(guò)多次歸約使問(wèn)題的規(guī)模降到足夠小，然后對(duì)這個(gè)較小規(guī)模的實(shí)例直接用已有的算法求解，最后通過(guò)相反的次序拼接部分解，最終得到一個(gè)合法解。論文最后的試驗(yàn)表明，采用多級(jí)歸約算法求得的解的質(zhì)量甚至好于目前求解問(wèn)題最好的算法。的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計(jì)求解問(wèn)題并集搜索的新宏啟發(fā)式算法是利

13、用問(wèn)題解的概率統(tǒng)計(jì)模型，分析了問(wèn)題的局部最優(yōu)解并集的性質(zhì)，發(fā)現(xiàn)局部最優(yōu)解的并集規(guī)模較小且包含了絕大多數(shù)全局最優(yōu)解的邊。利用該性質(zhì)，將局部最優(yōu)解并集作為啟發(fā)集，并調(diào)用局部搜索算子在其上求解問(wèn)題，由此得到一種稱為并集搜索的新宏啟發(fā)算法。利用該算法改進(jìn)的問(wèn)題算法的、在（附錄）中典型實(shí)例上的試驗(yàn)結(jié)果表明新算法在求解的質(zhì)量上有了較顯著的提高。本文的主要工作本文針對(duì)目前的描述結(jié)構(gòu)特征的工具研究現(xiàn)狀和不足，主要做了以下的三個(gè)方面的工作：（）介紹了的一些概念，并針對(duì)目前的研究熱點(diǎn)描述結(jié)構(gòu)特征工具的研究現(xiàn)狀進(jìn)行了介紹和分析，指出不足之處。（）分析了問(wèn)題的脂肪計(jì)算復(fù)雜性，通過(guò)構(gòu)造偏移實(shí)例的技巧，首次給出了獲取的脂

14、肪是一難解的理論證明，即在尸的假設(shè)下，不存在算法可以在多項(xiàng)式時(shí)間內(nèi)獲得完整脂肪。在此基礎(chǔ)上，通過(guò)分析問(wèn)題局部最優(yōu)解與脂肪的關(guān)系，給出了求解問(wèn)題新的元啟發(fā)式算法一動(dòng)態(tài)候選集搜索算法。利用該算法，本文改進(jìn)了目前求解問(wèn)題最好的算法之一的。（）首次提出一種新的描述結(jié)構(gòu)特征工具擾邊。本文首先在分析了全局和局部最優(yōu)解關(guān)系的基礎(chǔ)上，給出了求解擾邊是一難得理論證明。然后，通過(guò)試驗(yàn)分析，通過(guò)對(duì)局部最優(yōu)解之間的相互操作，求得可以有效模擬擾邊的“近似擾邊”。并在此基礎(chǔ)上，提出了基于近似擾邊的元啟發(fā)式算法框架（）。最后在上對(duì)算法框架進(jìn)行了實(shí)現(xiàn)。本文最后，對(duì)工作做了總結(jié)并對(duì)描述結(jié)構(gòu)特征工具以后的研究做了展望。本文的結(jié)構(gòu)

15、本文第章為緒論，介紹了研究領(lǐng)域的背景、國(guó)內(nèi)外的研究現(xiàn)狀和本文的主要內(nèi)容：第章為問(wèn)題的現(xiàn)狀研究，包括啟發(fā)式算法的介紹和目前的研究熱點(diǎn)結(jié)構(gòu)特征工具的研究現(xiàn)狀；第章為脂肪的理論分析與啟發(fā)式算法設(shè)計(jì)；第章為擾邊的理論分析與啟發(fā)式算法設(shè)計(jì)；最后在結(jié)論里對(duì)本文進(jìn)行了總結(jié)并對(duì)以后的研究作了展望。一一大連理工大學(xué)碩士學(xué)位論文問(wèn)題的研究現(xiàn)狀問(wèn)題是一個(gè)典型的組合優(yōu)化問(wèn)題，解的空間很大，窮舉所有的解根本不可能也不現(xiàn)實(shí)，其可能的路徑數(shù)目與城市數(shù)目是成指數(shù)型增長(zhǎng)的。傳統(tǒng)方法求解問(wèn)題，采用窮舉法。但因?yàn)樗阉骺臻g太大，因此到達(dá)一定規(guī)模，用窮舉法不現(xiàn)實(shí)。的搜索空間是給定的個(gè)城市的排列的集合，因此有一不同的排列組合。但考慮到，

16、如果不考慮起始城市的話，每條路徑都能用種不同的方法表示（對(duì)于一個(gè)對(duì)稱）。如路徑，同時(shí)可以包括序列、一等種序列。因此的搜索空間是悻（呻（）！。已經(jīng)被證明了是屬于難的問(wèn)題，而根據(jù)計(jì)算復(fù)雜性理論可知：對(duì)于一難解問(wèn)題，除非尸，否則不存在多項(xiàng)式時(shí)間內(nèi)得到最優(yōu)解的完全算法。因而對(duì)大規(guī)模問(wèn)題，人們尋求往往是在可接受的計(jì)算時(shí)間內(nèi)能得到（在解的性能上）可接受的近似解的啟發(fā)式算法（）。問(wèn)題的啟發(fā)式算法問(wèn)題的啟發(fā)式算法可以分為兩類：環(huán)路構(gòu)造算法和環(huán)路改進(jìn)算法。前者從某個(gè)非法解開始，通過(guò)某種增廣策略逐步改變?cè)摻?，直到得到一個(gè)合法解為止。環(huán)路構(gòu)造算法包括最近鄰、貪心算法、等。環(huán)路改進(jìn)算法則在給定初始的合法解之后，使用某

17、種策略來(lái)改進(jìn)初始解。這些策略包括局部搜索、禁忌搜索、模擬退火、遺傳算法等。、是最常見也是最常用的環(huán)路改進(jìn)算法，它們不僅可以單獨(dú)用來(lái)求解問(wèn)題，也可以作為局部?jī)?yōu)化算子而廣泛應(yīng)用于其他環(huán)路改迸算法。禁忌搜索中的算法在相當(dāng)長(zhǎng)的一段時(shí)間內(nèi)是求解問(wèn)題最好的算法，改進(jìn)的算法依然目前是求解問(wèn)題最好的局部搜索算法。的啟發(fā)式算法均可以通過(guò)兩個(gè)要素來(lái)衡量：運(yùn)行時(shí)間和解的質(zhì)量（即環(huán)路的長(zhǎng)度）。在算法設(shè)計(jì)中，每種啟發(fā)式算法都是在運(yùn)行時(shí)間和解的質(zhì)量之間進(jìn)行平衡。在后面的敘述中，本文集中于那些具有代表性的應(yīng)用廣泛的啟發(fā)式算法，較少介紹那些使用范圍狹窄僅僅針對(duì)某種類型實(shí)例的特定算法。環(huán)路構(gòu)造算法本節(jié)詳細(xì)討論的環(huán)路構(gòu)造算法包括

18、最近鄰算法、貪心算法、算法和算法等。不同的算法在局部搜索中具有不同的作用。前三種環(huán)路構(gòu)造算法為環(huán)路改進(jìn)算法提供了在運(yùn)行時(shí)間上可行的較好初始回路。通過(guò)衡量他們?cè)诃h(huán)路改進(jìn)算法的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計(jì)中的不同效果，可以為算法設(shè)計(jì)提供許多好的思路。第四種環(huán)路構(gòu)造算法在一定程度上代表了目前環(huán)路構(gòu)造算法所能取得的最好結(jié)果，因此其可以作為其他算法的一個(gè)參照算法。最近鄰問(wèn)題的啟發(fā)式算法中最著名也是最自然的是最近鄰算法（，）。在這個(gè)算法中，每次選擇一個(gè)距離當(dāng)前頂點(diǎn)最近的沒(méi)有被訪問(wèn)過(guò)的頂點(diǎn)。利用這一方法構(gòu)造了一個(gè)頂點(diǎn)序列（】），（），以（。），其中初始頂點(diǎn)攻（。）的選擇完全隨機(jī)。對(duì)應(yīng)的環(huán)路按照這一序列依次訪

19、問(wèn)各個(gè)頂點(diǎn)，在訪問(wèn)后回到（）。以上所述的最近鄰算法的時(shí)間復(fù)雜度為（）。對(duì)于滿足三角不等式的那些問(wèn)題而言，算法的解滿足（）?。ǎㄒ裕ｋm然如此，實(shí)際上對(duì)于大量的實(shí)例而言，算法的系數(shù)為（，）。：、】等人分別實(shí)現(xiàn)了標(biāo)準(zhǔn)的最近鄰算法?！康热诉€提出了最近鄰算法的不同變體（包括、等）。、表給出了的最近鄰算法實(shí)驗(yàn)結(jié)果。為了與隨機(jī)歐氏空間上的實(shí)例相比較，的實(shí)例依照表的規(guī)則給出。從表中，我們可以看到：最近鄰算法在不同種類的實(shí)例上的運(yùn)行時(shí)間都很短，而解的質(zhì)量通常超過(guò)下界左右。表最近鄰算法的試驗(yàn)性能問(wèn)題規(guī)模大連理工大學(xué)碩士學(xué)位論文表中實(shí)例的參照標(biāo)準(zhǔn)解空間實(shí)例名稱，貪心算法有些學(xué)者將最近鄰算法稱為貪心算法，但是一般

20、而言，問(wèn)題的貪心算法特指以下矩陣胚理論（）的貪心算法。在此啟發(fā)式算法，將實(shí)例看成一個(gè)完全圖。一條環(huán)路就是該完全圖上的一條環(huán)路，也就是說(shuō)一組邊的集合，其中每個(gè)頂點(diǎn)的度為。算法在構(gòu)造環(huán)路時(shí)，每次加入一條新的邊。算法從最短的邊開始，依次加入剩余可用邊中最短的邊。這里，一條邊是可用的，當(dāng)且僅當(dāng)它不在環(huán)路中并且加入后不會(huì)產(chǎn)生個(gè)度為的頂點(diǎn)或者邊數(shù)小于的環(huán)路。在運(yùn)行過(guò)程中，算法將生成一系列的環(huán)路片斷。因此該算法也被稱為多片斷（）啟發(fā)式算法。問(wèn)題的貪心算法的運(yùn)行時(shí)間復(fù)雜度為（），因此相對(duì)而言，比最近鄰算法慢一些。然而，另一方面，在最壞情況下，它所生成的環(huán)路比最近鄰方法要好。因此，從這里可以看出算法設(shè)計(jì)的一個(gè)基

21、本規(guī)律：算法設(shè)計(jì)總是在尋求運(yùn)行時(shí)間和求解質(zhì)量之間的平衡，對(duì)于一個(gè)好的成熟的算法而言，其運(yùn)行時(shí)間與求解質(zhì)量永遠(yuǎn)是一對(duì)矛盾。如何在這一對(duì)矛盾中間取舍，是算法設(shè)計(jì)人員所要面臨重要課題。一個(gè)好的算法，總是需要在某方面做出犧牲，因此獲得另一方面性能的改進(jìn)。這種取舍通常依賴于具體問(wèn)題的特性和求解問(wèn)題的客觀條件。例如，在類似交通調(diào)度這樣的在線問(wèn)題，其要求算法的時(shí)效性較強(qiáng)，在這個(gè)時(shí)候就應(yīng)該選擇運(yùn)行速度快的算法，即使在解的質(zhì)量方面略有下降也可以接受。而在類似電路板印刷這樣的離線問(wèn)題，通常的時(shí)效性要求較低，而對(duì)算法的求解質(zhì)量要求較高，這個(gè)時(shí)候就應(yīng)該選擇運(yùn)行時(shí)間略長(zhǎng)而解的質(zhì)量更高的算法。因此，判斷一個(gè)算法的優(yōu)劣，需

22、要在運(yùn)行時(shí)間和求解質(zhì)量?jī)蓚€(gè)方面進(jìn)行綜合考慮，在不同的情況下，算法的適用性不同。對(duì)于滿足三角不等式的那些問(wèn)題實(shí)例而言，貪心算法所獲得解滿足（）（）（）療）。對(duì)于己知最壞的例子，貪心算法的系數(shù)也僅在（）。的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計(jì)表給出了的貪心算法實(shí)驗(yàn)結(jié)果。對(duì)于隨機(jī)歐氏空間上的實(shí)例而言，算法的性能隨著實(shí)例規(guī)模的增加而逐漸上升，運(yùn)行時(shí)間迅速上升。對(duì)于隨機(jī)歐氏空間上的實(shí)例而言，算法的性能隨著實(shí)例規(guī)模的增加而逐漸下降。算法在實(shí)例上的結(jié)果與隨機(jī)歐氏空間上的實(shí)例類似。而在隨機(jī)距離矩陣實(shí)例上，算法的性能隨著實(shí)例規(guī)模的增加而迅速下降（環(huán)路超出下界的百分比從迅速上升到）。表貪心算法的試驗(yàn)性能！生：?。?！問(wèn)題規(guī)

23、模蘭翌塑里型堡墮！嬰竺堡！受塑（）啟發(fā)式算法源自于提出一個(gè)求解車輛調(diào)度的通用算法】。在問(wèn)題中，算法從一個(gè)偽環(huán)路（）開始。該偽環(huán)路以一個(gè)隨機(jī)選定的頂點(diǎn)作為軸心（），訪問(wèn)一個(gè)頂點(diǎn)后，在訪問(wèn)下一個(gè)頂點(diǎn)前，商人都回到軸心。（換句話說(shuō)，算法從一個(gè)開始，在這個(gè)圖上，每一個(gè)非軸心頂點(diǎn)都與軸心頂點(diǎn)之間有兩條邊相連）。對(duì)于每對(duì)非軸心頂點(diǎn)，結(jié)余（）表示商人直接從其中一個(gè)到另外一個(gè)非軸心頂點(diǎn)而不經(jīng)過(guò)軸心時(shí)總的環(huán)路可以縮短的距離。接下來(lái)，類似于貪心算法的處理方法，算法處理按照結(jié)余非增的順序依次處理非軸心頂點(diǎn)，只要它不會(huì)生成一個(gè)非軸心頂點(diǎn)的環(huán)路或者導(dǎo)致某個(gè)非軸心頂點(diǎn)和多個(gè)（多于）的非軸心頂點(diǎn)相鄰。該構(gòu)造算法在僅有兩個(gè)非

24、軸心頂點(diǎn)和軸心相鄰時(shí)結(jié)一一大連理工大學(xué)碩士學(xué)位論文束，此時(shí)算法得到一個(gè)完整的環(huán)路。與貪心算法類似，問(wèn)題的算法的運(yùn)行時(shí)間復(fù)雜度為（）。對(duì)于滿足三角不等式的問(wèn)題實(shí)例，算法的理論界是（）（），常數(shù)因子是貪心算法倍。然而，對(duì)于已知的最壞的情況，算法的系數(shù)與貪心算法相同，也是（）。表給出了等人在國(guó)際競(jìng)賽【】中提供的算法的實(shí)驗(yàn)性能。從表中可以看出，對(duì)于隨機(jī)歐氏空間上的實(shí)例麗言，算法的性能隨著實(shí)例規(guī)模的增加基本穩(wěn)定（環(huán)路長(zhǎng)度超出下界左右），運(yùn)行時(shí)間迅速上升。對(duì)于隨機(jī)歐氏空間上的實(shí)例而言，算法的性能隨著實(shí)例規(guī)模的增加而逐漸下降。算法在實(shí)例上的結(jié)果隨著實(shí)例規(guī)模增加而逐漸上升（環(huán)路超出下界的百分比從下降到）。表算

25、法的試驗(yàn)性能！墊：！：！曼翌！墮翌！墮堡！墮翌塑堡笪！竺！塑墊！問(wèn)題規(guī)模算法前面的三個(gè)算法在滿足三角不等式的情況下，最壞情況下算法的理論界的系數(shù)都是的函數(shù)。沒(méi)有排除有更好性能算法存在的可能性，實(shí)際上，許多算法都可以取得好的多的性能。例如，等提出雙重最小生成樹（），最近鄰插入（），和最近鄰擴(kuò)展（）等，在滿足三角不等式的情況下，算法在最壞情況下的理論界系數(shù)為。并且，他們通過(guò)構(gòu)造大的實(shí)例，指的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計(jì)出該理論界系數(shù)不能被進(jìn)一步提高。由于這些算法都可以歸類于最近鄰算法、貪心算法、，因此本文中不再詳細(xì)討論，盡管他們?cè)谧顗那闆r下的性能更好。下面要介紹的算法在最壞的情況下理論界的系數(shù)為（

26、對(duì)于滿足三角不等式的實(shí)例而言）。即便是對(duì)于歐氏平面上的問(wèn)題而言，這個(gè)理論界也是非常好的。的基本算法框架如下：首先，為所有的頂點(diǎn)構(gòu)造一棵最小生成樹，注意這樣的一棵最小生成樹的長(zhǎng)度比最優(yōu)環(huán)路短，因?yàn)閯h除最優(yōu)環(huán)路上的任意一邊即可得到一個(gè)生成樹；其次，對(duì)于最小生成樹上的度為奇數(shù)的頂點(diǎn)，計(jì)算一個(gè)最小長(zhǎng)度的匹配，容易證明：對(duì)于滿足三角不等式的實(shí)例，該匹配的長(zhǎng)度不超過(guò)（，）。匹配和最小生成樹構(gòu)成了一個(gè)連通圖，在該圖上，任意一個(gè)頂點(diǎn)的度均為偶數(shù)。這樣，這個(gè)圖上必定包含了一個(gè)歐拉回路（），也就是說(shuō)一個(gè)回路經(jīng)過(guò)每條邊一次且剛好一次，并且這樣的回路易于獲得。這樣一條環(huán)路可以通過(guò)遍歷該歐氏回路并利用捷徑（）避免多次訪

27、問(wèn)同一個(gè)頂點(diǎn)而得到，顯然該環(huán)路長(zhǎng)度不超過(guò)該歐拉回路。（一條捷徑用兩個(gè)頂點(diǎn)之間的直接連邊代替他們之間的一條路徑，由三角不等式可知，該直接邊的長(zhǎng)度小于它所替代的路徑）相對(duì)其它的環(huán)路構(gòu)造算法而言，算法不僅在最壞情況下的理論界更好，而且在實(shí)際運(yùn)用中，通過(guò)精心選擇捷徑，所能獲得的環(huán)路質(zhì)量也確實(shí)更好。算法的運(yùn)行時(shí)間相對(duì)于最近鄰、貪心算法、而言更長(zhǎng)。這主要?dú)w結(jié)于算法中匹配一步所需的時(shí)間為。（行），而其他的三種算法的總的運(yùn)行時(shí)間不超過(guò)（玎）。理論上說(shuō)這種運(yùn)行時(shí)間上的差距可以被縮小：一種具有相同理論界的算法的變種，通過(guò)使用基于可擴(kuò)展匹配算法并且匹配在長(zhǎng)度小于（珂）最優(yōu)匹配時(shí)立即中止，該變種的時(shí)間復(fù)雜度為（）。然

28、而，該種方法始終未被實(shí)際編碼實(shí)現(xiàn)過(guò)，基于局部搜索的環(huán)路改進(jìn)算法的卓越性能使得這樣編碼實(shí)現(xiàn)的意義不大。表給出了算法的實(shí)驗(yàn)性能。從表中，我們看到，算法在各種實(shí)例上的環(huán)路長(zhǎng)度超過(guò)下界均不到。而相對(duì)于其他的三種環(huán)路構(gòu)造算法，算法的運(yùn)行時(shí)間要多得多。下面，我們對(duì)四種環(huán)路構(gòu)造算法的性能進(jìn)行對(duì)比。對(duì)于隨機(jī)歐氏平面上的實(shí)例的情況，四種環(huán)路構(gòu)造算法所求得的解的長(zhǎng)度均逼近超出，下界，其中算法的解超出下界不到。對(duì)于其余的三個(gè)環(huán)路構(gòu)造算法而言，隨著實(shí)例的規(guī)模的增加，算法的解的質(zhì)量的變化比較大。算法在實(shí)例的規(guī)模為時(shí)的解的質(zhì)量與實(shí)例的規(guī)模很大時(shí)候的解的質(zhì)量之間沒(méi)有明顯關(guān)聯(lián)。特別是，對(duì)于貪心算法，它的解的平均距離從（實(shí)例規(guī)

29、模為時(shí)）下降至（實(shí)例規(guī)模為，）。大連理工大學(xué)碩士學(xué)位論文就運(yùn)行時(shí)間而言，算法的增長(zhǎng)速度如預(yù)期的超過(guò)挖。其他的環(huán)路構(gòu)造算法的運(yùn)行時(shí)間增長(zhǎng)速度低于，從實(shí)驗(yàn)的角度來(lái)看，運(yùn)行時(shí)間應(yīng)該在（功，盡管當(dāng)時(shí)，由于內(nèi)存的容量的限制，算法的運(yùn)行時(shí)間迅猛上升。即使在這種情況下，最近鄰，貪心算法和中最慢的一個(gè)也只需要大約秒鐘時(shí)間來(lái)求解，個(gè)頂點(diǎn)的實(shí)例。因此，算法在解的性能上可以作為其他環(huán)路構(gòu)造算法的一個(gè)參照，面其他的三種環(huán)路構(gòu)造算法由于運(yùn)行時(shí)間短，可以用于環(huán)路改進(jìn)算法以生成初始環(huán)路。表算法的試驗(yàn)性能三生：?。?！問(wèn)題規(guī)模里型堊型堡生嬰塑堡墮曼塑塑里塑平均運(yùn)行時(shí)間（秒）環(huán)路改進(jìn)算法環(huán)路改進(jìn)算法包括局部搜索及其變體、禁忌搜索

30、、模擬退火、遺傳算法等。、是最常見也是最常用的環(huán)路改進(jìn)算法，它們不僅可以單獨(dú)用來(lái)求解問(wèn)題，也可以作為局部?jī)?yōu)化算子而廣泛應(yīng)用于其他環(huán)路改進(jìn)算法。禁忌搜索中的算法在相當(dāng)長(zhǎng)的一段時(shí)間內(nèi)是求解問(wèn)題最好的算法，改進(jìn)的算法（）依然目前是求解問(wèn)題最好的局部搜索算法。模擬退火和遺傳算法也被應(yīng)用于問(wèn)題的求解，并取得了相當(dāng)好的實(shí)驗(yàn)性能。特別是遺傳算法在年間一直是求解問(wèn)題最好的算法，直到算法的出現(xiàn)。的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計(jì)局部搜索在本節(jié)中，我們考慮問(wèn)題的基于環(huán)路改進(jìn)的啟發(fā)式算法。這類算法通過(guò)對(duì)環(huán)路的一系列操作（交換或移動(dòng)），將一個(gè)環(huán)路轉(zhuǎn)換成另外一個(gè)環(huán)路。給定一個(gè)可行環(huán)路，算法對(duì)其進(jìn)行一系列的操作（每次操作可以

31、減少當(dāng)前環(huán)路的長(zhǎng)度），直到不能進(jìn)一步減少為止。此時(shí)的環(huán)路稱為一個(gè)局部最優(yōu)環(huán)路。換句話說(shuō)，我們可以將這一過(guò)程看作是鄰域搜索的過(guò)程，每個(gè)環(huán)路擁有一個(gè)鄰域（由一系列的相鄰的環(huán)路組成，也就是說(shuō)這些環(huán)路可以通過(guò)一個(gè)簡(jiǎn)單移動(dòng)或者交換得到）。算法持續(xù)地進(jìn)行這樣的移動(dòng)或交換，直到?jīng)]有更好的相鄰環(huán)路存在。在這些簡(jiǎn)單的環(huán)路改進(jìn)算法中，最著名的是和。算法最早由提出叨，盡管此前已經(jīng)提出了基本的交換操作【勰】。該交換刪除兩條邊，這樣將環(huán)路打破為條路徑，然后以別的方式連接這兩條路徑。如圖所示。值得一提的是，該圖是示意性的。在實(shí)際運(yùn)用中，如果邊的長(zhǎng)度如圖所示，則由于此將導(dǎo)致環(huán)路長(zhǎng)度的增加，故該將不會(huì)付諸實(shí)施。對(duì)于（見圖）而

32、言，算法利用條新的邊取代當(dāng)前環(huán)路上的條邊，得到新的環(huán)路。圖交換大連理工大學(xué)碩士學(xué)位論文圖，交換在討論等算法的解的質(zhì)量時(shí)，本文首先考慮問(wèn)題的任意局部?jī)?yōu)化算法的解質(zhì)量。對(duì)于任意的問(wèn)題而言，還有以下結(jié)論的成立：除非，否則不存在多項(xiàng)式時(shí)間的局部?jī)?yōu)化算法能夠保證（）（）成立，對(duì)于任何常數(shù)。即使是的情況下，依然不存在多項(xiàng)式時(shí)間的局部?jī)?yōu)化算法可以在不依賴于頂點(diǎn)距離的多項(xiàng)式規(guī)模的鄰域上確保獲得全局最優(yōu)解。在滿足三角不等式的情況下，等算法的理論界好得多。，和等指出在任意選擇初始環(huán)路的情況下，算法的解的目標(biāo)函數(shù)值至少是全局最優(yōu)解的¨，對(duì)于算法這個(gè)系數(shù)：是帕，更一般的情況下，對(duì)于算法這個(gè)系數(shù)為。當(dāng)實(shí)例限制

33、在歐氏空間且頂點(diǎn)之間距離通過(guò)空間上的某種范式（）計(jì)算，算法的理論界將更好。在這種情形下，沒(méi)有哪個(gè)算法的最壞情況下性能會(huì)差于（），盡管這個(gè)系數(shù)在二維歐氏空間上增長(zhǎng)速度是（力。所有的這些理論下界都是在任意選擇初始環(huán)路（此時(shí)選擇的初始環(huán)路有可能是已經(jīng)是一個(gè)比較差的局部最優(yōu)解環(huán)路）的情況下獲得的。在實(shí)際應(yīng)用中，通過(guò)使用一個(gè)好的啟發(fā)式算法以獲得一個(gè)好的初始環(huán)路，可以得到更好的理論界冽。當(dāng)使用算法生成初始環(huán)路時(shí)，在滿足三角不等式的情況下，等算法的理論界在最壞情況下不超過(guò)，這個(gè)結(jié)果優(yōu)于上面二維歐氏空間上的結(jié)論。對(duì)于環(huán)路改造算法，另一個(gè)有趣而又重要的問(wèn)題是：這些啟發(fā)式算法在達(dá)到一個(gè)局部最優(yōu)解前可以進(jìn)行多少次交

34、換？對(duì)于和，這個(gè)數(shù)目可能非常的大（甚至在實(shí)例滿足三角不等式的情況下）。已經(jīng)證明存在這樣的實(shí)例和初始環(huán)路使得在停止局部搜索前進(jìn)行（們）次的交換。，和等證明了對(duì)于同樣存在這樣的結(jié)論，并且可以推廣到，對(duì)于任意固定的。這些結(jié)論都是在任意選擇實(shí)倒和初始環(huán)路的情況下得到的。對(duì)于值較大的情況，即使使用好的初始環(huán)路對(duì)的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計(jì)結(jié)論的影響也不大。證明對(duì)于足夠大的值，在的鄰域結(jié)構(gòu)上尋找局部最優(yōu)解是完全的。這意味著無(wú)法在多項(xiàng)式時(shí)間內(nèi)求得局部最優(yōu)環(huán)路，除非所有的問(wèn)題均可以在多項(xiàng)式時(shí)間內(nèi)求解。等使用鄰接表實(shí)現(xiàn)了和算法。為了減少算法的運(yùn)行時(shí)間，等對(duì)算法的實(shí)現(xiàn)作了一些折衷，放棄了算法的理論界。然而，至少

35、對(duì)于歐氏空間上的實(shí)例而言，這樣的修改既沒(méi)有明顯影響到環(huán)路的質(zhì)量也沒(méi)有明顯影響算法的交換次數(shù)。表，給出了和算法在隨機(jī)歐氏空間上的實(shí)例和隨機(jī)距離矩陣的實(shí)例的實(shí)驗(yàn)結(jié)果。對(duì)于和算法的結(jié)果，文中采用了貪心算法的一種變體來(lái)生成初始環(huán)路。在選擇加入環(huán)路的邊時(shí)，貪心算法一般選擇最短的一條可行邊，而在本貪心算法的變體中，使用最短的兩條邊，其中選擇最短的一條邊的概率為，另一條邊的概率為。從平均性能上說(shuō)，這種貪心算法的變體所得環(huán)路長(zhǎng)度與原貪心算法基本相同。對(duì)于隨機(jī)歐氏空間上的實(shí)例而言，比最好的環(huán)路構(gòu)造算法平均好，盡管算法的初始環(huán)路比差到。而算法比解的性能還要好左右，僅僅比下界多左右，這個(gè)結(jié)果對(duì)于一般的實(shí)際應(yīng)用已經(jīng)足

36、夠了。對(duì)于隨機(jī)距離矩陣的實(shí)例而言，等算法的改進(jìn)程度相對(duì)就沒(méi)有前面那么明顯了。盡管在這些實(shí)例上，和都明顯優(yōu)于最好的環(huán)路構(gòu)造算法，隨著實(shí)例規(guī)模的增加，及的解的質(zhì)量逐步下降，其超出，下界的百分比增長(zhǎng)速度似乎是。正如我們?cè)谧罱徦惴ê拓澬乃惴ㄖ杏^察到的一樣。算法在上的實(shí)驗(yàn)結(jié)果與此類似，只是解的質(zhì)量略有下降。算法的解平均超出下界，而算法平均超出。初始環(huán)路的選擇對(duì)算法的性能的影響比較大。等研究了不同的初始環(huán)路對(duì)、解的影響（見表、）。對(duì)于隨機(jī)歐氏空間和隨機(jī)距離矩陣上的規(guī)模為的實(shí)例，等比較了不同的初始環(huán)路生成算法對(duì)于和算法的影響。對(duì)于隨機(jī)歐氏空間上的實(shí)例，最差的初始環(huán)路并不對(duì)應(yīng)著最差的環(huán)路，而恰恰相反，最好的

37、初始環(huán)路所生成的最終環(huán)路最差！盡管算法產(chǎn)生一個(gè)顯著優(yōu)于其它啟發(fā)算法的初始環(huán)路，在應(yīng)用和進(jìn)行進(jìn)一步優(yōu)化后，其最終得到的環(huán)路比其他的更差，甚至對(duì)于隨機(jī)生成的初始環(huán)路也是如此。這并不是算法的所特有的性質(zhì)。等指出，與其他的著名的環(huán)路構(gòu)造算法（包括最遠(yuǎn)插入法、算法的快速近似算法等）相比，利用貪心算法生成的初始環(huán)路進(jìn)行或優(yōu)化，得到的最終環(huán)路的質(zhì)量更好。其中的原因在于：為了讓局部搜索可以持續(xù)快速地對(duì)環(huán)路進(jìn)行優(yōu)化，初始環(huán)大連理工大學(xué)碩士學(xué)位論文路應(yīng)該包含一定數(shù)目的可用缺陷（），而一個(gè)初始環(huán)路太好的情況下，通常很少有這樣的可用缺陷。注意，對(duì)于剩余的三個(gè)算法而言，初始環(huán)路算法越好最后得到的環(huán)路就越好。不考慮算法的

38、情況下，隨機(jī)距離矩陣上的實(shí)例同樣具有這樣的性質(zhì)：好的初始環(huán)路生成好的最終環(huán)路。在隨機(jī)距離矩陣上的實(shí)例上，算法依然是一個(gè)例外：經(jīng)過(guò)算法生成的初始環(huán)路遠(yuǎn)遠(yuǎn)優(yōu)于隨機(jī)算法，但是最后得到的解卻比隨機(jī)算法要差。對(duì)于其他規(guī)模的實(shí)例，情況與此類似。表算法的實(shí)驗(yàn)性能沖渤一，；盯一一們心平均運(yùn)行時(shí)間（秒）的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計(jì)表不同初始環(huán)路對(duì)環(huán)路改進(jìn)算法的影響解超過(guò)下界的百分比（平均），問(wèn)題規(guī)模為表算法及的平均交換次數(shù)一除了、之外，問(wèn)題常見的局部搜索算法還包括、剝、和等。因?yàn)槠?，在此不再累述。一大連理工大學(xué)碩士學(xué)位論文禁忌搜索和模擬退火和其他的算法一樣，蔡忌搜索也是基于以下觀察：局部最優(yōu)解并非一定是

39、質(zhì)量好的解。因此，有必要對(duì)純粹的局部搜索算法進(jìn)行改進(jìn)，利用某種機(jī)制以幫助我們跳出局部最優(yōu)解的陷阱繼續(xù)搜索。一種可能的選擇是簡(jiǎn)單地隨機(jī)重啟，每當(dāng)局部搜索落入局部最優(yōu)解陷阱，按照某種隨機(jī)重啟策略重新選擇一個(gè)起始點(diǎn)開始局部搜索，由此得到一個(gè)新的解。隨機(jī)重啟策略的性能非常有限，并且隨著問(wèn)題規(guī)模的增加而下降。例如：盡管對(duì)于隨機(jī)歐氏空間上的頂點(diǎn)個(gè)數(shù)為的城市而言，次運(yùn)行結(jié)果中的最好者的性能通常優(yōu)于的平均解，但是對(duì)于個(gè)城市的實(shí)例而言，次運(yùn)行結(jié)果中的最好者的性能也遠(yuǎn)遠(yuǎn)差于次運(yùn)行結(jié)果中的最差者。隨機(jī)重啟策略的作用有限的一個(gè)原因在于：隨機(jī)重啟策略不考慮局部最優(yōu)解之間的相關(guān)性（局部最優(yōu)解的聚集性），也就是說(shuō)對(duì)于任意的

40、局部最優(yōu)解，一個(gè)更好的解可能就在附近。如果這種聚集性確實(shí)存在的話，從一個(gè)當(dāng)前解的附近重新開始搜索的性能，通常要優(yōu)于從任意選擇的點(diǎn)重新開始搜索。這也就是禁忌搜索的精髓之所在。禁忌搜索的基本策略如下：每一次都選擇最好的操作，即使該操作使得當(dāng)前解的目標(biāo)函數(shù)值變差。這樣，假設(shè)在每一步當(dāng)前解的所有的鄰域均被檢查，若鄰域中存在解優(yōu)于當(dāng)前解，則選擇鄰域中最好的解作為新的當(dāng)前解，否則禁忌搜索陷入了局部最優(yōu)解，此時(shí)仍然選擇鄰域中最好的解作為下一個(gè)當(dāng)前解。這樣做的一個(gè)風(fēng)險(xiǎn)是：從這個(gè)“鄰域中最好的解”開始的操作恰好選擇剛才離開的局部最優(yōu)解或者某個(gè)以前已經(jīng)訪問(wèn)過(guò)的解。因此，有必要引入所謂的禁忌列表（）。最近所執(zhí)行的一系列操作的信息被保存在一個(gè)或多個(gè)禁忌列表中。使用禁忌列表可以避免重復(fù)訪問(wèn)那些以前訪問(wèn)過(guò)的頂點(diǎn)。目前存在多種問(wèn)題的禁忌搜索算法，包括，擴(kuò)】，刪。等。在本小節(jié)的討論中，我們僅僅限于那些有實(shí)驗(yàn)結(jié)果的算法。問(wèn)題的第一個(gè)禁忌搜索算法的實(shí)現(xiàn)是提供的。，等報(bào)告了關(guān)于該實(shí)現(xiàn)及變體的實(shí)驗(yàn)結(jié)果，和等也研究了類似的方法。所有的這些算法使用作為基本交換操作，他們?cè)诮闪斜砑凹?jí)別的實(shí)現(xiàn)上有所不