第1期 李发捷，等：多边形序列的最短路径算法 ·27· 度h 7)Let 6=h-k. 8如果6>e,令h=b,返回3). 否则，停止 算法2的输入例子见图7.图8显示一些测量 的时间用以说明算法的时间复杂性（正确性和时间 复杂性的证明见文献[2).解旅游问题动物园看护 人问题约束TPP问题和看守人路线问题的算法都 可以由修改算法2而获得) 图9说明子程序1 Fig 9 Illustration for procedure 1 4)Letq=minf,4}(点的坐标按字典排列次 序比较大小) 5)输出q 如果存在i,j∈1,2，…k使得i≠，0P,n aP+1≠O,那么修改算法2如下：假设pm=p, p+I=q,P6=p,而且P+1=q(算法2与算法3的 图7算法2的输入例子 差别仅在4)中的①和5)中的①.假设P=fp,p1。 Fig.7 Input example for algorithm 2 ph,pk,p时 .0 算法3 0.8 1)Letc=10~0(选定精确度) 0.6 2)计算初始路径p=〈p,pm,pm,p,q〉的长 0.4 度h. 0.2 3)Let g=p and i=1. 4)while i<k-1 do 13151719×10 X ①如果(p:=p.1且p,≠p+)或(p,≠p.1且 图8算法2的运行时间 p,=P+或(p:=P.1且p=p+1),那么应用子程 Fig.8 Measured run times for algorithm 2 序1计算一点p,使得p:卡p.且p,≠p+1 ②Letp=pi+1: 以下的子程序用以处理退化路出现的情形.当 ③计算一个点∈aP(参见文献21中引理53 应用算法3（它是算法2的一个变形）于无约束TPP 的证明)使得d.(,)+d.(,)=min{d(, 时，因为所有的多边形未必都有两两不相交的，有必 q)+d.(,9):q∈8P}其中a卫是多边形P,的 要处理这样情况 边界.)： 子程序1 ④更换p,为q2以更新路径P: 输入：一点p和2个多边形B和P使得p2∈ ⑤etqm=p:和i=i+1. aP∩8B(见图9). 5)①如果(pk=pk.1且pk卡pk+1)或(p:卡pk.1 输出：一点q∈aP使得d.(g,p≤e而且q 且pk=pk+)或(P=pk.1且p:=pk+),那么应用子 0P2 程序1计算一点P:使得pk卡p.1且p:≠pk+1: 1)Let￡=10~0（选定精确度）； ②etp=q 2)寻找一点e∈EP)使得p∈e1∩a,此处 ③计算一个点∈P:使得d:(,p)+ j=1,2: d.(.)=min d.(aq)d.(gs g):qp 3)Let er=q.假设p和年分别是线段mp ④更换p:为92以更新路径P 和qpp上的两点（见图9）使得d。(g,p)≤e而且 6)计算更新路径p=〈p,pm,pm,pk,q〉的长 9乃，此处j=1,2; 边h. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net度 l2 . 7) Letδ= l1 - l2 . 8) 如果δ>ε,令 l1 = l2 ,返回 3) . 否则 ,停止. 算法 2 的输入例子见图 7. 图 8 显示一些测量 的时间用以说明算法的时间复杂性 (正确性和时间 复杂性的证明见文献[2 ]) . 解旅游问题、动物园看护 人问题、约束 TPP 问题和看守人路线问题的算法都 可以由修改算法 2 而获得[2 ] ) . 以下的子程序用以处理退化路出现的情形. 当 应用算法 3 (它是算法 2 的一个变形) 于无约束 TPP 时 ,因为所有的多边形未必都有两两不相交的 ,有必 要处理这样情况. 子程序 1 输入 :一点 p 和 2 个多边形 P1 和 P2 使得 p2 ∈ 9 P1 ∩9 P2 (见图 9) . 输出 :一点 q ∈9 P1 使得 de ( q , p) ≤ε而且 q 9 P2 . 1) Letε= 10 - 10 (选定精确度) ; 2) 寻找一点 ej ∈E ( Pj ) 使得 p ∈e1 ∩e2 , 此处 j = 1 ,2 ; 3) Let e1 = q1 q2 . 假设 q3 和 q4 分别是线段 q1 p 和 q2 p 上的两点 (见图 9) 使得 de ( qj , p) ≤ε而且 qj ≠9 P2 ,此处 j = 1 ,2 ; 图 9 说明子程序 1 Fig19 Illustration for procedure 1 4) Let q = min{ q3 , q4 } (点的坐标按字典排列次 序比较大小) . 5) 输出 q. 如果存在 i , j ∈{ 1 , 2 , …, k} 使得 i ≠j , 9 Pi ∩ 9 Pi + 1 ≠ ª, 那么修改算法 2 如下 : 假设 p0 = p , pk + 1 = q , P0 = p ,而且 Pk + 1 = q (算法 2 与算法 3 的 差别仅在 4) 中的 ①和 5) 中的 ①) . 假设 P = { p , p1 , p2 , …, pk , p} . 算法 3 1) Letε= 10 - 10 (选定精确度) . 2) 计算初始路径ρ=〈p , p1 , p2 , …, pk , q〉的长 度 l1 . 3) Let q1 = p and i = 1. 4) while i < k - 1 do ①如果 ( pi = pi - 1 且 pi ≠pi + 1 ) 或 ( pi ≠pi - 1 且 pi = pi + 1 ) 或( pi = pi - 1 且 pi = pi + 1 ) ,那么应用子程 序 1 计算一点 pi 使得 p i ≠pi - 1且 pi ≠pi + 1 ; ②Let q3 = pi + 1 ; ③计算一个点 q2 ∈9 Pi (参见文献[2 ]中引理 53 的证明) 使得 de ( q1 , q2 ) + de ( q3 , q2 ) = min{ de ( q1 , q′) + de ( q3 , q′) :q′∈9 Pi} (其中 9 Pi 是多边形 Pi 的 边界. ) ; ④更换 pi 为 q2 以更新路径ρ; ⑤Let q1 = pi 和 i = i + 1. 5) ①如果 ( pk = pk - 1 且 pk ≠pk + 1 ) 或 ( pk ≠pk - 1 且 pk = pk + 1 ) 或( pk = pk - 1且 pk = pk + 1 ) ,那么应用子 程序 1 计算一点 pk 使得 p k ≠pk - 1且 pk ≠pk + 1 ; ②Let q3 = q; ③计算一个点 q2 ∈9 Pk 使得 de ( q1 , q2 ) + de ( q3 , q2 ) = min { de ( q1 q) + de ( q3 q) :q ∈9 Pk } ; ④更换 pk 为 q2 以更新路径ρ. 6) 计算更新路径ρ=〈p , p1 , p2 , …, pk , q〉的长 边 l2 . 第 1 期 李发捷 ,等 :多边形序列的最短路径算法 ·27 ·