·24 智能系统学报 第3卷 同)，那么说路径p(p,q〉访问P于p,点，此处i= 1,2,…k 无约束TPP问题定义如下： 在平面上如何寻找出一条欧几里德最短路径 Pp,p,p,p,q〉，使得它按给定次序(i=1,2, 付访问每个多边形P 假定对于任意i,j∈1,2，…k,0P∩8P= 0,而且每个P,都是凸的，文献37讨论这类特别情 形并且给出复杂性为O(kdog(W))的算法解.这 图1说明文献[4]中简化的PTSP(假定这里多边形 里n是平面π上所有多边形P,的顶点总数，1=1， 按照给定次序访问) 2,…k Fig 1 Illustration for the simplified P TSP in Ref.[4]where 根据他们的结果，文献3指出，“一个最能引起 polygons are assumed to be given in a particular order 兴趣的公开的问题是确定两两不相交的非凸的简单 多边形的TPP复杂性” 法，进而按启发式方法解决这个简化了的P 本文3.1节的算法2针对这个问题给出一个复 TSP.但它没有给出这个方法的复杂性分析的证明： 杂性为x(g·O(m的一种近似算法，这里n是给定 作为文献[4]的工作的后续工作，文献[11]证明了一 所有多边形的顶点总数，￡是精确度 个进一步简化了的PTSP(即文献[11]只考虑凸多 1.2部件切割问题 边形，且这些多边形按照给定次序访问)是多项式时 在各种各样的加工工业上，例如制衣、制窗、机 间可解的（见图2）.如果再加上一个条件：起点是给 械加工等，常常需要从大片的纸、布料玻璃金属上 定的（见图3），那么称他们能解决这个问题，算法的 面切割出很多的部件假如以简单多边形为模型). 复杂性是O(kdog(/)).这里n是平面上所有多 受到这些应用的启发，文献[4提出3种切割模式： 边形的顶点总数，aPCT,i=1,2,,k )连续切割问题：切割工具访问每个对象（例如 简单多边形正好一次.切割刀具可以从对象的边缘 上任意一点开始，但在移动到下一对象前必须切割 完整个对象.因此，那个对象的进入点和离开点必须 是同一点. 2)端点切割问题：进入和退出每个对象的某个 预先规定的边沿点.但可以切割每个对象成为几个 部分.也就是说，它可以重复地访问一个对象 图2说明文献[11]中进一步简化的P-TSP 3)间歇切割问题：这是最一般的情形.每个对象 (假定这里多边形全是凸的) 可以被切割成为几个部分而且进入和离开点没有受 Fig.2 Illustration for the further simplified 到限制. P-TSP in Ref.11]also assuming convex polygons 文献[4]集中考虑每个对象都是一个简单多边 形的连续切割问题.他们称这个问题为模板切割旅 行售货员问题(PTSP).它是著名的旅行售货员问 题(TSP)的推广例 PTSP可进一步推广到广义的TSP (GTSP)).如果每个多边形都退化成一个单一顶 点，那么PTSP就变成TSP,是己知NP困难的 由此可知PTSP也是NP困难的 图3说明文献[3]中的PTSP(假定这里给定起点s) PTSP的困难使得文献[4]添加上一个条件来 Fig.3 Illustration for the P-TSP as considered 考虑这个问题：假定所有多边形都按一个给定的次 in Ref.[3].now also with a given start point s 序访问（见图1），于是基于一种拉格朗日放松方 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net同) ,那么说路径ρ〈p , q〉访问 Pi 于 p i 点 ,此处 i = 1 ,2 , …, k. 无约束 TPP 问题定义如下 : 在平面上如何寻找出一条欧几里德最短路径 ρ〈p , p1 , p2 , …, pk , q〉,使得它按给定次序 ( i = 1 , 2 , …, k) 访问每个多边形 Pi . 假定对于任意 i , j ∈{ 1 , 2 , …, k} , 9 Pi ∩9 Pj = ª,而且每个 Pi 都是凸的 ,文献[3 ]讨论这类特别情 形并且给出复杂性为 O ( knlog ( n/ k) ) 的算法解. 这 里 n 是平面π上所有多边形 Pi 的顶点总数 , i = 1 , 2 , …, k. 根据他们的结果 ,文献[3 ]指出“, 一个最能引起 兴趣的公开的问题是确定两两不相交的非凸的简单 多边形的 TPP 复杂性”. 本文 311 节的算法 2 针对这个问题给出一个复 杂性为κ(ε) ·O( n) 的一种近似算法 ,这里 n 是给定 所有多边形的顶点总数 ,ε是精确度. 112 部件切割问题 在各种各样的加工工业上 ,例如制衣、制窗、机 械加工等 ,常常需要从大片的纸、布料、玻璃、金属上 面切割出很多的部件 (假如以简单多边形为模型) . 受到这些应用的启发 ,文献[4 ]提出 3 种切割模式 : 1) 连续切割问题 :切割工具访问每个对象(例如 简单多边形) 正好一次. 切割刀具可以从对象的边缘 上任意一点开始 ,但在移动到下一对象前必须切割 完整个对象. 因此 ,那个对象的进入点和离开点必须 是同一点. 2) 端点切割问题 :进入和退出每个对象的某个 预先规定的边沿点. 但可以切割每个对象成为几个 部分. 也就是说 ,它可以重复地访问一个对象. 3) 间歇切割问题 :这是最一般的情形. 每个对象 可以被切割成为几个部分而且进入和离开点没有受 到限制. 文献[4 ]集中考虑每个对象都是一个简单多边 形的连续切割问题. 他们称这个问题为模板切割旅 行售货员问题 (P2TSP) . 它是著名的旅行售货员问 题( TSP) 的推广[5 ] . P2TSP 可 进 一 步 推 广 到 广 义 的 TSP ( GTSP) [627 ] . 如果每个多边形都退化成一个单一顶 点 ,那么 P2TSP 就变成 TSP ,是已知 N P 困难的[8 ] . 由此可知 P2TSP 也是 NP 困难的. P2TSP 的困难使得文献[4 ]添加上一个条件来 考虑这个问题 :假定所有多边形都按一个给定的次 序访问 (见图 1) ,于是基于一种拉格朗日放松方 图 1 说明文献[4 ]中简化的 P2TSP(假定这里多边形 按照给定次序访问) Fig11 Illustration for the simplified P2TSP in Ref. [4] where polygons are assumed to be given in a particular order 法[9210 ] ,进而按启发式方法解决这个简化了的 P2 TSP. 但它没有给出这个方法的复杂性分析的证明. 作为文献[ 4 ]的工作的后续工作 ,文献[11 ]证明了一 个进一步简化了的 P2TSP(即文献[ 11 ]只考虑凸多 边形 ,且这些多边形按照给定次序访问) 是多项式时 间可解的(见图 2) . 如果再加上一个条件 :起点是给 定的(见图 3) ,那么称他们能解决这个问题 ,算法的 复杂性是 O( knlog ( n/ k) ) . 这里 n 是平面上所有多 边形的顶点总数 , 9 Pi <π, i = 1 ,2 , …, k. ·24 · 智 能 系 统 学 报 第 3 卷