旅行商問題中巡回路徑的數(shù)據(jù)結(jié)構(gòu).docx

第 24 卷 第 12 期2014 年 12 月計算機技術(shù)與發(fā)展 COMPUTE TECHNOLOGY AND DEVELOPMENTVol 24 No 12 Dec2014旅行商問題中巡回路徑的數(shù)據(jù)結(jié)構(gòu)宗德才1 ，王康康2( 1 常熟理工學院 計算機科學與工程學院，江蘇 常熟 215500; 2 江蘇科技大學 數(shù)理學院，江蘇 鎮(zhèn)江 212003)摘 要: 旅行商問題中巡回路徑的數(shù)據(jù)結(jié)構(gòu)對局部啟發(fā)式算法的效率起著非常關(guān)鍵的作用。巡回路徑的數(shù)據(jù)結(jié)構(gòu)必須能 夠查詢一條回路中每個城市的相對順序，并且能夠?qū)⒁粭l回路中的部分城市逆序。分析了數(shù)組表示法、伸展樹表示法和 兩級樹表示法表示巡回路徑時各種基本操作的實現(xiàn)過程及時間復雜度。數(shù)組表示法能夠在常數(shù)時間內(nèi)確定一條回路中每個城市的相對順序，但是最壞情況下完成逆序操作需要 ( n) 時間，不適用于大規(guī)模的旅行商問題。伸展樹表示法執(zhí)行查詢和更新操作的平攤時間復雜度是 O( logn) ，適用于極大規(guī)模的旅行商問題。而兩級樹表示法在最壞情況下每一個更 新操作的時間復雜度是 O( n0 5 ) ，適用于大規(guī)模的旅行商問題。關(guān)鍵詞: 旅行商問題; 局部啟發(fā)式算法; 數(shù)組; 伸展樹; 兩級樹中圖分類號: TP311 12文獻標識碼: A文章編號: 1673 629X( 2014) 12 0072 06 doi: 10 3969 / j issn 1673 629X 2014 12 018Data Structure of Tour for Traveling Salesman ProblemZONG De cai1 ，WANG Kang kang2( 1 College of Computer Science and Engineering，Changshu Institute of Technology，Changshu 215500，China;2 School of Mathematics and Physics，Jiangsu University of Science and Technology，Zhenjiang 212003，China)Abstract: The data structure of tour for the traveling salesman problem plays a critical role in the efficiency of local heuristic algorithms The data structure of tour must permit queries about the relative order of cities in the tour and must allow sections of the tour to be re- versed The implementation and time complexity of several basic operations when the tour is represented by array ，splay tree and two level tree are analyzed The array based representation of a tour permits the relative order of cities to be determined in small constanttime，but requires worst case ( n) time to implement a reversal，w hich renders it impractical for large instances For the data structurebased on splay tree，all queries and updates take amortized time O( logn) ，w hich is available for extremely large scale traveling salesman problem For the data structure based on two level tree representation，the worst case time for each update operation is O( n0 5 ) ，w hich is available for large scale traveling salesman problemKey words: traveling salesman problem; local heuristic algorithm; array; splay tree; two level tree0引言旅行商問題( Traveling Salesman Problem ，TSP) 是an ) 表示訪問的第一個城市是城市 a1 ，第 二個城市是 城市 a2 ，訪問的最后一個城市是 an ，最后再回到第1i j = dj i 時，稱為對一個典型的 NP 難1的組合優(yōu)化問題。假設(shè)有 n 個城市，用 1 n 對城市進行編號，1 表 示城市 1，2 表示城市 2，n 表示城市 n。 是所有 1， 2，n 排列的集合，di，j 是城市 i 到城市 j 的距離，s =一個城市 a 的一條巡回路徑。當 d ，稱 TSP 問題; 當 di，j dj，i 時，稱為不對稱 TSP 問題。文 中提到的 TSP 問題均是指對稱 TSP 問題。TSP 問題可以用數(shù)學表達式表示為:( da ，aa ，aa ，a )( 1)( a1 ，a2 ，an ) 是 1，2，n 的一個排列，( a1 ，a2 ，mins+ d1 22+ + d3n 1收稿日期: 2014 01 24修回日期: 2014 04 28網(wǎng)絡(luò)出版時間: 2014 10 23基金項目: 江蘇省高校自然科學基礎(chǔ)研究項目( 13KJB110006) ; 常熟理工學院青年教師基金項目( CST201209)作者簡介: 宗德才( 1979 ) ，男，江蘇常熟人，講師，碩士，研究方向為智能優(yōu)化算法、概率論; 王康康，副教授，博士，研究方向為智能優(yōu)化算法、 概率論。網(wǎng)絡(luò)出版地址: http: / / www cnki net / kcms / detail /61 1450 TP 20141023 1102 023 html第 12 期宗德才等: 旅行商問題中巡回路徑的數(shù)據(jù)結(jié)構(gòu)73求解 TSP 問題的算法有兩類: 一類是精確算法， 能夠求出 TSP 問題的精確解，但是計算時間是問題規(guī) 模( 城市個數(shù)) 的指數(shù)級，隨著問題規(guī)模的擴大，將 產(chǎn) 生組合爆炸; 另一類是隨機優(yōu)化算法或局部搜索算法， 能夠在多項式時間內(nèi)求得問題的近似解。近年來，為解決 TSP 問題出現(xiàn)了許多局部搜索算 法，比較著名的有: 2 opt 算法2、3 opt 算法3、Lin Kernighan( LK) 算法4 等。這些算法能夠在較短時 間內(nèi)獲得近似解。在 2 opt 算法、3 opt 算法和 Lin Kernighan 算 法中，巡回路 徑的數(shù)據(jù)結(jié)構(gòu)必須支持四種基本操作:Next( a) 返回當前巡回路徑中位于城市 a 之后的城 市; Prev( a) 返回當前巡回路徑中位于城市 a 之前的城 市; Between( a，b ，c ) 返回 True 或 False，如果從城市 a 出發(fā)，先到達城市 b 再到達城市 c，則返回 True，否則， 返回 False; Flip( a，b ，c，d) 用邊( b ，c ) 和邊( a，d) 代替 邊( a，b ) 和邊( c，d) ，假定 a = Next( b ) ，d = Next( c) 。1巡回路徑的數(shù)據(jù)結(jié)構(gòu)旅行商問題中的巡回路徑可以用數(shù)組、伸展樹和 兩級樹來表示。下面將詳細分析這三種表示方法的具 體實現(xiàn)過程。1 1數(shù)組表示法數(shù)組表示法是最簡單的表示方法。文獻5 10中巡回路徑的數(shù)據(jù)結(jié)構(gòu)都是用數(shù)組表示的。 一條巡回路徑可以用兩個長度是 n 的一維數(shù)組 A和 B 表示。A 表示巡回路徑中訪問城市的先后順序，A1表示訪問的第一個城市是 A1，A2表示訪問的 第二個城市是 A2，An表示訪問的最后一個城 市是 An; B1表示城市 c1 在巡回路徑中是第 B1 個被訪問的，B2表 示城市 c2 在巡回路徑中是第 B2個被訪問的，Bn表示城市 cn 在巡回路徑中是 第 Bn個被訪問的。ABi= ci ，1in用數(shù)組表示法 Next( a) ，Prev( a) ，Between( a，b，c) 操作能夠在常數(shù)時間內(nèi)完成。Next( a) 操作的實現(xiàn)過 程: 假設(shè) a = ck ，在數(shù)組 B 中找到 ck 在回路中是第 Bk 個被訪問的，Next( a) = ABk+ 1。Prev( a) 操作的 實現(xiàn)過程: 假設(shè) a = ck ，在數(shù)組 B 中找到 ck 在回路中是 第 Bk個 被訪問的，Prev ( a) = ABk 1 。Be- tween( a，b，c) 操作的實現(xiàn)過程: 假設(shè) a = ci ，b = cj ，c = ck ，如果 Bi Bj Bk，則 Between( a，b，c) 返回True，否則返回 False。Flip( a，b，c，d) 操作的實現(xiàn)最復雜。假設(shè) a = ci ，b= cj ，c = cp ，d = cq ，令 Lac = Bp Bi+ 1，如果 Lac 0，Lac = Lac + n，如果 2Lac n，則將 a 和 c 之間的路徑反轉(zhuǎn)，即交換 Ai與 Ap的值，Ai + 1與 Ap 1的 值，并且要交換 Bi與 Bp的值，Bi + 1與 Bp 1的值，; 如果 2Lac n，則將 b 和 d 之間的路徑反轉(zhuǎn)。 Flip( a，b，c，d) 操作在最壞情況下的時間復雜度是 O( n) 。隨著 n 的增加，這些操作所用的時間將占整個算 法運行時間的絕大部分。1 2伸展樹表示法伸展樹 是 一 種 能 夠 實 現(xiàn) 自我調(diào)整的二叉查找 樹11，每當一個節(jié)點被訪問后，它會沿著從該節(jié)點到 樹根的路徑，通過一系列的旋轉(zhuǎn)把該節(jié)點調(diào)整到樹根 處( 伸展操作) ，使下次再訪問該節(jié)點時可以快速找到 該節(jié)點。文獻12中巡回路徑的數(shù)據(jù)結(jié)構(gòu) 是用伸展 樹表示的。如果要對一個二叉查找樹執(zhí)行一系列操作，它能 夠在當前操作中使用一種簡單的重建啟發(fā)式規(guī)則( 伸 展) 提高后續(xù)操作的效率。一條巡回路徑可以用一棵伸展樹來表示，樹中的 每個節(jié)點代表一個城市，每 個節(jié)點有一個反轉(zhuǎn)位13 ( 如果反轉(zhuǎn)位是 0，表 示將按照中序訪問此節(jié)點的子 樹，即先訪問該節(jié)點的左子樹，然后訪問該節(jié)點，最后 訪問右子樹; 如果反轉(zhuǎn)位是 1，則先訪問該節(jié)點的右子 樹，然后訪問該節(jié)點，最后訪問左子樹) 。如果節(jié)點的 反轉(zhuǎn)位是 1，則該節(jié)點用雙圈表示。由一棵帶反轉(zhuǎn)位的伸展樹確定一條巡回路徑的方 法如下: 從樹根開始，從上往下將所有節(jié)點的反轉(zhuǎn)位變 成 0 得到一棵等價的樹，然后中序遍歷該樹就可得到 所需的巡回路徑。如果一個節(jié)點的反轉(zhuǎn)位是 1，通 過 以下方法可將該節(jié)點的反轉(zhuǎn)位變?yōu)?0: 首先交換該節(jié) 點的左子樹和右子樹，并且給左子樹和右子樹的樹根 的反轉(zhuǎn)位加上 1，如果反轉(zhuǎn)位變成了 2，相當于取消反 轉(zhuǎn)，直接將反轉(zhuǎn)位由 2 變成 0 即可。對節(jié)點 x 執(zhí)行伸展操作，是在保持伸展樹有序性的前提下，通過一系列的伸展步驟將節(jié)點 x 調(diào)整到樹 根處。執(zhí)行伸展操作之前要將相關(guān)節(jié)點的反轉(zhuǎn)位置 0。 伸展步驟11 分三種: 左旋 ( 右旋) 、右 旋 右旋( 左旋 左旋) 、左旋 右旋( 右旋 左旋) 。如圖 1( a) 所示，節(jié)點 x 的父節(jié)點 y 是根節(jié)點并且 x 是 y 的左孩子，則 向右旋轉(zhuǎn)連接節(jié)點 x 和節(jié)點 y 的 邊; 如果 x 是 y 的右孩子，則向左旋轉(zhuǎn)連接節(jié)點 x 和節(jié) 點 y 的邊。如圖 1( b) 所示，節(jié)點 x 的父節(jié)點 y 不是根節(jié)點， 節(jié)點 y 的父節(jié)點是 z，并且 x 和 y 同時是各自父節(jié)點的 左孩子，則先向右旋轉(zhuǎn)連接節(jié)點 y 和 z 的邊，然后向右 旋轉(zhuǎn)連接節(jié)點 x 和節(jié)點 y 的邊; 如果節(jié)點 x 的父節(jié)點 y 不是根節(jié)點，節(jié)點 y 的父節(jié)點是 z，并且 x 和 y 同時是 各自父節(jié)點的右孩子，則先向左旋轉(zhuǎn)連接節(jié)點 y 和節(jié)74計算機技術(shù)與發(fā)展第 24 卷點 z 的邊，然后向左旋轉(zhuǎn)連接節(jié)點 x 和節(jié)點 y 的邊。圖 1伸展步驟如圖 1( c) 所示，節(jié)點 x 的父節(jié)點 y 不是根節(jié)點， 節(jié)點 x 是其父節(jié)點 y 的右孩子，節(jié)點 y 是其父節(jié)點 z 的 左孩子，則先向左旋轉(zhuǎn)連接節(jié)點 y 和節(jié)點 x 的邊，然后 向右旋轉(zhuǎn)連接節(jié)點 x 和節(jié)點 z 的邊; 節(jié)點 x 的父節(jié)點 y 不是根節(jié)點，節(jié)點 x 是其父節(jié)點 y 的左孩子，節(jié)點 y 是 其父節(jié)點 z 的右孩子，則先向右旋轉(zhuǎn)連接節(jié)點 y 和節(jié) 點 x 的邊，然后向左旋轉(zhuǎn)連接節(jié)點 x 和節(jié)點 z 的邊。伸展樹的存儲結(jié)構(gòu): 伸展樹中一個節(jié)點對應(yīng)一個 城市，可以使用散列法將伸展樹的節(jié)點信息存儲在一 個數(shù)組 SPA 中，城市 c1 節(jié)點的信息存儲在 SPA1中，城市 ci 節(jié)點的信息存儲在 SPAi中，因此，根據(jù)城 市名字 ci 可以在常數(shù)時間內(nèi)找到城市 ci 在伸展樹中對應(yīng)的節(jié)點位置。Next( a) 操作的實現(xiàn)過程: 首先找到城市 a 在伸展 樹中的位置，將相關(guān)節(jié)點的反轉(zhuǎn)位變成 0，通過伸展操 作把該節(jié)點調(diào)整到樹根處; 然后從樹根開始，將相關(guān)節(jié) 點的反轉(zhuǎn)位變成 0 后右子樹中最左的節(jié)點就是 a 的后 繼節(jié)點 Next( a) ; 最后將 a 的后繼節(jié)點 Next( a) 通過伸 展操作調(diào)整到樹根處。Prev( a) 操作的實現(xiàn)過程: 首先找到城市 a 在伸展 樹中的位置，將相關(guān)節(jié)點的反轉(zhuǎn)位變成 0，通過伸展操作把該節(jié)點調(diào)整到樹根處; 然后從樹根開始，將相關(guān)節(jié) 點的反轉(zhuǎn)位變成 0 后左子樹中最右的節(jié)點就是 a 的前 驅(qū)節(jié)點 Prev( a) ; 最后將 a 的前驅(qū)節(jié)點 Prev( a) 通過伸 展操作調(diào)整到樹根處。Between( a，b，c) 操作的實現(xiàn)過程: 首先找到城市 b 的位置，通過伸展操作把節(jié)點 b 調(diào)整到樹根處，再找到 節(jié)點 a 的位置，通過伸展操作把節(jié)點 a 調(diào)整到樹根處， 然后找到節(jié)點 c 的位置，通過伸展操作把節(jié)點 c 調(diào)整到樹根處。找到節(jié)點 b 在伸展樹中的新位置，從節(jié)點 b 開始朝樹根方向按照中序遍歷伸展樹，如 果節(jié)點 c 比節(jié)點 a 先找到并且節(jié)點 b 在節(jié)點 c 的左子樹中或者 節(jié)點 a 比節(jié)點 c 先找到并且節(jié)點 b 在節(jié)點 a 的右子樹 中，則 Between( a，b，c) 返回 True，否則返回 False。Flip( a，b，c，d) 操作的實現(xiàn)最復雜。首先找到節(jié) 點 d 的位置，通過伸展操作把節(jié)點 d 調(diào)整到樹根處，再 找到節(jié)點 b 的位置，通過伸展操作把節(jié)點 b 調(diào)整到樹 根處，此時伸展樹將處于下面四種情況之一，如圖 2 所 示。圖 2 中 T1 T4 是節(jié)點的子樹。圖 2節(jié)點 d 和節(jié)點 b 先后進行伸展 操作后伸展樹的四種情況i對于圖 2 中的( a) 、( b) 兩種情況，F(xiàn)lip( a，b，c，d) 操作將對節(jié)點 b 和節(jié)點 d 之間的路徑進行反轉(zhuǎn)，反轉(zhuǎn) 后的伸展樹如圖 3( a) 、( b) 所示。對于圖 2 中的( c) 、 ( d) 兩種情況，F(xiàn)lip( a，b，c，d) 操作將對節(jié)點 a 和節(jié)點 c 之間的路徑進行反轉(zhuǎn)，反轉(zhuǎn)后的伸展樹如圖 3( c) 、( d) 所示。圖 3 中，帶雙圈的節(jié)點的反轉(zhuǎn)位是 1，T 表示子 樹 Ti 的根節(jié)點的反轉(zhuǎn)位是 1。圖 3執(zhí)行 Flip( a，b，c，d) 操作后的伸展樹對 n 個節(jié)點的伸展樹表示的一條巡回路徑執(zhí)行一 系列的 Next、Prev、Between、Flip 操作，每個操作的平攤 時間為 O( logn) 11( n 為回路中包含的城市個數(shù)) 。第 12 期宗德才等: 旅行商問題中巡回路徑的數(shù)據(jù)結(jié)構(gòu)75平攤時間是指執(zhí)行一系列最壞情況下的每個操作的平 均時間。1 3兩級樹表示法在文獻14 15中巡回路徑的 數(shù)據(jù)結(jié)構(gòu)都是用 兩級樹表示的。一條巡回路徑大約被分成 槡n 段子路徑，每段子路 徑中包含 槡n /2 到 2 槡n 個城市。每段子路徑用一個段節(jié)點表示，如圖 4 所示。每個段節(jié)點有 4 個指針: prev、 next 分別指向前一段子路徑和下一段子路徑，first、last 分別指向子路徑中包含的第一個城市節(jié)點和最后一個 城市節(jié)點，每段子路徑中還有 3 個變量 pos、rev、lens 分 別表示該段子路徑在第一層鏈表中的位置，訪問子路 徑中城市時是按順時針方向還是按逆時針方向和該段 子路徑中包含的城市節(jié)點個數(shù)有關(guān)。每段子路徑中的 城市節(jié)點用雙向鏈表相互連接起來。每個城市節(jié)點有 3 個指針: prevc( 指向前驅(qū)節(jié)點) 、nextc ( 指向后繼節(jié) 點) 、parent( 指向本節(jié)點所在的子路徑) ，還 有 2 個變 量 num，posc 分別表示該城市的編號和在子路徑中所 處的位置。圖 4 中，兩級樹表示的一條巡回路徑是( c6 ，c8 ，c4 ，c2 ，c9 ，c7 ，c3 ，c5 ，c1 ) 。兩級樹的存儲結(jié)構(gòu): 兩級樹中一個節(jié)點對應(yīng)一個 城市，可以使用散列法將兩級樹的節(jié)點信息存儲在一個數(shù)組 TLA 中，城市 c1 節(jié)點的信息存儲在 TLA1中，城市 ci 節(jié)點的信息存儲在 TLAi中，因此，根據(jù)城 市名字 ci 可以在常數(shù)時間內(nèi)找到城市 ci 在兩級樹中對 應(yīng)的節(jié)點位置。由于在訪問旅行回路時可以按照順時針方向或逆 時針方向訪問，用一個變量 eversed 表示在訪問旅行 回路時的方向，eversed = 0 表示順時針方向，eversed= 1 表示逆時針方向。Next( a) 操作的實現(xiàn)過程: 首先找到城市 a 在兩級 樹中的節(jié)點位置 na，則城市節(jié)點 na 的父節(jié)點是 na parent，如果 eversed = 0 并且 na parent 段節(jié)點的 rev 值是 1，即按照逆時針方向訪問 na parent 段中的 城市，則 Next( a) = a prevc; 如果 eversed = 0 并且 na parent 段節(jié)點的 rev 值是 0，則 Next( a) = a nextc; 如果 eversed = 1 并且 na parent 段節(jié)點的 rev 值是 1， 則 Next( a) = a nextc; 如果 eversed = 1 并且 na parent 段節(jié)點的 rev 值是 0，則 Next( a) = a prevc。Prev( a) 操作的實現(xiàn)過程與 Next( a) 操作的實現(xiàn) 過程類似。Between( a，b，c) 操作的實現(xiàn)過程: 首先找到城市 a、b、c 在兩級樹中的節(jié)點位置 na、nb、nc，則城市節(jié)點 a、b、c 的父節(jié)點分別是 na parent、nb parent、nc parent。圖 4兩級樹表示巡回路徑如果 na、nb、nc 在同一個段 na parent 中，當 eversed 等于na parent rev 時，如果滿足條件 na posc nb posc nc posc 或者 nc posc na posc nb posc 或者nb posc nc posc na posc，則Between( a，b，c) 返回 True，否則返回 False; 當 eversed 不等于na parent rev 時，如果滿足條件 nb posc na posc nc posc 或者 na posc nc posc nb posc 或者 nc posc nb posc na posc，則 Be- tween( a，b，c) 返回 True，否則返回 False。如果 na、nb、nc 有兩個節(jié)點在同一個段中，如果 na、nb 在 同一個段na parent 中，當 eversed 等于na parent rev 時，如果滿足條件 na posc nb posc，則 Between ( a，b，c) 返回 True，否則返回 False; 當 eversed 不等于 na parent rev 時，如果滿足條件 na posc nb posc， 則 Between( a，b，c) 返回 True，否則返回 False。如果 na、nc 在 同一個段na parent 中，當 eversed 等于na parent rev 時，如果滿足條件 nc posc na posc，則 Between ( a，b，c) 返回 True，否則返回 False; 當 eversed 不等于 na 76計算機技術(shù)與發(fā)展第 24 卷parent rev 時，如果滿足條件 na posc nc posc，則 Between( a，b，c) 返回 True，否則返回 False。如果 nb、nc 在同 一個段 nb parent 中，當 eversed 等于 nb parent rev 時，如果滿足條件 nb posc nc posc，則 Between ( a，b，c) 返回 True，否則返回 False; 當 eversed 不等于 nb parent rev 時，如果滿足條件 nc posc nb posc， 則 Between( a，b，c) 返回 True，否則返回 False。如果 na、nb、nc 在三個不同的段中，當 eversed = 0 時，如果滿 足條件 na parent pos nb parent pos nc parent pos 或者 nc par- ent pos na parent pos nb parent pos 或者 nb parent pos nc parent pos na parent pos，則 Between( a，b，c) 返回 True，否則返回 False; 當 eversed = 1 時，如果滿足條件nb parent pos na parent pos nc parent pos 或者 na parent pos nc parent pos nb parent pos 或者 nc parent pos nb parent pos na parent pos，則 Between( a，b，c) 返回 True，否則返回 False。Flip( a，b，c，d) 操作的實現(xiàn)最復雜。如果節(jié)點 a 和節(jié)點 c 之間的路徑在同一個段中并且節(jié)點 a 和節(jié)點 c 之間的長度大于 3 /4 槡n ( 如圖 5( a) 所示) ，那么，當節(jié)點 a 和節(jié)點 b 在同一段中時，將該段 在節(jié)點 a 和節(jié)點 b 中間分成兩段并且將長度較短的段 與鄰接段合并以保持段的總個數(shù)不變，當節(jié)點 c 和節(jié) 點 d 在同一段中時，將該段在節(jié)點 c 和節(jié)點 d 中間分 成兩段并且將長度較短的段與鄰接段合并以保持段的 總個數(shù)不變，然后在同一個段中將節(jié)點 a 和節(jié)點 c 之 間的路徑反轉(zhuǎn)，即更新節(jié)點 a 和節(jié)點 c 之間的城市節(jié) 點的 nextc、prevc 指針和 posc 變量的值以及節(jié)點 b、d 的 nextc、prevc 指針的值。之間的路徑反轉(zhuǎn)，即更新節(jié)點 a 和節(jié)點 c 之間的城市 節(jié)點的 nextc、prevc 指針和 posc 變量的值以及節(jié)點 b、d 的 nextc、prevc 指針的值。如果節(jié)點 b 和節(jié)點 d 之間的 路徑在同一個段中，處理方法類似。如果節(jié)點 b 和節(jié)點 d 之間的路徑與節(jié)點 a 和節(jié)點 c 之間的路徑都是由多個連續(xù)的完整段組成的( 如圖 6 所示) ，假設(shè)段的總個數(shù)為 S，令 Lac = c parent pos c parent pos + 1，如果 Lac 0，Lac = Lac + S。 如果 2Lac S，則將節(jié)點 b 和節(jié)點 d 之間的路徑反轉(zhuǎn)， 即更新 b 和 d 之間的段節(jié)點的 prev、next 指針和 pos 變 量的值以及 a parent、c parent 段節(jié)點的 prev、 next 指針的值。如果 2Lac S，則將節(jié)點 a 和節(jié)點 c 之 間的路徑反轉(zhuǎn)，即 更新 a 和 c 之間的段節(jié)點的 prev、 next 指針和 pos 變量的值以及 b parent、d par- ent 段節(jié)點的 prev、next 指針的值。圖 6節(jié)點 b 和節(jié)點 d 之間的路徑與節(jié)點 a 和節(jié)點c 之間的路徑都是由多個連續(xù)的完整段組成如果節(jié)點 b 和節(jié)點 d 之間的路徑不在同一個段中 并且節(jié)點 a 和節(jié)點 c 之間的路徑也不在同一個段中， 那么，當節(jié)點 a 和節(jié)點 b 在同一段中時，將該段在節(jié)點 a 和節(jié)點 b 中間分成兩段并且將長度較短的段與鄰接 段合并以保持段的總個數(shù)不變，當節(jié)點 c 和節(jié)點 d 在同一段中時，將該段在節(jié)點 c 和節(jié)點 d 中間分成兩段 并且將長度較短的段與鄰接段合并以保持段的總個數(shù) 不變，如果分段后，節(jié)點 b 和節(jié)點 d 之間的路徑在同一 個段中或節(jié)點 a 和節(jié)點 c 之間的路徑在同一個段中，則處理方法如圖 5 所示。如果分段后，節(jié)點 b 和節(jié)點 d 之間的路徑不在同一個段中并且節(jié)點 a 和節(jié)點 c 之間 的路徑也不在同一個段中，則處理方法如圖 6 所示。Prev( a) 、Next( a) 和 Between( a，b，c) 操作都能夠 在常數(shù)時間內(nèi)完成，而 Flip( a，b，c，d) 操作最壞情況下1 4的時間復雜度是 O( 槡n )。圖 5節(jié)點 a 和節(jié)點 c 之間的路徑在同一個段中如果節(jié)點 a 和節(jié)點 c 之間的路徑在同一個段中并且節(jié)點 a 和節(jié)點 c 之間的長度小于或等于 3 /4 槡n ( 如 圖 5( b) 所示) ，那么，在同一個段中將節(jié)點 a 和節(jié)點 c2結(jié)束語在 2 opt 算法、3 opt 算法和 Lin Kernighan 算 法等局部搜索算法中，巡回路徑的數(shù)據(jù)結(jié)構(gòu)必須支持 四種基本操作，即 Next( a) 、Prev( a) 、Between( a，b，c) 和 Flip( a，b，c，d) 。旅行商問題中的巡回路徑可以用 數(shù)組、伸展樹和兩級樹來表示。文中主要詳細分析了第 12 期宗德才等: 旅行商問題中巡回路徑的數(shù)據(jù)結(jié)構(gòu)77這三種表示方法的具體實現(xiàn)過程以及每一種數(shù)據(jù)結(jié)構(gòu) 中四種基本操作的時間復雜度。當巡回路徑用數(shù)組表 示時，Next( a) 、Prev( a) 和 Between( a，b，c) 操作能夠在 常數(shù)時間內(nèi)完成，F(xiàn)lip( a，b，c，d) 操作在最壞情況下的 時間復雜度是 O( n) ，不適用于大規(guī)模的旅行商問題。 當巡回路徑用伸展樹表示時，每個操作的平攤時間復 雜度為 O( logn) ，適用于極大規(guī)模的旅行商問題。當 巡回路徑用兩級樹表示時，Prev ( a ) 、Next ( a ) 和 Be- tween( a，b，c) 操作都能夠在常數(shù)時間內(nèi)完成，而 Flip ( a，b，c，d ) 操 作 在 最 壞 情 況 下 的 時 間 復 雜 度 是 O ( n1 /2 ) ，適用 于大規(guī)模的旅行商問題。下一步將用 C 語言編程實現(xiàn)這三種數(shù)據(jù)結(jié)構(gòu)，并通過仿真實驗分析 這三種數(shù)據(jù)結(jié)構(gòu)對 Lin Kernighan 算法等局部搜索算 法在求解旅行商問題時性能的影響。參考文獻:1 Garey M ，Johnson D S Computers and intractability: a guide to the theory of NP completenessM San Francisco，USA: Freeman W H，19792 Croes G A A method for solving traveling salesman problemsJ Operations esearch，1958，6( 6) : 791 8123 Lin S Computer solutions of the traveling salesman problemJ Bell System Technical Journal，1965，44 ( 10 ) : 2245 22694 Lin S，Kernighan B W An effective heuristic algorithm for the traveling salesman problemJ Operations esearch，1973，21 ( 2) : 498 5165 宗德才，王 康康 改進的嵌套分區(qū)算法求解旅行商問題 J 計算機工程與應(yīng)用，2011，47( 24) : 54 576 陳曉峰，宋 杰 量子人工魚群算 法J 東北大學學報( 自然科學版) ，2012，33( 12) : 1710 17137 蘇曉勤，孫鶴旭，潘旭華 改進蜂群算法的旅行商問題仿真J 計算機工程與設(shè)計，2013，34( 4) : 1420 14248 王忠英，白艷萍，岳利霞 經(jīng)過改進的求解 TSP 問題的蟻群 算法J 數(shù)學的實踐與認識，2012，24( 4) : 133 1409 柳 寅，馬 良 模糊人工蜂群算法的旅行商問題求解 J 計算機應(yīng)用研究，2013，30( 9) : 2694 269610 申鉉京，劉陽陽，黃永平，等 求解 TSP 問題的快速蟻群算 法J 吉林大學學報( 工學版) ，2013，43( 1) : 147 15111 Sleator D D，Tarjan E Self adjusting binary search treesJ Journal of the Association for Computing Machinery， 1985，32( 3) : 652 68612 Gamboa D，ego C，Glover F Data structures and ejection chains for solving large scale traveling salesman problemsJ European Journal of Operational esearch，2005，160( 1) : 154 17113 Chrobak M，Szymacha T，Krawczyk A A data structure useful for finding Hamiltonian cyclesJ Theoretical Computer Sci- ence，1990，71( 3) : 419 42414 Helsgaun K An effective implementation of the Lin Ker- nighan traveling salesman heuristicJ European Journal of Operational esearch，2000，126( 1) : 106 13015 Helsgaun K General k opt submoves for the Lin Kernighan TSP heuristicJ Mathematical Programming Computation， 200