The time-synchronous dynamic programming approach to the shortest path search in spoken dialog system

Shortest path search has important practical applications and is related to optimization problems. This paper discusses a new algorithm time-synchronous heuristic dynamic programming search, which combined the pruning and global optimization of DP (Dynamic programming) and the partial search of heuristic strategy and found the shortest path in time O(n/k(d))(k,d≥1). Furthermore, the algorithm can be applied to find the K shortest paths between a pair of given nodes or all paths less than a given length within the same steps. Finally this algorithm was applied to the shortest path search on the real map and user could use spoken dialog to query shortcut in real time; 90% of the system responses are correct.