| 本文已被：浏览 4362次 下载 6677次 |
码上扫一扫！ |
|
|
| 用Θ(t)的广义连接图求有障碍时的最短路径 |
|
周智1,2, 蒋承东1,2, 黄刘生1,2, 顾钧3
|
|
1.中国科学技术大学,计算机科学与技术系,安徽,合肥,230027;2.国家高性能计算中心(合肥),安徽,合肥,230027;3.香港科学技术大学,计算机科学系,香港
|
|
| 摘要: |
| 在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题,连接图是研究此问题的基本工具.现有算法构造的最好的连接图GF是基于自由区的概念而设计的,其顶数和边数分别为O(t)和O(tlogt),其中t为障碍的极边数.提出了广义自由区和极大正规划分的概念,在此基础上得到广义连接图GG,用来表征广义自由区之间的邻接情况,其顶数和边数均为Θ(t),且具有平面图的性质.同时还提出了基于扫描线的极大正规划分构造算法,其时间复杂度为O(tlogt);并提出规范路径的概念,以及采用"不改向"启发式策略的A*算法在广义连接图GG中寻找两点间的最短路径,算法的时间复杂度由基于GF的现有算法的O(tlogt)降低到Θ(t). |
| 关键词: VLSI设计 广义自由区 广义连接图 最短路径 NP-hard |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030401 (国家重点基础研究发展规划(973)) |
|
| Finding Obstacle-Avoiding Shortest Path Using Generalized Connection Graph with Θ(t) Edges |
|
ZHOU Zhi,JIANG Cheng-Dong,HUANG Liu-Sheng,GU Jun
|
| Abstract: |
| Finding obstacle-avoiding shortest path is an important problem in VLSI design, and connection graph is a fundamental tool to resolve the problem. The known best graph grounded on knowledge of free area, and it has O(t) vertices and O(tlogt) edges, in which t is the number of extreme edges of the obstacles. In this paper, a generalized connection graph GG is introduced, which is derived from some new conception such as generalized free area. GG is made up with vertex that represents the generalized free area and edges for their adjacency. It has only Θ(t) vertices and Θ(t) edges, and it is planar graph. An O(tlogt) time algorithm using plane scanning is designed to construct GG, and the do not change direction heuristic together with A* algorithm is used for getting the shortest obstacle-avoiding path using GG through the conception of formal path. This algorithm shorten the time complexity from O(tlogt)to Θ(t). |
| Key words: VLSI design generalized free area generalized connection graph shortest path NP-hard |
