摘要
针对有障碍时求两点间的最短路径这一问题，提出了极区和自由区的概念，并由此构造出一种新的强连接图ＧＦ，它由自由区的特征边和障碍的极边构成，其顶点数为Ｏ（ｔ），边数为Ｏ（ｔｌｏｇｔ），其中ｔ为障碍的极边数．而现有最佳连通图的顶点数和边数为Ｏ（ｔ２）．同时提出了时间复杂度为Ｏ（ｔｌｏｇ２ｔ）的高效ＧＦ构造算法，并使用“不改向”的启发式Ａ＊算法在ＧＦ中寻找两点间的最短路径．
Finding obstacle avoiding shortest path is an important problem in VLSI design. Connection graph is a fundamental tool to resolve the problem, the known best of which now have O(t 2) vertices and edges, where t is the number of extreme edges of the obstacles. This paper introduces some new conceptions such as extreme area and free area, from which a new connection graph G F is derived. G F is made up with characteristic edges of the free areas and extreme edges of the obstacles. It have only O(t) vertices and O(t log t) edges. This paper also derives a O(t log 2t) time algorithm used to construct G F and uses “don't change direction” heuristics together with A * algorithm to get the shortest obstacle avoiding path using G F .
出处
《计算机学报》
EI
CSCD
北大核心
1999年第5期519-524,共6页
Chinese Journal of Computers
基金
教育部博士点基金
关键词
VLSI
强连接图
最短路径
集成电路
VLSI design, extreme area, free area, connection graph, shortest path.
