第2期 周蓝海，等：TSP冰晶算法 ·169· 1.2.3局部扰动 范围内求点Pk,(如果做扰动的话，在此处加入扰动 初期模型的试验结果表明，在冰晶生长的过程 函数即可)，将P按照xy确定的位置加入点集V, 中，单一依靠距离函数的判定，效果不很理想.自然 删除P中该点 冰晶生长会出现一些临界冰渣，某个区域很难简单 Mi++,goto 3) 判定它是已结冰，还是未结冰，这种混沌现象会影响 5)路径输出：计算回路的长度并输出C 冰晶的继续生长，并诱导路径的错误走向.无序向有 算法终止 序的转化，本文采用微风吹拂湖面，对可能引导进入 时间复杂度：1)为0(log)时间，2)为 歧途的晶胞做局部扰动，扰动后如果小晶胞仍处于 O(klog),k为求n个点的前k个近邻点的时间开 结冰状态，就认定它已正常结冰，扰动的时间复杂度 销系数.3)、4)共小于O(knlogn),5)为常数时间，所 为O(kd 以该算法总的时间复杂度为O(kogm)时间， 2试验设计 3结果分析 本文选取的试验数据是国际TSPL IB和台湾某 本试验选取国际TSPLIB提供的数据和台湾 大学提供的参考数据」 清华大学咨询工程系的部分测试结果 冰晶算法框图如图3。 为了便于比较，对一些TSP求解的近似算法的 初始化点集A 效率有一个直观的认识，表2给出台湾清华大学提 供的参考数据劉.其中“弹性网络”表示1987年由 计算凸壳得到点集 Durbin和Willshaw提出了算法，其精髓是：想象弹 计算点集A的k~邻近 性网络是一个橡皮筋，会自动收缩到最小张力的状 m++ 态，“蚂蚁”表示“蚂蚁算法”，“基因”表示“基因算 mj=n 求P并加入点集严 法”，“人脑"”表示人工一笔画对平面点集求TSP路 径，城市数目比较少时，该算法比较理想.表中百分 输出 比“%”代表试验的结果比参考解高出多少，“”表示 Y 绘图[输出边集即TSP路径 数据空缺，“平均比”表示某算法比参考解高出的百 分比的平均值.“蚂蚁”取得了很好的成绩，平均比为 “2.84%”,2次获得参考解.冰晶算法是一个确定性 图3程序框图 Fig 3 Process diagram 局部算法，平均比为“1.59%” 算法实现： 表2其他TSP模型的试验比较 n表示城市的总数目，mj表示当前点集V中城 Table 2 Comparison of other TSP models 号 市的数目，C表示动态的凝固边界集 试验结果比参考解高出的部分 TSP 输入：给定点集A,包括n个点的坐标P,(x, 弹性网络蚂蚁基因人脑冰品 y)及各点之间的距离Dg,i,j=1,2,n Att48 5.812.863.04.412.19 输出：经过n个点的一条旅行回路C及此回路 Berlin52 6901.52 7.45.18267 的长度 E101 9.107.6414.2883 218 主要步骤为 E151 3.37 441 4.48.98 209 1)围建湖岸.求n个点的凸壳.设V=fm,, St70 4163425.97.031.47 V阿}是凸壳的顶点集，P={p,p2,:pa.画}是 Ulysses16 1.30 0 1.05 012 剩余点集，C=/M2,2内，4，Vv}是凝固 Ulysses22 1.57 0 03 0.45 前沿的动态边界集，初始值为凸壳的边集，j=1,2, 平均比 4.602.845.035.911.59 2)确定搜索范围.求n个点的邻近 试验选取了TSPL IB提供的68个TSP问题， 3)判断是否完全结冰.ifmj=n then C即所求 其中包含了一些有疑问的解，如bays29、gr202等测 回路，goto5); 试数据.冰晶算法直接计算的结果偏离程度不容乐 else goto 4). 观，平均比为8.006%，见表3，其中“参考解”表示目 4)冰晶生长.根据距离函数E(p),在K邻近 前TSPL IB所提供的最短路径长度.“冰晶”表示在 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net11213 局部扰动 初期模型的试验结果表明 ,在冰晶生长的过程 中 ,单一依靠距离函数的判定 ,效果不很理想. 自然 冰晶生长会出现一些临界冰渣 ,某个区域很难简单 判定它是已结冰 ,还是未结冰 ,这种混沌现象会影响 冰晶的继续生长 ,并诱导路径的错误走向. 无序向有 序的转化 ,本文采用微风吹拂湖面 ,对可能引导进入 歧途的晶胞做局部扰动 ,扰动后如果小晶胞仍处于 结冰状态 ,就认定它已正常结冰 ,扰动的时间复杂度 为 O( kn) . 2 试验设计 本文选取的试验数据是国际 TSPL IB 和台湾某 大学提供的参考数据. 冰晶算法框图如图 3. 图 3 程序框图 Fig13 Process diagram 算法实现 : n 表示城市的总数目 , m j 表示当前点集 V 中城 市的数目 , C 表示动态的凝固边界集. 输入 :给定点集 A ,包括 n 个点的坐标 p i ( xi , yi) 及各点之间的距离 Dij , i , j = 1 ,2 , …, n. 输出 :经过 n 个点的一条旅行回路 C 及此回路 的长度. 主要步骤为 1) 围建湖岸. 求 n 个点的凸壳. 设 V = { v1 , v2 , …, vmj}是凸壳的顶点集 , P = { p1 , p2 , …, pn - mj } 是 剩余点集 , C = { v1 v2 , v2 v3 , v3 v4 , …, vmj v 1 } 是凝固 前沿的动态边界集 ,初始值为凸壳的边集 , j = 1 , 2 , …. 2) 确定搜索范围. 求 n 个点的 K2邻近. 3) 判断是否完全结冰. if m j = n t hen C 即所求 回路 , goto 5) ; else goto 4) . 4) 冰晶生长. 根据距离函数 Exy ( pi) ,在 K2邻近 范围内求点 Pk , (如果做扰动的话 ,在此处加入扰动 函数即可) ,将 Pk 按照 x y 确定的位置加入点集 V , 删除 P 中该点. Mj + + ,goto 3) . 5) 路径输出 :计算回路的长度并输出 C. 算法终止. 时间 复 杂 度 : 1 ) 为 O ( nlog n) 时 间 , 2 ) 为 O( knlog n) , k 为求 n 个点的前 k 个近邻点的时间开 销系数. 3) 、4) 共小于 O( k nlog n) ,5) 为常数时间 ,所 以该算法总的时间复杂度为 O( knlog n) 时间. 3 结果分析 本试验选取国际 TSPL IB 提供的数据[7 ]和台湾 清华大学咨询工程系的部分测试结果. 为了便于比较 ,对一些 TSP 求解的近似算法的 效率有一个直观的认识 ,表 2 给出台湾清华大学提 供的参考数据[8 ] . 其中“弹性网络”表示 1987 年由 Durbin 和 Willshaw 提出了算法 ,其精髓是 :想象弹 性网络是一个橡皮筋 ,会自动收缩到最小张力的状 态“, 蚂蚁”表示“蚂蚁算法”“, 基因”表示“基因算 法”“, 人脑”表示人工一笔画对平面点集求 TSP 路 径 ,城市数目比较少时 ,该算法比较理想. 表中百分 比“%”代表试验的结果比参考解高出多少“, 2”表示 数据空缺“, 平均比”表示某算法比参考解高出的百 分比的平均值.“蚂蚁”取得了很好的成绩 ,平均比为 “2184 %”,2 次获得参考解. 冰晶算法是一个确定性 局部算法 ,平均比为“1159 %”. 表 2 其他 TSP 模型的试验比较 Table 2 Comparison of other TSP models % TSP 试验结果比参考解高出的部分 弹性网络 蚂蚁 基因 人脑 冰晶 Att48 5181 2186 310 4141 2119 Berlin52 6190 1152 714 5118 2167 Eil101 9110 7164 1412 8183 2118 Ei151 3137 4141 414 8198 2109 St70 4116 3142 519 7103 1147 Ulysses16 1130 0 2 1105 0112 Ulysses22 1157 0 013 2 0145 平均比 4160 2184 5103 5191 1159 试验选取了 TSPL IB 提供的 68 个 TSP 问题 , 其中包含了一些有疑问的解 ,如 bays29、gr202 等测 试数据. 冰晶算法直接计算的结果偏离程度不容乐 观 ,平均比为 81006 % ,见表 3 ,其中“参考解”表示目 前 TSPL IB 所提供的最短路径长度.“冰晶”表示在 第 2 期 周蓝海 ,等 : TSP 冰晶算法 ·169 ·