Expected search duration for finite backtracking adaptive search

D. L J Alexander*, D. W. Bulger, G. R. Wood

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    2 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    Pages (from-to)78-86
    Number of pages9
    JournalJournal of Algorithms
    Volume47
    Issue number2
    Publication statusPublished - Jul 2003

    Fingerprint Dive into the research topics of 'Expected search duration for finite backtracking adaptive search'. Together they form a unique fingerprint.

    Cite this