%0 Journal Article
%T 用θ(t)的广义连接图求有障碍时的最短路径
%A 周智？
%A 蒋承东？
%A 黄刘生？
%A 顾钧？
%J 软件学报
%P 166-174
%D 2003
%X 在有障碍时求两点间的最短路径是vlsi设计、机器人设计等领域中的基本问题,连接图是研究此问题的基本工具.现有算法构造的最好的连接图gf是基于自由区的概念而设计的,其顶数和边数分别为o(t)和o(tlogt),其中t为障碍的极边数.提出了广义自由区和极大正规划分的概念,在此基础上得到广义连接图gg,用来表征广义自由区之间的邻接情况,其顶数和边数均为θ(t),且具有平面图的性质.同时还提出了基于扫描线的极大正规划分构造算法,其时间复杂度为o(tlogt);并提出规范路径的概念,以及采用"不改向"启发式策略的a*算法在广义连接图gg中寻找两点间的最短路径,算法的时间复杂度由基于gf的现有算法的o(tlogt)降低到θ(t).
%K vlsi设计
%K 广义自由区
%K 广义连接图
%K 最短路径
%K np-hard
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20030202&flag=1