用（）(t)的广义连接图求有障碍时的最短路径

• 作者: 周智 蒋承东 顾钧 黄刘生
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: VLSI设计 广义自由区 广义连接图 最短路径 NP-hard
• 年，卷（期）: 2003,（2）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 166-174
• 页数: 9页
• 分类号: TP301
• 字数: 7359字
• 语种: 中文

摘要

在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题,连接图是研究此问题的基本工具.现有算法构造的最好的连接图GF是基于自由区的概念而设计的,其顶数和边数分别为O(t)和O(tlogt),其中t为障碍的极边数.提出了广义自由区和极大正规划分的概念,在此基础上得到广义连接图GG,用来表征广义自由区之间的邻接情况,其顶数和边数均为()(t),且具有平面图的性质.同时还提出了基于扫描线的极大正规划分构造算法,其时间复杂度为O(tlogt);并提出规范路径的概念,以及采用"不改向"启发式策略的A*算法在广义连接图GG中寻找两点间的最短路径,算法的时间复杂度由基于GF的现有算法的O(tlogt)降低到()(t).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	顾钧	香港科学技术大学计算机科学系	5	43	4.0	5.0