期刊
IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS
卷 47, 期 11, 页码 3037-3049出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TSMC.2016.2560418
关键词
A* search; admissibility; learning effect; shortest path
资金
- National Natural Science Foundation of China [61572127, 61272377]
- Specialized Research Fund for the Doctoral Program of Higher Education [20120092110027]
- Spanish Ministry of Economy and Competitiveness [DPI2012-36243-C02-01]
- FEDER
The shortest path problems (SPPs) with learning effects (SPLEs) have many potential and interesting applications. However, at the same time they are very complex and have not been studied much in the literature. In this paper, we show that learning effects make SPLEs completely different from SPPs. An adapted A* (AA*) is proposed for the SPLE problem under study. Though global optimality implies local optimality in SPPs, it is not the case for SPLEs. As all subpaths of potential shortest solution paths need to be stored during the search process, a search graph is adopted by AA* rather than a search tree used by A*. Admissibility of AA* is proven. Monotonicity and consistency of the heuristic functions of AA* are redefined and the corresponding properties are analyzed. Consistency/monotonicity relationships between the heuristic functions of AA* and those of A* are explored. Their impacts on efficiency of searching procedures are theoretically analyzed and experimentally evaluated.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据