An Architecture for a Three-Tier Path-Finder
Дата
Авторы
Barley,Michael
Guesgen,Hans
Karl,Gareth
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
This paper describes the architecture of a route finding system that computes an optimal route between two given locations efficiently and that considers user preferences when doing so. The basis of the system is an A* algorithm that applies heuristics such as the air distance heuristic or the Manhattan heuristic to compute the shortest path between the two locations. Since A* is not tractable in general, island search is used to divide the problem into smaller problems, which can be solved more easily. In addition to that, search control rules are introduced to express user preferences about the routes to be considered during the search.
Ключевые слова
route finding , A* search , island search , search control rules