·28· 智能系统学报 第3卷 7)Letδ=h-h. 这一段应用算法2有效地解2个特殊的ESP 8)如果6>c,令h=h,转3) 问题.还指出了，这两问题的“补问题”是NP困难的 否则，停止 或NP完全的 文献2J的11.5节应用这个算法证明在所有简 关键多边形的概念的推广：假定Ⅱ是一个简单 单多边形是未必两两不相交和非凸的情形下，TPP 连通可能无界)的多面体，而且允许关键多边形是 可以有复杂性为多项式时间的近似算法解： 无界的.例如，一个广义关键多边形可以有一个顶点 定理1I无约束TPP存在复杂性为 在无穷远，或它可以是一个关键多边形的补 x(g·O(W的一种近似算法，这里n是给定多边形 使用文献12所引入的一些概念，假设(x0,, 的顶点总数 0)是三维空间中的一个点， 根据以下定理，寻找这个问题的精确解是NP S=f(x,y,:m≤x<∞∧b≤y<y: 困难的： 品={(x,y,D):-∞<x≤m∧w≤y<g: 定理2BI对于任何Minkowski距离Lp(p), S={(x,y,D):-∞<x≤m八∞<y≤} 如果多边形P是非凸的，且它们的边与x轴成0°45° S={(x,y,2D):m≤x<∞八∞<y≤0 或90°，那么旅游多边形问题TPP是NP困难的 S,称为一个1型q矩形，这里1=1,2,3,4.进 3.2q矩形 而，假设(x1,片，0)是三维空间中的一个点，满足 对于放置于笛卡尔直角坐标系xy:中的三维 欧几里德空间中一个简单多面体即一个同胚于一 x1>x0且y1>0. 个单位球的紧的多面体区域)，表示为Ⅱ假设Ⅱ的 Sm={(x,y,o):-∞<x<∞Λ地≤y≤n: 边集是E,顶点集是V={m,2,…m S,={(x,y,:0≤x≤m八∞<y< 对于p∈Ⅱ，假设。是经过p而且平行于xoy 假设S(S)称为一个水平垂直)条， 面的平面，π。∩是有限个简单多边形组成的集合. S4=f(x,y,):m≤x<∞∧0≤y≤n}: 单个点看作是一个退化多边形.假设P是一个由P S%=x,y,):-∞<x≤∧b≤y≤n} 和π决定的这类简单多边形 S=f(x,y,):m≤x≤nΛw≤y<g; 任何简单多边形P是π。∩的一个连通部分， Sn=(x,y,0):0≤x≤1Λ∞<y≤b} 称为的相对于p的一个关键多边形 按照它们的几何形状，注意到 任何顶点p决定有限个关键多边形集.考虑任 S[S,S,S4]在(+x,+以[(-x,+以，(-x 何顶点p只确定一个关键多边形而且它是凸的情 -以，(+x,-y以]方向上是无界的：s[s1在 形：一个简单多面体是一个一型简单多面体当且仅 土x[y]方向上是无界的：s[Si Sy S]在+x 当任何顶点恰好确定一个凸关键多边形（图10 [-x,+y,-y方向上是无界的. ().一个简单多面体是一个二型简单多面体当且 S:、Sa、S,、S,和S,是轴对准矩形（见图11），这 仅当任何顶点恰好确定一个关键多边形（图10 里i=1,2,3,4,j=1,2.如果S中每个矩形在4个方 (b创) 向-x、+x、~y或+y中至少一个方向上是无界 的，轴对准矩形的堆（一个两两平行但不相交的轴对 准矩形的集合)S称为类似地形的 例1假设是一个简单多面体满足每个广义 关键多边形是轴对准矩形.假设p、q∈Ⅲ满足p:< ,Vg={v:p:<:<g且v白}，这里V是的顶 点集.由文献2]的定理27可知，包含于中p和q a)一型简单多面体 (b)二型简单多面体 中间的欧几里德最短路径可以以复杂性 x(g·O(V)来近似计算.因此，这种特别的情形 图10简单多面体 的E$P问题可以有效地近似解决.然而，如果修改 Fig 10 Polyhedron 使得每个广义关键多边形是一个轴对准矩形的 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net7) Letδ= l1 - l2 . 8) 如果δ>ε,令 l1 = l2 ,转 3) . 否则 ,停止. 文献[2 ]的 1115 节应用这个算法证明在所有简 单多边形是未必两两不相交和非凸的情形下 , TPP 可以有复杂性为多项式时间的近似算法解 : 定理 1 [2 ] 无 约 束 TPP 存 在 复 杂 性 为 κ(ε) ·O( n) 的一种近似算法 ,这里 n 是给定多边形 的顶点总数. 根据以下定理 ,寻找这个问题的精确解是 NP 困难的 : 定理 2 [3 ] 对于任何 Minkowski 距离 Lp ( p ≥1) , 如果多边形 Pi 是非凸的,且它们的边与 x 轴成 0°、45° 或 90°,那么旅游多边形问题( TPP)是 NP 困难的. 312 q 矩形 对于放置于笛卡尔直角坐标系 x y z 中的三维 欧几里德空间中一个简单多面体 (即一个同胚于一 个单位球的紧的多面体区域) ,表示为 Ⅱ. 假设 Ⅱ的 边集是 E,顶点集是 V = { v1 , v2 , …, vn } . 对于 p ∈Ⅱ,假设πp 是经过 p 而且平行于 x oy 面的平面 ,πp ∩Ⅱ是有限个简单多边形组成的集合. 单个点看作是一个退化多边形. 假设 P 是一个由 p 和π决定的这类简单多边形. 任何简单多边形 P 是πp ∩Ⅱ的一个连通部分 , 称为 Ⅱ的相对于 p 的一个关键多边形. 任何顶点 p 决定有限个关键多边形集. 考虑任 何顶点 p 只确定一个关键多边形而且它是凸的情 形 :一个简单多面体是一个一型简单多面体当且仅 当任何顶点恰好确定一个凸关键多边形 (图 10 ( a) ) . 一个简单多面体是一个二型简单多面体当且 仅当任何顶点恰好确定一个关键多边形 (图 10 ( b) ) . 图 10 简单多面体 Fig110 Polyhedron 这一段应用算法 2 有效地解 2 个特殊的 ESP 问题. 还指出了 ,这两问题的“补问题”是 NP 困难的 或 NP 完全的. 关键多边形的概念的推广 :假定 Ⅱ是一个简单 连通(可能无界) 的多面体 ,而且允许关键多边形是 无界的. 例如 ,一个广义关键多边形可以有一个顶点 在无穷远 ,或它可以是一个关键多边形的补. 使用文献[12 ]所引入的一些概念 ,假设( x0 , y0 , z0 ) 是三维空间中的一个点 , S1 = { ( x , y ,z0 ) :x0 ≤x < ∞∧y0 ≤y < ∞}; S2 = { ( x , y ,z0 ) : - ∞< x ≤x0 ∧y0 ≤y < ∞}; S3 = { ( x , y ,z0 ) : - ∞< x ≤x0 ∧- ∞< y ≤y0 }; S4 = { ( x , y ,z0 ) :x0 ≤x < ∞∧- ∞ < y ≤y0 }. S i 称为一个 i 型 q 矩形 ,这里 i = 1 , 2 , 3 , 4. 进 而 ,假设 ( x1 , y1 , z0 ) 是三维空间中的一个点 ,满足 x1 > x0 且 y1 > y0 . Sh = { ( x , y ,z0 ) : - ∞< x < ∞∧y0 ≤y ≤y1 }; Sv = { ( x , y ,z0 ) :x0 ≤x ≤x1 ∧- ∞ < y < ∞}. 假设 S h ( S v ) 称为一个水平(垂直) 条 , Sh 1 = { ( x , y ,z0 ) :x0 ≤x < ∞∧y0 ≤y ≤y1 } ; Sh 2 = { ( x , y ,z0 ) : - ∞< x ≤x1 ∧y0 ≤y ≤y1 }; Sv 1 = { ( x , y ,z0 ) :x0 ≤x ≤x1 ∧y0 ≤y < ∞} ; Sv 2 = { ( x , y ,z0 ) :x0 ≤x ≤x1 ∧- ∞< y ≤y0 }. 按照它们的几何形状 ,注意到 S1 [ S2 , S3 , S4 ]在( + x , + y) [ ( - x , + y) , ( - x , - y) , ( + x , - y ) ] 方 向 上 是 无 界 的; sh [ sv ] 在 ±x [ ±y ]方向上是无界的; sh 1 [ sh 2 sv 1 sv 2 ] 在 + x [ - x , + y , - y ]方向上是无界的. S i 、S h 、S v 、S h j 和 S v j 是轴对准矩形(见图 11) ,这 里 i = 1 ,2 ,3 ,4 , j = 1 ,2. 如果 S 中每个矩形在 4 个方 向 - x、+ x、- y 或 + y 中至少一个方向上是无界 的 ,轴对准矩形的堆(一个两两平行但不相交的轴对 准矩形的集合) S 称为类似地形的. 例 1 假设 Ⅱ是一个简单多面体满足每个广义 关键多边形是轴对准矩形. 假设 p、q ∈Ⅱ满足 pz < qz ,V pq = { v : pz < vz < qz 且 v ∈V } ,这里 V 是 Ⅱ的顶 点集. 由文献[2 ]的定理 27 可知 ,包含于 Ⅱ中 p 和 q 中间 的 欧 几 里 德 最 短 路 径 可 以 以 复 杂 性 κ(ε) ·O(| V pq | ) 来近似计算. 因此 ,这种特别的情形 的 ESP 问题可以有效地近似解决. 然而 ,如果修改 Ⅱ使得每个广义关键多边形是一个轴对准矩形的 ·28 · 智 能 系 统 学 报 第 3 卷