Multiple-goal search algorithms and their application to web crawling
Dmitry Davidov, Shaul Markovitch · 2002
The work described in this paper presents a new frame-work for heuristic search where the task is to collect as many goals as possible within the allocated resources. We show the inadequacy of traditional distance heuris-tics for this type of tasks and present alternative types of heuristics that are more appropriate for multiple-goal search. In particular we introduce the yield heuristic that estimates the cost and the benefit of exploring a subtree below a search node. We present a learning al-gorithm for inferring the yield based on search experi-ence. We apply our adaptive and non-adaptive multiple-goal search algorithms to the web crawling problem and show their efficiency.