第1期 李发捷，等：多边形序列的最短路径算法 ·29· 以有效地近似解决（见图12） 0.12 (, (Xi.W.Zo) 0.10 0.08 20.06 (x%) 0.04 0.02 10141822×10 图11轴对准矩形 Fig 11 Axis-aligned rectangles 图12算法2应用于q矩形的补的运行时间 补，那么根据定理3，寻找包含于Ⅱ中p和g中间的 Fig 12 Ilustration of measured run time for algorithm 2 欧几里德最短路径是NP完全的， applied to the complements of qrectangles. 定理32)判定是否存在一个长最多L的，回 例4修改例2如下（也只是稍微修改例2当 避以轴对准矩形堆为障碍物的，轴一对准矩形堆中 中的D:假设Ⅱ是一个单连通多面体满足每个关键 的欧几里德最短路径是NP完全的.如果所有轴对 多边形是一个三角形的补.由文献[21的定理32可 准矩形是一或三型q矩形，那么此问题在这种特别 知，包含于中p和q中间的欧几里德最短路径可 的情形下也是NP完全的 以以复杂性K(9·OAVm)来近似计算 例2修改例1当中的Ⅱ：假设Ⅱ是一个简单 例5假设S是k个水平或垂直条的堆.包含 多面体满足每个广义关键多边形是一个三角形.由 于S中的欧几里德最短路径可以以复杂性x(©·O 文献2的定理27可知，包含于Ⅱ中p和g中间的 (付近似计算.根据定理5，寻找该问题的精确解是 欧几里德最短路径可以以复杂性x(9·O(V网) NP完全的 定理52，判定是否存在一个长最多为L的 来近似计算.因此，这种特别的情形的ESP问题可 以有效地近似解决.然而，如果修改使得每个广义 回避以水平或垂直条的堆为障碍物的，欧几里德最 短路径是NP完全的 关键多边形是一个三角形的补，那么根据定理4，寻 例6假设S是k个类似地形的，轴对准矩形 找包含于中p和g中间的欧几里德最短路径是 的堆，包含于S中的欧几里德最短路径可以以复杂 NP完全的： 定理4)判定是否存在一个长最多为L的， 性x(9·O(从来近似计算.根据定理6，寻找该问题 的精确解的最好的己知算法的复杂性是O(k): 回避以三角形堆为障碍物的，欧几里德最短路径是 定理621假设S是k个地形的，轴对准矩形 NP困难的 的堆，S中的欧几里德最短路径可以以复杂性O() 在本文以下的3.3节的例3和例4，近似地解 来计算 决这2个非常困难的问题 例6说明了一个最好的已知算法的复杂性是 3.33个NP完全或NP困难问题 O(k)的精确解问题却可以以复杂性x(g·O(付来 正如本文3.2节一样，再次推广关键多边形的 近似计算（精确度参数ε可以选定给定计算机所能 概念，同样允许无界的多边形.现在应用推广的算法 保证的最大可能的数量精确度)」 2近似地解决本文3.2节所提到的困难问题， 例3修改例1如下：假设Ⅱ是一个单连通多 4结束语 面体，满足每个关键多边形是一个轴对准矩形的补 本文首先详细介绍一个简单版本的R算法作 假设p,q∈满足p:<华，这里V是的顶点集.由 为引导这个算法逼近的基本思想.然后从一个实例， 文献2的定理32可知，包含于Ⅱ中p和g中间的 而且给出一个一般的程序来解释如何处理退化路 欧几里德最短路径可以以复杂性x()·O(V网) 径.最后文章报告当应用R算法的几个版本时的结 来近似计算.因此，这种特别的情形的ESP问题可 果.实例说明R算法定义了一个广阔的可应用的算 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net图 11 轴对准矩形 Fig111 Axis2aligned rectangles 补 ,那么根据定理 3 ,寻找包含于 Ⅱ中 p 和 q 中间的 欧几里德最短路径是 N P 完全的. 定理 3 [12 ] 判定是否存在一个长最多 L 的 ,回 避以轴对准矩形堆为障碍物的 ,轴一对准矩形堆中 的欧几里德最短路径是 N P 完全的. 如果所有轴对 准矩形是一或三型 q 矩形 ,那么此问题在这种特别 的情形下也是 NP 完全的. 例 2 修改例 1 当中的 Ⅱ:假设 Ⅱ是一个简单 多面体满足每个广义关键多边形是一个三角形. 由 文献[2 ]的定理 27 可知 ,包含于 Ⅱ中 p 和 q 中间的 欧几里德最短路径可以以复杂性κ(ε) ·O (| V pq | ) 来近似计算. 因此 ,这种特别的情形的 ESP 问题可 以有效地近似解决. 然而 ,如果修改 Ⅱ使得每个广义 关键多边形是一个三角形的补 ,那么根据定理 4 ,寻 找包含于 Ⅱ中 p 和 q 中间的欧几里德最短路径是 NP 完全的 : 定理 4 [13 ] 判定是否存在一个长最多为 L 的 , 回避以三角形堆为障碍物的 ,欧几里德最短路径是 NP 困难的. 在本文以下的 313 节的例 3 和例 4 ,近似地解 决这 2 个非常困难的问题. 313 3 个 N P 完全或 N P 困难问题 正如本文 312 节一样 ,再次推广关键多边形的 概念 ,同样允许无界的多边形. 现在应用推广的算法 2 近似地解决本文 312 节所提到的困难问题. 例 3 修改例 1 如下 :假设 Ⅱ是一个单连通多 面体 ,满足每个关键多边形是一个轴对准矩形的补. 假设 p , q ∈Ⅱ满足 pz < qz ,这里 V 是 Ⅱ的顶点集. 由 文献[2 ]的定理 32 可知 ,包含于 Ⅱ中 p 和 q 中间的 欧几里德最短路径可以以复杂性κ(ε) ·O (| V pq | ) 来近似计算. 因此 ,这种特别的情形的 ESP 问题可 以有效地近似解决(见图 12) . 图 12 算法 2 应用于 q 矩形的补的运行时间 Fig112 Illustration of measured run time for algorithm 2 applied to the complements of q2rectangles. 例 4 修改例 2 如下 (也只是稍微修改例 2 当 中的 Ⅱ) :假设 Ⅱ是一个单连通多面体满足每个关键 多边形是一个三角形的补. 由文献[2 ]的定理 32 可 知 ,包含于 Ⅱ中 p 和 q 中间的欧几里德最短路径可 以以复杂性κ(ε) ·O(| V pq | ) 来近似计算. 例 5 假设 S 是 k 个水平或垂直条的堆. 包含 于 S 中的欧几里德最短路径可以以复杂性κ(ε) ·O ( k) 近似计算. 根据定理 5 ,寻找该问题的精确解是 NP 完全的. 定理 5 [12 ] 判定是否存在一个长最多为 L 的 , 回避以水平或垂直条的堆为障碍物的 ,欧几里德最 短路径是 N P 完全的. 例 6 假设 S 是 k 个类似地形的 ,轴对准矩形 的堆 ,包含于 S 中的欧几里德最短路径可以以复杂 性κ(ε) ·O( k) 来近似计算. 根据定理 6 ,寻找该问题 的精确解的最好的已知算法的复杂性是 O( k 4 ) : 定理 6 [12 ] 假设 S 是 k 个地形的 ,轴对准矩形 的堆 , S 中的欧几里德最短路径可以以复杂性O ( k 4 ) 来计算. 例 6 说明了一个最好的已知算法的复杂性是 O( k 4 ) 的精确解问题却可以以复杂性κ(ε) ·O( k) 来 近似计算(精确度参数ε可以选定给定计算机所能 保证的最大可能的数量精确度) . 4 结束语 本文首先详细介绍一个简单版本的 R 算法作 为引导这个算法逼近的基本思想. 然后从一个实例 , 而且给出一个一般的程序来解释如何处理退化路 径. 最后文章报告当应用 R 算法的几个版本时的结 果. 实例说明 R 算法定义了一个广阔的可应用的算 第 1 期 李发捷 ,等 :多边形序列的最短路径算法 ·29 ·