| 用O(tlogt)的连接图求有障碍时的最短路径 |
| |
| 引用本文： | 周智,陈国良,顾钧. 用O(tlogt)的连接图求有障碍时的最短路径[J]. 计算机学报, 1999, 22(5): 519-524 |
| |
| 作者姓名： | 周智 陈国良 顾钧 |
| |
| 作者单位： | 1. 中国科学技术大学计算机科学技术系,合肥,230027
2. 香港科学技术大学计算机科学系,香港 |
| |
| 摘 要： | 针对有障碍时求两点间的最短路径这一问题，提出了极区和自由区的概念，并由此构造出一种新的强连接图ＣＦ，它由自由区的特征边和障碍的极边构成，其顶点数为Ｏ（ｔ），边数为Ｏ（ｔｌｏｇｔ），其中ｔ为障碍的极边数，而现有最佳连通图的顶点数和边数为Ｏ（ｔ＾２），同时提出了时间复杂度为Ｏ（ｔｌｏｇ＾２ｔ）的高效ＧＦ构造算法，并使用“不改向”的启发式Ａ算法在ＧＦ中寻找两点间的最短路径。
|
| 关 键 词： | VLSI设计 极区 自由区 强连接图 最短路径 |
| 修稿时间： | 1998-02-11 |
FINDING OBSTACLE-AVOIDING SHORTEST PATH USING CONNECTION GRAPH WITH O(tlogt) EDGES |
| |
| ZHOU Zhi,CHEN Guo-Liang,GU Jun. FINDING OBSTACLE-AVOIDING SHORTEST PATH USING CONNECTION GRAPH WITH O(tlogt) EDGES[J]. Chinese Journal of Computers, 1999, 22(5): 519-524 |
| |
| Authors: | ZHOU Zhi CHEN Guo-Liang GU Jun |
| |
| Abstract: | |
| |
| Keywords: | VLSI design extreme area free area connection graph shortest path. |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
