论文部分内容阅读
针对有障碍时求两点间的最短路径这一问题，提出了极区和自由区的概念，并由此构造出一种新的强连接图ＣＦ，它由自由区的特征边和障碍的极边构成，其顶点数为Ｏ（ｔ），边数为Ｏ（ｔｌｏｇｔ），其中ｔ为障碍的极边数，而现有最佳连通图的顶点数和边数为Ｏ（ｔ＾２），同时提出了时间复杂度为Ｏ（ｔｌｏｇ＾２ｔ）的高效ＧＦ构造算法，并使用“不改向”的启发式Ａ算法在ＧＦ中寻找两点间的最短路径。