| « | August 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | | | | |
|
| 公告 |
本站技术贴除标明为“原创”的之外，其余均为网上转载，文中我会尽量保留原作者姓名，若有侵权请与我联系，我将第一时间做出修改。谢谢！
——既瑜 |
| 统计 |
blog名称:★既瑜★
日志总数:183
评论数量:636
留言数量:-25
访问次数:1405964
建立时间:2005年3月12日 |
OICQ：215768265
njucs2001@hotmail.com
erichoo1982@gmail.com |
|
W3CHINA Blog首页 管理页面 写新日志 退出
 [【技术文档】]具有障碍物的欧几里德最短路径问题 （starfish） |
这个问题是计算几何学中的一个经典课题：具有障碍物的欧几里德最短路径问题(ESP0)
ESPO可以描述如下:给定平面中两点s和t，及多边形障碍物集Ω={ω1,ω2,...,ωk}，要求由s至t并避开所有障碍物的最短路径。
平面中的ESPO问题在多项式时间内可以求解，而E^3中具有多面体障碍物时确定最短路径长度的问题是NP难的。
一个简单的算法如下：由s到t的最短路径是一条折线链，该链的顶点是多边形障碍物的顶点。利用Dijkstra的最短路算法和可视图算法可以求解ESPO问题，其时间复杂性为0(n^2)。如果可视图是稀疏的，则在O(m+nlogn)时间内可以确定解，其中m是可视图边的数目。
对于该问题还有一些更好的算法，下面也一并作简单的介绍：利用最短路径映射SPM(s,Ω)在O(n(k+logn))时间内求解任意多边形障碍物的ESPO问题的方法是由Reif和Storer提出的。如果给定SPM(s,Ω)，则在O(logn)时间内可以确定包含t的域，而在0(b+logn)时间内能够确定到t的路径，其中b是路径上线段的数目。Welzl等人利用可视图给出了求解平面上n条线段的ESPO问题的算法，该算法要求0(n^2)时间。不难修改这个算法使其能处理多边形障碍物，并且具有相同的时间复杂性。注意，如果使用可视图方法，那么对限界0(n^2)将不可能改进。多边形物体中两个物体(而非点)之间的最短路径的0(n^2)算法是已知的。当n是平行线段集合时，Lee和Preparata提出θ(nlogn)平面扫描算法。线段穿过扫描线并且把最短路径映射到扫描线。平面上没有最短路径的0(n^2)算法能处理避开n条任意相交的线段。Rohnert给出平面中避开k个凸障碍物最短路径的O(nlogn+k^2)时间的算法。这个时间限界在O(k^2logn+n)时间和O(n+k^2)空间预处理障碍物的条件下达到。预处理包括构造可视图的子图。Rohnert还给出平面中避开k个凸障碍物最短路径的O(knlogn)时间和O(n)空间的算法。后者不需预先处理障碍物，而是利用Dijkstra最短路径算法在线计算可视性。当平面中有k个凸障碍物并且其边界至多相交两次时，Rohnert给出的算法能找到平面中任意两点之间的最短路径，其时间复杂性为O(nlogn+k^2)。这个时间限界在O(nlogn+k^3)时间和O(n+k^2)空间预处理障碍物的条件下达到。
以上的那些算法你可以参考相关的论文。（去http://cora.whizbang.com/搜索"ESPO"关键字） 对于E^3中有多面体障碍物的情况，因为是NP难的，这里不做讨论，但是现在也有很多成熟的多项式时间近似算法。
|
阅读全文(2185) | 回复(0) | 编辑 | 精华 |
|
