Backtracking adaptive search is an optimisation algorithm which generalises pure adaptive search and hesitant adaptive search. This paper considers the number of iterations for which the algorithm runs, on a problem with finitely many range levels, in order to reach a sufficiently extreme objective function level. A difference equation for the expectation of this quantity is derived and solved. Several examples of backtracking adaptive search on finite problems are presented, including special cases that have received attention in earlier papers.
|Number of pages||9|
|Journal||Journal of Algorithms|
|Publication status||Published - Jul 2003|