第1期 李发捷，等：多边形序列的最短路径算法 ·25 同的端点的情形.例如，假设算法1的输入为下列的 2 R算法 数据： 利用以下一个非常简单的二维例子来说明R s1=p,2=pp,4=0,0),=(2,4),9= 算法的基本思想.考虑无约束TPP的一个退化情 3,0),p=1,0,及q=2,0(见图5). 形：每个多边形都收缩成一条单一的直线段（见图 4).以下的算法是R算法的简化了的版本(“弧版 本”.它可以说明原始的R算法的基本原理 图5说明2个脚步元素可能含有相同的端点 Fig,5 Illustration for identical endpoints of steps 作为初始，假设pm和m分别是s和”的中 图4TSP的退化情形，k=3 点.也就是说，p1=(1,2)和p2=(2.5,2).这样就得 Fig 4 Degenerate case of the TPP,for k=3 到初始多边线路即包含于多边形边界的一条路径) 算法1 p=〈p,pm,pm,q的长是5.5616.算法1找到近似的 1)Lete=10~o(选定精确度) 最短路径是P=〈p,p1,p2,q〉，p1=(0.3646, 2)计算初始路径p=〈p,p,pm,p,q〉的长 0.7291),p2=(2.8636,0.5455),它的长是 度h. 4.4944(见表1) 3)Let g=p and i=1. 4)while i<k-1 do 表1初始由图5说明的重复数1和结果6， ①etqp=pi+1； (p1=(1,2)和2=(25,2)作为初始点) ②计算一个点∈，使得 Table 1 Numbor I of iterations and resulting for the initialization illustrated by Fig 5 de(q.)+de(.)=min de(q.q)+ with p =(1,2)and pe=(2 5,2)as initialication points) d(p,q):q'∈s.(d(qm,p)表示两点q,间的 欧几里德距离)： ③更换p为gp以更新路径P: 1 -0.8900 ④etg=p:andi=i+l. -0.1752 5)Let os=q. 3 .0.0019 ①计算一个点∈：使得 -1.2935e-005 d。(p,p)+d(g,p)= 5 -84435e-008 mind de(q,q de(eq):qEs ②更换p:为q2以更新路径P 6 -5.4930e-010 6计算更新路径p=〈p,p,p2,p,q〉的长 7 -3.5740e-012 度h. 7)Let 8=h-k. 现在假定一个不同的初始点的输入，使得p= 8)如果6>￡，令h=h,转到3 p=.在这种情形下，算法1的4)中的②步的输 否则，停止 出将是错误的：所计算的路径p=〈p,p,p2,q〉， 步骤1)的精确度参数ε可以选定给定计算机 p1=和p2=.它的长是8.1231.（文献[2J的 所能保证的最大可能的数量精确度， 引理16，看到在这个例子里，p1≠m,p) 在本文的其余的部分称{，2，sx为R算 称这个初始例子的情形为应用R算法时出现 法的脚步集，而每个5是R算法的一个脚步元素 的一条退化路径.它可能出现在算法的初始化或算 在一个脚步集当中，可能出现2个脚步元素具有相 法后面的重复迭代中间.一般地说，它是定义成为初 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net2 R 算法 利用以下一个非常简单的二维例子来说明 R 算法的基本思想. 考虑无约束 TPP 的一个退化情 形 :每个多边形都收缩成一条单一的直线段 (见图 4) . 以下的算法是 R 算法的简化了的版本 “( 弧版 本”) . 它可以说明原始的 R 算法的基本原理. 图 4 TSP 的退化情形 , k = 3 Fig14 Degenerate case of the TPP ,for k = 3 算法 1 1) Letε= 10 - 10 (选定精确度) . 2) 计算初始路径ρ=〈p , p1 , p2 , …, pk , q〉的长 度 l1 . 3) Let q1 = p and i = 1. 4) while i < k - 1 do ①Let q3 = pi + 1 ; ②计算一个点 q2 ∈si 使得 de ( q1 , q2 ) + de ( q3 , q2 ) = min{ de ( q1 , q′) + de ( q3 , q′) :q′∈si} . ( de ( q1 , q2 ) 表示两点 q1 , q2 间的 欧几里德距离) ; ③更换 pi 为 q2 以更新路径ρ; ④Let q1 = pi and i = i + 1. 5) Let q3 = q , ①计算一个点 q2 ∈sk 使得 de ( q1 , q2 ) + de ( q3 , q2 ) = min{ de ( q1 , q) + de ( q3 , q) :q ∈sk } ; ②更换 pk 为 q2 以更新路径ρ. 6) 计算更新路径ρ=〈p , p1 , p2 , …, pk , q〉的长 度 l2 . 7) Letδ= l1 - l2 . 8) 如果δ>ε,令 l1 = l2 ,转到 3) . 否则 ,停止. 步骤 1) 的精确度参数ε可以选定给定计算机 所能保证的最大可能的数量精确度. 在本文的其余的部分称 { s1 ,s2 , …,sk } 为 R 算 法的脚步集 ,而每个 si 是 R 算法的一个脚步元素. 在一个脚步集当中 ,可能出现 2 个脚步元素具有相 同的端点的情形. 例如 ,假设算法 1 的输入为下列的 数据 : s1 = q1 q2 ,s2 = q2 q3 , q1 = (0 ,0) , q2 = (2 , 4) , q3 = (3 ,0) , p = (1 ,0) ,及 q = (2 ,0) (见图 5) . 图 5 说明 2 个脚步元素可能含有相同的端点 Fig15 Illustration for identical endpoints of step s 作为初始 ,假设 p1 和 p2 分别是 s1 和 s2 的中 点. 也就是说 , p1 = (1 ,2) 和 p2 = (215 ,2) . 这样就得 到初始多边线路(即包含于多边形边界的一条路径) ρ=〈p , p1 , p2 , q〉的长是 51561 6. 算法 1 找到近似的 最短路径是ρ=〈 p , p′1 , p′2 , q〉, p′1 = ( 01364 6 , 01729 1 ) , p′2 = ( 21863 6 , 01545 5 ) , 它 的 长 是 41494 4 (见表 1) . 表 1 初始由图 5 说明的重复数 I 和结果δs ( p1 = (1 ,2) 和 p2 = ( 215 ,2)作为初始点) Table 1 Numbor I of iterations and resultingδs for the initialization illustrated by Fig15 ( with p1 = ( 1 ,2) and p2 = ( 215 ,2) as initialization points) I δ 1 - 01890 0 2 - 01175 2 3 - 01001 9 4 - 11293 5e - 005 5 - 81443 5e - 008 6 - 51493 0e - 010 7 - 31574 0e - 012 现在假定一个不同的初始点的输入 ,使得 p1 = p2 = q2 . 在这种情形下 ,算法 1 的 4) 中的 ②步的输 出将是错误的 :所计算的路径ρ=〈p , p′1 , p′2 , q〉, p′1 = q2 和 p′2 = q2 . 它的长是 81123 1. (文献[2 ]的 引理 16 ,看到在这个例子里 , p1 ≠p0 , p2 ) . 称这个初始例子的情形为应用 R 算法时出现 的一条退化路径. 它可能出现在算法的初始化或算 法后面的重复迭代中间. 一般地说 ,它是定义成为初 第 1 期 李发捷 ,等 :多边形序列的最短路径算法 ·25 ·