第3卷第1期 智能系统学报 Vol.3№1 2008年2月 CAAI Transactions on Intelligent Systems Fcb.2008 多边形序列的最短路径算法 李发捷，KL ETTE Reinhard (1.格罗宁根大学数学与计算科学学院，荷兰格罗宁根9700：2.奥克兰大学计算机科学系，新西兰奥克兰1142) 摘要：给定平面上一个含k个简单多边形的序列及一个起点p和一个终点q,近似地计算一条最短路径使得它开 始于P点，然后按指定的次序访问每个多边形，最后终止于q点.如果多边形是两两不相交且是非凸的，那么此问题 至今还没有算法解.应用一种R算法，给出复杂性为x(9·O(W的一种近似算法，这里n是给定多边形的顶点总数， 函数x(g定义为L。与L的差与e的商，其中Lo是初始路径长度，L是最优路径长度，e是计算精确度.给定的R算 法稍作修改也能用来近似地解决3个NP完全或NP困难的三维欧几里德最短路径问题(ESP).它们的复杂性均为 k(9·O(利，这里k是含有所给定的障碍物的堆的层数. 关键词：算法；最短路径；旅游多边形；部件切割；q矩形 中图分类号：TP202+7文献标识码：A文章编号：1673-4785(2008)01-0023-08 Shortest path algorithms for sequences of polygons LI Fa-jie',KL ETTE Reinhard2 (1.Institute for Mathematics and Computing Science,University of Groningen P.O.Box 800,9700 AV Groningen,The Nether- lands;2.Computer Science Department,The University of Auckland Private Bag 92019,Auckland 1142,New Zealand) Abstract:Given a sequence of k simple polygons in a plane,and a start point p,a target point q.We ap- proximately compute a shortest path that starts at p,then visit each of the polygons in the specified order, and finally end at g.So far no solution is known if the polygons are disjoint with each other and nomcon- vex.By applying a rubberband algorithm,we give an approximate algorithm with time complexity in K(O(n,where n is the total number of vertices of the given polygons,and function K(is the differ- ence between Lo and L over e,where Lo is the length of the initial path,and L is the true (i.e.,optimum) path length.The given rubberband algorithm can also be applied to solve approximately three NP-complete or NPhard 3D Euclidean shortest path (ESP)problems in K((,where k is the number of layers in a stack which contains the defined obstacles. Key words:rubberband algorithm;shortest paths;touring polygons;parts cutting;qrectangles 1问题的提出 本文报告R算法的一些应用.R算法最初由文 献[1]提出，然后文献[2]加以详细研究.在详细说 1.1旅游多边形问题 明R算法之前，首先描述2个紧密相关的问题，旅 回忆文献[3所引入的一些概念和符号.该文首 游多边形问题和部件切割问题，文中将给出它们的 次提出旅游多边形问题.假设π是一个平面，它可以 近似解.本文第2节介绍R算法的基本原理和一些 表示成R.考虑多边形P,Cπ，这里i=1,2,k及 应用时应注意的问题，第3节举例说明它关于旅游 两点p,g∈刀假如pm=p及p+1=q,p:∈R2,此处 多边形问题和q矩形问题的应用，第4节结束 i=1,2,k,p以p,pi,pm,p,q)表示路径ppmp 全文 …paq CRi.假如p(p,q〉表示路径p(p,p1,p, 收稿日期：2007-0616. pk,q〉不会引起混淆，p,∈P,满足p,是aP,∩p(p 通讯作者：李发捷.上mail:F.li@rug.nl. p〉上的沿着路径第一点(aP,表示P,的边界，以下 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3 卷第 1 期 智 能 系 统 学 报 Vol. 3 №. 1 2008 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2008 多边形序列的最短路径算法 李发捷1 , KL ETTE Reinhard 2 (1. 格罗宁根大学 数学与计算科学学院 ,荷兰 格罗宁根 9700 ;2. 奥克兰大学 计算机科学系 ,新西兰 奥克兰 1142) 摘 要 :给定平面上一个含 k 个简单多边形的序列及一个起点 p 和一个终点 q ,近似地计算一条最短路径使得它开 始于 p 点 ,然后按指定的次序访问每个多边形 ,最后终止于 q点. 如果多边形是两两不相交且是非凸的 ,那么此问题 至今还没有算法解. 应用一种 R 算法 ,给出复杂性为κ(ε) ·O( n) 的一种近似算法 ,这里 n 是给定多边形的顶点总数 , 函数κ(ε) 定义为 L0 与 L 的差与ε的商 ,其中 L0 是初始路径长度 , L 是最优路径长度 ,ε是计算精确度. 给定的 R 算 法稍作修改也能用来近似地解决 3 个 NP 完全或 NP 困难的三维欧几里德最短路径问题 ( ESP) . 它们的复杂性均为 κ(ε) ·O( k) ,这里 k 是含有所给定的障碍物的堆的层数. 关键词 :R 算法 ;最短路径 ;旅游多边形 ;部件切割 ;q 矩形 中图分类号 : TP202 + 7 文献标识码 :A 文章编号 :167324785 (2008) 0120023208 Shortest path algorithms for sequences of polygons L I Fa2jie 1 , KL ETTE Reinhard 2 (1. Institute for Mathematics and Computing Science , University of Groningen P. O. Box 800 ,9700 AV Groningen ,The Nether2 lands; 2. Computer Science Department , The University of Auckland Private Bag 92019 , Auckland 1142 , New Zealand) Abstract :Given a sequence of k simple polygons in a plane , and a start point p , a target point q. We ap2 proximately comp ute a shortest pat h that starts at p , t hen visit each of t he polygons in t he specified order , and finally end at q. So far no solution is known if t he polygons are disjoint wit h each ot her and non2con2 vex. By applying a rubberband algorit hm , we give an approximate algorit hm with time complexity in κ(ε) ·O( n) , where n is t he total number of vertices of t he given polygons , and f unctionκ(ε) is the differ2 ence between L0 and L overε, where L0 is the length of t he initial pat h , and L is the true (i. e. , optimum) path lengt h. The given rubberband algorithm can also be applied to solve app roximately t hree N P2complete or NP2hard 3D Euclidean shortest pat h ( ESP) problems inκ(ε) ·O( k) , where k is t he number of layers in a stack which contains the defined obstacles. Keywords :rubberband algorit hm ;shortest pat hs ; touring polygons ; parts cutting ; q2rectangles 收稿日期 :2007206216. 通讯作者 :李发捷. E2mail : F. li @rug. nl. 本文报告 R 算法的一些应用. R 算法最初由文 献[ 1 ]提出 ,然后文献[ 2 ]加以详细研究. 在详细说 明 R 算法之前 ,首先描述 2 个紧密相关的问题 ,旅 游多边形问题和部件切割问题 ,文中将给出它们的 近似解. 本文第 2 节介绍 R 算法的基本原理和一些 应用时应注意的问题 ,第 3 节举例说明它关于旅游 多边形问题和 q 矩形问题的应用 , 第 4 节结束 全文. 1 问题的提出 111 旅游多边形问题 回忆文献[3 ]所引入的一些概念和符号. 该文首 次提出旅游多边形问题. 假设π是一个平面 ,它可以 表示成 R 2 . 考虑多边形 Pi <π,这里 i = 1 ,2 , …, k 及 两点 p , g ∈π. 假如 p0 = p 及 p k + 1 = q , pi ∈R 2 ,此处 i = 1 ,2 , …, k ,ρ〈p , p1 , p2 , …, pk , q〉表示路径 p p1 p2 …pkq < R 2 . 假如ρ〈p , q〉表示路径ρ〈p , p1 , p2 , …, pk , q〉不会引起混淆 , pi ∈Pi 满足 p i 是 9 Pi ∩ρ〈p , pi〉上的沿着路径第一点( 9 Pi 表示 Pi 的边界 ,以下