Title :
A fast algorithm for finding better routes by AI search techniques
Author :
Ikeda, Takahiro ; Hsu, Min-Yao ; Imai, Hiroshi ; Nishimura, Shigeki ; Shimoura, Hiroshi ; Hashimoto, Takeo ; Tenmoku, Kenji ; Mitoh, Kunihiko
Author_Institution :
Dept. of Inf. Sci., Tokyo Univ., Japan
fDate :
31 Aug-2 Sep 1994
Abstract :
The shortest path problem is one of the most fundamental problems applicable in various fields, and has close relation to route navigation systems. This paper surveys algorithms for the two-terminal shortest path problem and proposes bidirectional A* algorithm based on a new approach. This algorithm is suitable for finding not only the shortest route but also better routes. The efficiency and the property of these algorithms are discussed through experiments applying them to an actual road network
Keywords :
computational complexity; minimisation; navigation; search problems; AI search techniques; bidirectional A* algorithm; route navigation systems; two-terminal shortest path problem; Artificial intelligence; Industrial relations; Information science; Navigation; Roads; Shortest path problem; Telecommunication traffic;
Conference_Titel :
Vehicle Navigation and Information Systems Conference, 1994. Proceedings., 1994
Conference_Location :
Yokohama
Print_ISBN :
0-7803-2105-7
DOI :
10.1109/VNIS.1994.396824
