A fewest-turn-and-shortest path algorithm based on breadth-first search |
| |
| Authors: | Yan Zhou Weisheng Wang Di He Zhe Wang |
| |
| Institution: | 1. School of Resources and Environment, University of Electronic Science and Technology of China, Chengdu, P.R. Chinazhouyan_gis@uestc.edu.cn;3. School of Resources and Environment, University of Electronic Science and Technology of China, Chengdu, P.R. China |
| |
| Abstract: | Many cognitive studies have indicated that the path simplicity may be as important as its distance travelled. However, the optimality of paths for current navigation system is often judged purely on the distance travelled or time cost, and not the path simplicity. To balance these factors, this paper presented an algorithm to compute a path that not only possesses fewest turns but also is as short as possible by utilizing the breadth-first-search strategy. The proposed algorithm started searching from a starting point, and expanded layer by layer through searching zero-level reachable points until the endpoint is found, and then deleted unnecessary points in the reverse direction. The forward searching and backward cleaning strategies were presented to build a hierarchical graph of zero-level reachable points, and form a fewest-turn-path graph (G*). After that, a classic Dijkstra shortest path algorithm was executed on the G* to obtain a fewest-turn-and-shortest path. Comparing with the shortest path in Baidu map, the algorithm in this work has less than half of the turns but the nearly same length. The proposed fewest-turn-and-shortest path algorithm is proved to be more suitable for human beings according to human cognition research. |
| |
| Keywords: | fewest-turn-and-shortest path breadth-first search hierarchical graph |
|
|
