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

Finding Obstacle-Avoiding Shortest Path Using Generalized Connection Graphwith Θ(t) Edges

作　　者：周智[1] 蒋承东[1] 黄刘生[1] 顾钧 

机构地区：[1]中国科学技术大学计算机科学与技术系 [2]香港科学技术大学计算机科学系

出　　处：《软件学报》2003年第2期166-174,共9页Journal of Software

基　　金：国家重点基础研究发展规划(973)~~

摘　　要：在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题,连接图是研究此问题的基本工具.现有算法构造的最好的连接图GF是基于自由区的概念而设计的,其顶数和边数分别为O(t)和O(tlogt),其中t为障碍的极边数.提出了广义自由区和极大正规划分的概念,在此基础上得到广义连接图GG,用来表征广义自由区之间的邻接情况,其顶数和边数均为Q(t),且具有平面图的性质.同时还提出了基于扫描线的极大正规划分构造算法,其时间复杂度为O(tlogt);并提出规范路径的概念,以及采用不改向启发式策略的A*算法在广义连接图GG中寻找两点间的最短路径,算法的时间复杂度由基于GF的现有算法的O(tlogt)降低到Q(t).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 Q(t) vertices and Q(t) edges, and it is planar graph. An O(tlogt) time algorithm using plane scanning is designed to construct GG , and the 慸o 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 Q(t).

关 键 词：Θ(t) 广义连接图 最短路径 走迷宫算法 线搜索算法 超大规模集成电路 布线 

分 类 号：TN47[电子电信—微电子学与固体电子学] TP301.6[自动化与计算机技术—计算机系统结构]