###
DOI:
Journal of Software:2003.14(2):166-174

Θ(t)的广义连接图求有障碍时的最短路径
周智,蒋承东,黄刘生,顾钧
(中国科学技术大学,计算机科学与技术系,安徽,合肥,230027;国家高性能计算中心(合肥),安徽,合肥,230027;香港科学技术大学,计算机科学系,香港)
Finding Obstacle-Avoiding Shortest Path Using Generalized Connection Graph with Θ(t) Edges
ZHOU Zhi,JIANG Cheng-Dong,HUANG Liu-Sheng,GU Jun
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3037   Download 3344
Received:April 02, 2002    Revised:June 10, 2002
> 中文摘要: 在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题,连接图是研究此问题的基本工具.现有算法构造的最好的连接图GF是基于自由区的概念而设计的,其顶数和边数分别为O(t)和O(tlogt),其中t为障碍的极边数.提出了广义自由区和极大正规划分的概念,在此基础上得到广义连接图GG,用来表征广义自由区之间的邻接情况,其顶数和边数均为Θ(t),且具有平面图的性质.同时还提出了基于扫描线的极大正规划分构造算法,其时间复杂度为O(tlogt);并提出规范路径的概念,以及采用"不改向"启发式策略的A*算法在广义连接图GG中寻找两点间的最短路径,算法的时间复杂度由基于GF的现有算法的O(tlogt)降低到Θ(t).
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).
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030401 (国家重点基础研究发展规划(973)) Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030401 (国家重点基础研究发展规划(973))
Foundation items:
Reference text:

周智,蒋承东,黄刘生,顾钧.用Θ(t)的广义连接图求有障碍时的最短路径.软件学报,2003,14(2):166-174

ZHOU Zhi,JIANG Cheng-Dong,HUANG Liu-Sheng,GU Jun.Finding Obstacle-Avoiding Shortest Path Using Generalized Connection Graph with Θ(t) Edges.Journal of Software,2003,14(2):166-174