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

• 作者: KLETTE Reinhard 李发捷
• 来源期刊: 智能系统学报
• 学科: 工学
• 关键词: R算法 最短路径 旅游多边形 部件切割 q矩形
• 年，卷（期）: 2008,（1）
• 页码范围: 23-30
• 页数: 8页
• 分类号: TP202+7
• 字数: 6628字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-4785.2008.01.003

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李发捷	格罗宁根大学数学与计算科学学院	1	5	1.0	1.0