论文部分内容阅读
针对有障碍时求两点间的最短路径这一问题，提出了极区和自由区的概念，并由此构造出一种新的强连接图ＧＦ，它由自由区的特征边和障碍的极边构成，其顶点数为Ｏ（ｔ），边数为Ｏ（ｔｌｏｇｔ），其中ｔ为障碍的极边数．而现有最佳连通图的顶点数和边数为Ｏ（ｔ２）．同时提出了时间复杂度为Ｏ（ｔｌｏｇ２ｔ）的高效ＧＦ构造算法，并使用“不改向”的启发式Ａ＊算法在ＧＦ中寻找两点间的最短路径．
Aiming at the problem of finding the shortest path between two points when there is an obstacle, this paper proposes the concept of polar region and free region, and constructs a new strong connection GF, which is composed of the characteristic edge of free region and the pole of obstacle , The number of vertices is O (t) and the number of edges is O (tlogt), where t is the number of poles of the barrier. The number of vertices and edges of the best connected graph is O (t2). At the same time, an efficient GF construction algorithm with time complexity O (tlog2t) is proposed and the shortest path between two points is searched for in GF using the heuristic A * algorithm of “no change”.