Θ(t)的广义连接图求有障碍时的最短路径
作者:
基金项目:

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
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [11]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    在有障碍时求两点间的最短路径是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).

    参考文献
    [1]Lee CY. An algorithm for path connections and its applications. IRE Transactions on Electronic Computers, 1961,EC-10:346~365.
    [2]Akers SB. A modification of Lee's path connection algorithm. IEEE Transactions on Electronic Computers, 1967,EC-16:97~98.
    [3]Soukup J. Fast maze router. In: Proceedings of the 15th Design Automation Conference. Las Vegas: ACM Press, 1978. 100~102.
    [4]Hightower DW. A solution to line routing problems on the continuous plan. In: Proceedings of the 6th Annul Design Automation Workshop. ACM Press,1969. 1~24.
    [5]Clarkson KL, Kapoor S, Vaidya PM. Rectilinear shortest path through polygonal obstacles in O(nlog2n) time. In: Proceedings of the 3rd Annual Symposium on Computational Geometry. New York: ACM Press, 1987. 251~257.
    [6]Zheng SQ, Lim JS, Iyengar SS. Finding obstacle-avoiding shortest paths using implicit connection graphs. IEEE Transactions on Computer Aided Design, 1996,15(1):103~110.
    [7]Wu YF, Widmayer P, Schlag MDF, Wong CK. Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles. IEEE Transactions on Computers, 1987,36(3):321~331.
    [8]Zhou Z. Obstacle-Avoiding minimum rectilinear steiner tree problem [MS. Thesis]. Hefei: University of Science and Technology of China, 1998 (in Chinese with English Abstract).
    [9]Zhou Z, Chen GL, Gu J. Finding obstacle-avoiding shortest path using connection graph with O(tlogt) edges. Chinese Journal of Computers, 1999,22(5):519~524 (in Chinese with English Abstract).
    [10]周智.有障碍的Manhattan空间中的最小Steiner树问题[硕士学位论文].合肥:中国科学技术大学,1998.
    [11]周智,陈国良,顾钧.用O(tlogt)的连接图求有障碍时的最短路径.计算机学报,1999,22(5):519~524.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

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

复制
分享
文章指标
  • 点击次数:3797
  • 下载次数: 5559
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2002-04-02
  • 最后修改日期:2002-06-10
文章二维码
您是第19868246位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号