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

第 24 卷 第 12 期2014 年 12 月計(jì)算機(jī)技術(shù)與發(fā)展 COMPUTE TECHNOLOGY AND DEVELOPMENTVol 24 No 12 Dec2014旅行商問題中巡回路徑的數(shù)據(jù)結(jié)構(gòu)宗德才1 ，王康康2( 1 常熟理工學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 常熟 215500; 2 江蘇科技大學(xué) 數(shù)理學(xué)院，江蘇 鎮(zhèn)江 212003)摘 要: 旅行商問題中巡回路徑的數(shù)據(jù)結(jié)構(gòu)對局部啟發(fā)式算法的效率起著非常關(guān)鍵的作用。巡回路徑的數(shù)據(jù)結(jié)構(gòu)必須能 夠查詢一條回路中每個(gè)城市的相對順序，并且能夠?qū)⒁粭l回路中的部分城市逆序。分析了數(shù)組表示法、伸展樹表示法和 兩級樹表示法表示巡回路徑時(shí)各種基本操作的實(shí)現(xiàn)過程及時(shí)間復(fù)雜度。數(shù)組表示法能夠在常數(shù)時(shí)間內(nèi)確定一條回路中每個(gè)城市的相對順序，但是最壞情況下完成逆序操作需要 ( n) 時(shí)間，不適用于大規(guī)模的旅行商問題。伸展樹表示法執(zhí)行查詢和更新操作的平攤時(shí)間復(fù)雜度是 O( logn) ，適用于極大規(guī)模的旅行商問題。而兩級樹表示法在最壞情況下每一個(gè)更 新操作的時(shí)間復(fù)雜度是 O( n0 5 ) ，適用于大規(guī)模的旅行商問題。關(guān)鍵詞: 旅行商問題; 局部啟發(fā)式算法; 數(shù)組; 伸展樹; 兩級樹中圖分類號: TP311 12文獻(xiàn)標(biāo)識碼: 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 ) 表示訪問的第一個(gè)城市是城市 a1 ，第 二個(gè)城市是 城市 a2 ，訪問的最后一個(gè)城市是 an ，最后再回到第1i j = dj i 時(shí)，稱為對一個(gè)典型的 NP 難1的組合優(yōu)化問題。假設(shè)有 n 個(gè)城市，用 1 n 對城市進(jìn)行編號，1 表 示城市 1，2 表示城市 2，n 表示城市 n。 是所有 1， 2，n 排列的集合，di，j 是城市 i 到城市 j 的距離，s =一個(gè)城市 a 的一條巡回路徑。當(dāng) d ，稱 TSP 問題; 當(dāng) di，j dj，i 時(shí)，稱為不對稱 TSP 問題。文 中提到的 TSP 問題均是指對稱 TSP 問題。TSP 問題可以用數(shù)學(xué)表達(dá)式表示為:( da ，aa ，aa ，a )( 1)( a1 ，a2 ，an ) 是 1，2，n 的一個(gè)排列，( a1 ，a2 ，mins+ d1 22+ + d3n 1收稿日期: 2014 01 24修回日期: 2014 04 28網(wǎng)絡(luò)出版時(shí)間: 2014 10 23基金項(xiàng)目: 江蘇省高校自然科學(xué)基礎(chǔ)研究項(xiàng)目( 13KJB110006) ; 常熟理工學(xué)院青年教師基金項(xiàng)目( CST201209)作者簡介: 宗德才( 1979 ) ，男，江蘇常熟人，講師，碩士，研究方向?yàn)橹悄軆?yōu)化算法、概率論; 王康康，副教授，博士，研究方向?yàn)橹悄軆?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 問題的精確解，但是計(jì)算時(shí)間是問題規(guī) 模( 城市個(gè)數(shù)) 的指數(shù)級，隨著問題規(guī)模的擴(kuò)大，將 產(chǎn) 生組合爆炸; 另一類是隨機(jī)優(yōu)化算法或局部搜索算法， 能夠在多項(xiàng)式時(shí)間內(nèi)求得問題的近似解。近年來，為解決 TSP 問題出現(xiàn)了許多局部搜索算 法，比較著名的有: 2 opt 算法2、3 opt 算法3、Lin Kernighan( LK) 算法4 等。這些算法能夠在較短時(shí) 間內(nèi)獲得近似解。在 2 opt 算法、3 opt 算法和 Lin Kernighan 算 法中，巡回路 徑的數(shù)據(jù)結(jié)構(gòu)必須支持四種基本操作:Next( a) 返回當(dāng)前巡回路徑中位于城市 a 之后的城 市; Prev( a) 返回當(dāng)前巡回路徑中位于城市 a 之前的城 市; Between( a，b ，c ) 返回 True 或 False，如果從城市 a 出發(fā)，先到達(dá)城市 b 再到達(dá)城市 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ù)組、伸展樹和 兩級樹來表示。下面將詳細(xì)分析這三種表示方法的具 體實(shí)現(xiàn)過程。1 1數(shù)組表示法數(shù)組表示法是最簡單的表示方法。文獻(xiàn)5 10中巡回路徑的數(shù)據(jù)結(jié)構(gòu)都是用數(shù)組表示的。 一條巡回路徑可以用兩個(gè)長度是 n 的一維數(shù)組 A和 B 表示。A 表示巡回路徑中訪問城市的先后順序，A1表示訪問的第一個(gè)城市是 A1，A2表示訪問的 第二個(gè)城市是 A2，An表示訪問的最后一個(gè)城 市是 An; B1表示城市 c1 在巡回路徑中是第 B1 個(gè)被訪問的，B2表 示城市 c2 在巡回路徑中是第 B2個(gè)被訪問的，Bn表示城市 cn 在巡回路徑中是 第 Bn個(gè)被訪問的。ABi= ci ，1in用數(shù)組表示法 Next( a) ，Prev( a) ，Between( a，b，c) 操作能夠在常數(shù)時(shí)間內(nèi)完成。Next( a) 操作的實(shí)現(xiàn)過 程: 假設(shè) a = ck ，在數(shù)組 B 中找到 ck 在回路中是第 Bk 個(gè)被訪問的，Next( a) = ABk+ 1。Prev( a) 操作的 實(shí)現(xiàn)過程: 假設(shè) a = ck ，在數(shù)組 B 中找到 ck 在回路中是 第 Bk個(gè) 被訪問的，Prev ( a) = ABk 1 。Be- tween( a，b，c) 操作的實(shí)現(xiàn)過程: 假設(shè) a = ci ，b = cj ，c = ck ，如果 Bi Bj Bk，則 Between( a，b，c) 返回True，否則返回 False。Flip( a，b，c，d) 操作的實(shí)現(xiàn)最復(fù)雜。假設(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) 操作在最壞情況下的時(shí)間復(fù)雜度是 O( n) 。隨著 n 的增加，這些操作所用的時(shí)間將占整個(gè)算 法運(yùn)行時(shí)間的絕大部分。1 2伸展樹表示法伸展樹 是 一 種 能 夠 實(shí) 現(xiàn) 自我調(diào)整的二叉查找 樹11，每當(dāng)一個(gè)節(jié)點(diǎn)被訪問后，它會沿著從該節(jié)點(diǎn)到 樹根的路徑，通過一系列的旋轉(zhuǎn)把該節(jié)點(diǎn)調(diào)整到樹根 處( 伸展操作) ，使下次再訪問該節(jié)點(diǎn)時(shí)可以快速找到 該節(jié)點(diǎn)。文獻(xiàn)12中巡回路徑的數(shù)據(jù)結(jié)構(gòu) 是用伸展 樹表示的。如果要對一個(gè)二叉查找樹執(zhí)行一系列操作，它能 夠在當(dāng)前操作中使用一種簡單的重建啟發(fā)式規(guī)則( 伸 展) 提高后續(xù)操作的效率。一條巡回路徑可以用一棵伸展樹來表示，樹中的 每個(gè)節(jié)點(diǎn)代表一個(gè)城市，每 個(gè)節(jié)點(diǎn)有一個(gè)反轉(zhuǎn)位13 ( 如果反轉(zhuǎn)位是 0，表 示將按照中序訪問此節(jié)點(diǎn)的子 樹，即先訪問該節(jié)點(diǎn)的左子樹，然后訪問該節(jié)點(diǎn)，最后 訪問右子樹; 如果反轉(zhuǎn)位是 1，則先訪問該節(jié)點(diǎn)的右子 樹，然后訪問該節(jié)點(diǎn)，最后訪問左子樹) 。如果節(jié)點(diǎn)的 反轉(zhuǎn)位是 1，則該節(jié)點(diǎn)用雙圈表示。由一棵帶反轉(zhuǎn)位的伸展樹確定一條巡回路徑的方 法如下: 從樹根開始，從上往下將所有節(jié)點(diǎn)的反轉(zhuǎn)位變 成 0 得到一棵等價(jià)的樹，然后中序遍歷該樹就可得到 所需的巡回路徑。如果一個(gè)節(jié)點(diǎn)的反轉(zhuǎn)位是 1，通 過 以下方法可將該節(jié)點(diǎn)的反轉(zhuǎn)位變?yōu)?0: 首先交換該節(jié) 點(diǎn)的左子樹和右子樹，并且給左子樹和右子樹的樹根 的反轉(zhuǎn)位加上 1，如果反轉(zhuǎn)位變成了 2，相當(dāng)于取消反 轉(zhuǎn)，直接將反轉(zhuǎn)位由 2 變成 0 即可。對節(jié)點(diǎn) x 執(zhí)行伸展操作，是在保持伸展樹有序性的前提下，通過一系列的伸展步驟將節(jié)點(diǎn) x 調(diào)整到樹 根處。執(zhí)行伸展操作之前要將相關(guān)節(jié)點(diǎn)的反轉(zhuǎn)位置 0。 伸展步驟11 分三種: 左旋 ( 右旋) 、右 旋 右旋( 左旋 左旋) 、左旋 右旋( 右旋 左旋) 。如圖 1( a) 所示，節(jié)點(diǎn) x 的父節(jié)點(diǎn) y 是根節(jié)點(diǎn)并且 x 是 y 的左孩子，則 向右旋轉(zhuǎn)連接節(jié)點(diǎn) x 和節(jié)點(diǎn) y 的 邊; 如果 x 是 y 的右孩子，則向左旋轉(zhuǎn)連接節(jié)點(diǎn) x 和節(jié) 點(diǎn) y 的邊。如圖 1( b) 所示，節(jié)點(diǎn) x 的父節(jié)點(diǎn) y 不是根節(jié)點(diǎn)， 節(jié)點(diǎn) y 的父節(jié)點(diǎn)是 z，并且 x 和 y 同時(shí)是各自父節(jié)點(diǎn)的 左孩子，則先向右旋轉(zhuǎn)連接節(jié)點(diǎn) y 和 z 的邊，然后向右 旋轉(zhuǎn)連接節(jié)點(diǎn) x 和節(jié)點(diǎn) y 的邊; 如果節(jié)點(diǎn) x 的父節(jié)點(diǎn) y 不是根節(jié)點(diǎn)，節(jié)點(diǎn) y 的父節(jié)點(diǎn)是 z，并且 x 和 y 同時(shí)是 各自父節(jié)點(diǎn)的右孩子，則先向左旋轉(zhuǎn)連接節(jié)點(diǎn) y 和節(jié)74計(jì)算機(jī)技術(shù)與發(fā)展第 24 卷點(diǎn) z 的邊，然后向左旋轉(zhuǎn)連接節(jié)點(diǎn) x 和節(jié)點(diǎn) y 的邊。圖 1伸展步驟如圖 1( c) 所示，節(jié)點(diǎn) x 的父節(jié)點(diǎn) y 不是根節(jié)點(diǎn)， 節(jié)點(diǎn) x 是其父節(jié)點(diǎn) y 的右孩子，節(jié)點(diǎn) y 是其父節(jié)點(diǎn) z 的 左孩子，則先向左旋轉(zhuǎn)連接節(jié)點(diǎn) y 和節(jié)點(diǎn) x 的邊，然后 向右旋轉(zhuǎn)連接節(jié)點(diǎn) x 和節(jié)點(diǎn) z 的邊; 節(jié)點(diǎn) x 的父節(jié)點(diǎn) y 不是根節(jié)點(diǎn)，節(jié)點(diǎn) x 是其父節(jié)點(diǎn) y 的左孩子，節(jié)點(diǎn) y 是 其父節(jié)點(diǎn) z 的右孩子，則先向右旋轉(zhuǎn)連接節(jié)點(diǎn) y 和節(jié) 點(diǎn) x 的邊，然后向左旋轉(zhuǎn)連接節(jié)點(diǎn) x 和節(jié)點(diǎn) z 的邊。伸展樹的存儲結(jié)構(gòu): 伸展樹中一個(gè)節(jié)點(diǎn)對應(yīng)一個(gè) 城市，可以使用散列法將伸展樹的節(jié)點(diǎn)信息存儲在一 個(gè)數(shù)組 SPA 中，城市 c1 節(jié)點(diǎn)的信息存儲在 SPA1中，城市 ci 節(jié)點(diǎn)的信息存儲在 SPAi中，因此，根據(jù)城 市名字 ci 可以在常數(shù)時(shí)間內(nèi)找到城市 ci 在伸展樹中對應(yīng)的節(jié)點(diǎn)位置。Next( a) 操作的實(shí)現(xiàn)過程: 首先找到城市 a 在伸展 樹中的位置，將相關(guān)節(jié)點(diǎn)的反轉(zhuǎn)位變成 0，通過伸展操 作把該節(jié)點(diǎn)調(diào)整到樹根處; 然后從樹根開始，將相關(guān)節(jié) 點(diǎn)的反轉(zhuǎn)位變成 0 后右子樹中最左的節(jié)點(diǎn)就是 a 的后 繼節(jié)點(diǎn) Next( a) ; 最后將 a 的后繼節(jié)點(diǎn) Next( a) 通過伸 展操作調(diào)整到樹根處。Prev( a) 操作的實(shí)現(xiàn)過程: 首先找到城市 a 在伸展 樹中的位置，將相關(guān)節(jié)點(diǎn)的反轉(zhuǎn)位變成 0，通過伸展操作把該節(jié)點(diǎn)調(diào)整到樹根處; 然后從樹根開始，將相關(guān)節(jié) 點(diǎn)的反轉(zhuǎn)位變成 0 后左子樹中最右的節(jié)點(diǎn)就是 a 的前 驅(qū)節(jié)點(diǎn) Prev( a) ; 最后將 a 的前驅(qū)節(jié)點(diǎn) Prev( a) 通過伸 展操作調(diào)整到樹根處。Between( a，b，c) 操作的實(shí)現(xiàn)過程: 首先找到城市 b 的位置，通過伸展操作把節(jié)點(diǎn) b 調(diào)整到樹根處，再找到 節(jié)點(diǎn) a 的位置，通過伸展操作把節(jié)點(diǎn) a 調(diào)整到樹根處， 然后找到節(jié)點(diǎn) c 的位置，通過伸展操作把節(jié)點(diǎn) c 調(diào)整到樹根處。找到節(jié)點(diǎn) b 在伸展樹中的新位置，從節(jié)點(diǎn) b 開始朝樹根方向按照中序遍歷伸展樹，如 果節(jié)點(diǎn) c 比節(jié)點(diǎn) a 先找到并且節(jié)點(diǎn) b 在節(jié)點(diǎn) c 的左子樹中或者 節(jié)點(diǎn) a 比節(jié)點(diǎn) c 先找到并且節(jié)點(diǎn) b 在節(jié)點(diǎn) a 的右子樹 中，則 Between( a，b，c) 返回 True，否則返回 False。Flip( a，b，c，d) 操作的實(shí)現(xiàn)最復(fù)雜。首先找到節(jié) 點(diǎn) d 的位置，通過伸展操作把節(jié)點(diǎn) d 調(diào)整到樹根處，再 找到節(jié)點(diǎn) b 的位置，通過伸展操作把節(jié)點(diǎn) b 調(diào)整到樹 根處，此時(shí)伸展樹將處于下面四種情況之一，如圖 2 所 示。圖 2 中 T1 T4 是節(jié)點(diǎn)的子樹。圖 2節(jié)點(diǎn) d 和節(jié)點(diǎn) b 先后進(jìn)行伸展 操作后伸展樹的四種情況i對于圖 2 中的( a) 、( b) 兩種情況，F(xiàn)lip( a，b，c，d) 操作將對節(jié)點(diǎn) b 和節(jié)點(diǎn) d 之間的路徑進(jìn)行反轉(zhuǎn)，反轉(zhuǎn) 后的伸展樹如圖 3( a) 、( b) 所示。對于圖 2 中的( c) 、 ( d) 兩種情況，F(xiàn)lip( a，b，c，d) 操作將對節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間的路徑進(jìn)行反轉(zhuǎn)，反轉(zhuǎn)后的伸展樹如圖 3( c) 、( d) 所示。圖 3 中，帶雙圈的節(jié)點(diǎn)的反轉(zhuǎn)位是 1，T 表示子 樹 Ti 的根節(jié)點(diǎn)的反轉(zhuǎn)位是 1。圖 3執(zhí)行 Flip( a，b，c，d) 操作后的伸展樹對 n 個(gè)節(jié)點(diǎn)的伸展樹表示的一條巡回路徑執(zhí)行一 系列的 Next、Prev、Between、Flip 操作，每個(gè)操作的平攤 時(shí)間為 O( logn) 11( n 為回路中包含的城市個(gè)數(shù)) 。第 12 期宗德才等: 旅行商問題中巡回路徑的數(shù)據(jù)結(jié)構(gòu)75平攤時(shí)間是指執(zhí)行一系列最壞情況下的每個(gè)操作的平 均時(shí)間。1 3兩級樹表示法在文獻(xiàn)14 15中巡回路徑的 數(shù)據(jù)結(jié)構(gòu)都是用 兩級樹表示的。一條巡回路徑大約被分成 槡n 段子路徑，每段子路 徑中包含 槡n /2 到 2 槡n 個(gè)城市。每段子路徑用一個(gè)段節(jié)點(diǎn)表示，如圖 4 所示。每個(gè)段節(jié)點(diǎn)有 4 個(gè)指針: prev、 next 分別指向前一段子路徑和下一段子路徑，first、last 分別指向子路徑中包含的第一個(gè)城市節(jié)點(diǎn)和最后一個(gè) 城市節(jié)點(diǎn)，每段子路徑中還有 3 個(gè)變量 pos、rev、lens 分 別表示該段子路徑在第一層鏈表中的位置，訪問子路 徑中城市時(shí)是按順時(shí)針方向還是按逆時(shí)針方向和該段 子路徑中包含的城市節(jié)點(diǎn)個(gè)數(shù)有關(guān)。每段子路徑中的 城市節(jié)點(diǎn)用雙向鏈表相互連接起來。每個(gè)城市節(jié)點(diǎn)有 3 個(gè)指針: prevc( 指向前驅(qū)節(jié)點(diǎn)) 、nextc ( 指向后繼節(jié) 點(diǎn)) 、parent( 指向本節(jié)點(diǎn)所在的子路徑) ，還 有 2 個(gè)變 量 num，posc 分別表示該城市的編號和在子路徑中所 處的位置。圖 4 中，兩級樹表示的一條巡回路徑是( c6 ，c8 ，c4 ，c2 ，c9 ，c7 ，c3 ，c5 ，c1 ) 。兩級樹的存儲結(jié)構(gòu): 兩級樹中一個(gè)節(jié)點(diǎn)對應(yīng)一個(gè) 城市，可以使用散列法將兩級樹的節(jié)點(diǎn)信息存儲在一個(gè)數(shù)組 TLA 中，城市 c1 節(jié)點(diǎn)的信息存儲在 TLA1中，城市 ci 節(jié)點(diǎn)的信息存儲在 TLAi中，因此，根據(jù)城 市名字 ci 可以在常數(shù)時(shí)間內(nèi)找到城市 ci 在兩級樹中對 應(yīng)的節(jié)點(diǎn)位置。由于在訪問旅行回路時(shí)可以按照順時(shí)針方向或逆 時(shí)針方向訪問，用一個(gè)變量 eversed 表示在訪問旅行 回路時(shí)的方向，eversed = 0 表示順時(shí)針方向，eversed= 1 表示逆時(shí)針方向。Next( a) 操作的實(shí)現(xiàn)過程: 首先找到城市 a 在兩級 樹中的節(jié)點(diǎn)位置 na，則城市節(jié)點(diǎn) na 的父節(jié)點(diǎn)是 na parent，如果 eversed = 0 并且 na parent 段節(jié)點(diǎn)的 rev 值是 1，即按照逆時(shí)針方向訪問 na parent 段中的 城市，則 Next( a) = a prevc; 如果 eversed = 0 并且 na parent 段節(jié)點(diǎn)的 rev 值是 0，則 Next( a) = a nextc; 如果 eversed = 1 并且 na parent 段節(jié)點(diǎn)的 rev 值是 1， 則 Next( a) = a nextc; 如果 eversed = 1 并且 na parent 段節(jié)點(diǎn)的 rev 值是 0，則 Next( a) = a prevc。Prev( a) 操作的實(shí)現(xiàn)過程與 Next( a) 操作的實(shí)現(xiàn) 過程類似。Between( a，b，c) 操作的實(shí)現(xiàn)過程: 首先找到城市 a、b、c 在兩級樹中的節(jié)點(diǎn)位置 na、nb、nc，則城市節(jié)點(diǎn) a、b、c 的父節(jié)點(diǎn)分別是 na parent、nb parent、nc parent。圖 4兩級樹表示巡回路徑如果 na、nb、nc 在同一個(gè)段 na parent 中，當(dāng) eversed 等于na parent rev 時(shí)，如果滿足條件 na posc nb posc nc posc 或者 nc posc na posc nb posc 或者nb posc nc posc na posc，則Between( a，b，c) 返回 True，否則返回 False; 當(dāng) eversed 不等于na parent rev 時(shí)，如果滿足條件 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 有兩個(gè)節(jié)點(diǎn)在同一個(gè)段中，如果 na、nb 在 同一個(gè)段na parent 中，當(dāng) eversed 等于na parent rev 時(shí)，如果滿足條件 na posc nb posc，則 Between ( a，b，c) 返回 True，否則返回 False; 當(dāng) eversed 不等于 na parent rev 時(shí)，如果滿足條件 na posc nb posc， 則 Between( a，b，c) 返回 True，否則返回 False。如果 na、nc 在 同一個(gè)段na parent 中，當(dāng) eversed 等于na parent rev 時(shí)，如果滿足條件 nc posc na posc，則 Between ( a，b，c) 返回 True，否則返回 False; 當(dāng) eversed 不等于 na 76計(jì)算機(jī)技術(shù)與發(fā)展第 24 卷parent rev 時(shí)，如果滿足條件 na posc nc posc，則 Between( a，b，c) 返回 True，否則返回 False。如果 nb、nc 在同 一個(gè)段 nb parent 中，當(dāng) eversed 等于 nb parent rev 時(shí)，如果滿足條件 nb posc nc posc，則 Between ( a，b，c) 返回 True，否則返回 False; 當(dāng) eversed 不等于 nb parent rev 時(shí)，如果滿足條件 nc posc nb posc， 則 Between( a，b，c) 返回 True，否則返回 False。如果 na、nb、nc 在三個(gè)不同的段中，當(dāng) eversed = 0 時(shí)，如果滿 足條件 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; 當(dāng) eversed = 1 時(shí)，如果滿足條件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) 操作的實(shí)現(xiàn)最復(fù)雜。如果節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間的路徑在同一個(gè)段中并且節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間的長度大于 3 /4 槡n ( 如圖 5( a) 所示) ，那么，當(dāng)節(jié)點(diǎn) a 和節(jié)點(diǎn) b 在同一段中時(shí)，將該段 在節(jié)點(diǎn) a 和節(jié)點(diǎn) b 中間分成兩段并且將長度較短的段 與鄰接段合并以保持段的總個(gè)數(shù)不變，當(dāng)節(jié)點(diǎn) c 和節(jié) 點(diǎn) d 在同一段中時(shí)，將該段在節(jié)點(diǎn) c 和節(jié)點(diǎn) d 中間分 成兩段并且將長度較短的段與鄰接段合并以保持段的 總個(gè)數(shù)不變，然后在同一個(gè)段中將節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之 間的路徑反轉(zhuǎn)，即更新節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間的城市節(jié) 點(diǎn)的 nextc、prevc 指針和 posc 變量的值以及節(jié)點(diǎn) b、d 的 nextc、prevc 指針的值。之間的路徑反轉(zhuǎn)，即更新節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間的城市 節(jié)點(diǎn)的 nextc、prevc 指針和 posc 變量的值以及節(jié)點(diǎn) b、d 的 nextc、prevc 指針的值。如果節(jié)點(diǎn) b 和節(jié)點(diǎn) d 之間的 路徑在同一個(gè)段中，處理方法類似。如果節(jié)點(diǎn) b 和節(jié)點(diǎn) d 之間的路徑與節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間的路徑都是由多個(gè)連續(xù)的完整段組成的( 如圖 6 所示) ，假設(shè)段的總個(gè)數(shù)為 S，令 Lac = c parent pos c parent pos + 1，如果 Lac 0，Lac = Lac + S。 如果 2Lac S，則將節(jié)點(diǎn) b 和節(jié)點(diǎn) d 之間的路徑反轉(zhuǎn)， 即更新 b 和 d 之間的段節(jié)點(diǎn)的 prev、next 指針和 pos 變 量的值以及 a parent、c parent 段節(jié)點(diǎn)的 prev、 next 指針的值。如果 2Lac S，則將節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之 間的路徑反轉(zhuǎn)，即 更新 a 和 c 之間的段節(jié)點(diǎn)的 prev、 next 指針和 pos 變量的值以及 b parent、d par- ent 段節(jié)點(diǎn)的 prev、next 指針的值。圖 6節(jié)點(diǎn) b 和節(jié)點(diǎn) d 之間的路徑與節(jié)點(diǎn) a 和節(jié)點(diǎn)c 之間的路徑都是由多個(gè)連續(xù)的完整段組成如果節(jié)點(diǎn) b 和節(jié)點(diǎn) d 之間的路徑不在同一個(gè)段中 并且節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間的路徑也不在同一個(gè)段中， 那么，當(dāng)節(jié)點(diǎn) a 和節(jié)點(diǎn) b 在同一段中時(shí)，將該段在節(jié)點(diǎn) a 和節(jié)點(diǎn) b 中間分成兩段并且將長度較短的段與鄰接 段合并以保持段的總個(gè)數(shù)不變，當(dāng)節(jié)點(diǎn) c 和節(jié)點(diǎn) d 在同一段中時(shí)，將該段在節(jié)點(diǎn) c 和節(jié)點(diǎn) d 中間分成兩段 并且將長度較短的段與鄰接段合并以保持段的總個(gè)數(shù) 不變，如果分段后，節(jié)點(diǎn) b 和節(jié)點(diǎn) d 之間的路徑在同一 個(gè)段中或節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間的路徑在同一個(gè)段中，則處理方法如圖 5 所示。如果分段后，節(jié)點(diǎn) b 和節(jié)點(diǎn) d 之間的路徑不在同一個(gè)段中并且節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間 的路徑也不在同一個(gè)段中，則處理方法如圖 6 所示。Prev( a) 、Next( a) 和 Between( a，b，c) 操作都能夠 在常數(shù)時(shí)間內(nèi)完成，而 Flip( a，b，c，d) 操作最壞情況下1 4的時(shí)間復(fù)雜度是 O( 槡n )。圖 5節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間的路徑在同一個(gè)段中如果節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間的路徑在同一個(gè)段中并且節(jié)點(diǎn) a 和節(jié)點(diǎn) c 之間的長度小于或等于 3 /4 槡n ( 如 圖 5( b) 所示) ，那么，在同一個(gè)段中將節(jié)點(diǎn) a 和節(jié)點(diǎn) 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ù)組、伸展樹和兩級樹來表示。文中主要詳細(xì)分析了第 12 期宗德才等: 旅行商問題中巡回路徑的數(shù)據(jù)結(jié)構(gòu)77這三種表示方法的具體實(shí)現(xiàn)過程以及每一種數(shù)據(jù)結(jié)構(gòu) 中四種基本操作的時(shí)間復(fù)雜度。當(dāng)巡回路徑用數(shù)組表 示時(shí)，Next( a) 、Prev( a) 和 Between( a，b，c) 操作能夠在 常數(shù)時(shí)間內(nèi)完成，F(xiàn)lip( a，b，c，d) 操作在最壞情況下的 時(shí)間復(fù)雜度是 O( n) ，不適用于大規(guī)模的旅行商問題。 當(dāng)巡回路徑用伸展樹表示時(shí)，每個(gè)操作的平攤時(shí)間復(fù) 雜度為 O( logn) ，適用于極大規(guī)模的旅行商問題。當(dāng) 巡回路徑用兩級樹表示時(shí)，Prev ( a ) 、Next ( a ) 和 Be- tween( a，b，c) 操作都能夠在常數(shù)時(shí)間內(nèi)完成，而 Flip ( a，b，c，d ) 操 作 在 最 壞 情 況 下 的 時(shí) 間 復(fù) 雜 度 是 O ( n1 /2 ) ，適用 于大規(guī)模的旅行商問題。下一步將用 C 語言編程實(shí)現(xiàn)這三種數(shù)據(jù)結(jié)構(gòu)，并通過仿真實(shí)驗(yàn)分析 這三種數(shù)據(jù)結(jié)構(gòu)對 Lin Kernighan 算法等局部搜索算 法在求解旅行商問題時(shí)性能的影響。參考文獻(xiàn):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 宗德才，王 康康 改進(jìn)的嵌套分區(qū)算法求解旅行商問題 J 計(jì)算機(jī)工程與應(yīng)用，2011，47( 24) : 54 576 陳曉峰，宋 杰 量子人工魚群算 法J 東北大學(xué)學(xué)報(bào)( 自然科學(xué)版) ，2012，33( 12) : 1710 17137 蘇曉勤，孫鶴旭，潘旭華 改進(jìn)蜂群算法的旅行商問題仿真J 計(jì)算機(jī)工程與設(shè)計(jì)，2013，34( 4) : 1420 14248 王忠英，白艷萍，岳利霞 經(jīng)過改進(jìn)的求解 TSP 問題的蟻群 算法J 數(shù)學(xué)的實(shí)踐與認(rèn)識，2012，24( 4) : 133 1409 柳 寅，馬 良 模糊人工蜂群算法的旅行商問題求解 J 計(jì)算機(jī)應(yīng)用研究，2013，30( 9) : 2694 269610 申鉉京，劉陽陽，黃永平，等 求解 TSP 問題的快速蟻群算 法J 吉林大學(xué)學(xué)報(bào)( 工學(xué)版) ，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