多边形序列的最短路径算法

摘要：

给定平面上一个含k个简单多边形的序列及一个起点p和一个终点q,近似地计算一条最短路径使得它开始于p点,然后按指定的次序访问每个多边形,最后终止于q点.如果多边形是两两不相交且是非凸的,那么此问题至今还没有算法解.应用一种R算法,给出复杂性为κ(ε)·O(n)的一种近似算法,这里n是给定多边形的顶点总数,函数κ(ε)定义为L0与L的差与ε的商,其中L0是初始路径长度,L是最优路径长度,ε是计算精确度.给定的R算法稍作修改也能用来近似地解决3个NP完全或NP困难的三维欧几里德最短路径问题(ESP).它们的复杂性均为κ(ε)·O(k),这里k是含有所给定的障碍物的堆的层数.

关键词：R算法、最短路径、旅游多边形、部件切割、q矩形

所属期刊栏目：3

分类号：TP202+7(自动化技术及设备)

在线出版日期：2008-05-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：23-30