The boundary iterative-deepening depth-first search algorithm

Kai Li Lim, Kah Phooi Seng, LS Yeong, SI Ch'ng, Li-minn K Ang

    Research output: Book chapter/Published conference paperConference paperpeer-review

    Abstract

    Boundary searches were introduced in pathfinding aiming to find a middle-ground between memory intensive algorithms such as the A* search algorithm and the cycle redundancy of iterative-deepening algorithms such as the IDA*. Boundary search algorithms allocate a small memory footprint during runtime to store frontier nodes between each iteration to reduce redundancy, while expanding nodes in the same manner as iterative-deepening algorithms. The boundary search algorithm fringe search is an informed search algorithm derived from the IDA* for use in known environments. This paper proposes the boundary iterative-deepening depth-first search (BIDDFS) algorithm, which fills the gap made by the fringe search for uninformed search algorithms. The BIDDFS is optimised to perform blind searches in unknown environments, where simulation experiments found that it is up to more than 3 times faster than standard uninformed iterative-deepening algorithms.
    Original languageEnglish
    Title of host publicationProceedings of the 2nd International Conference on Advances in Computer and Information Technology - ACIT 2013
    Place of PublicationUnited States
    PublisherInstitute of Research Engineers and Doctors, LLC
    Pages119-124
    Number of pages6
    ISBN (Electronic)9789810762612
    DOIs
    Publication statusPublished - 04 May 2013
    EventSecond International Conference on Advances in Computer and Information Technology: ACIT 2013 - Shangri-La Hotel, Kuala Lumpur, Malaysia
    Duration: 04 May 201305 May 2013
    https://web.archive.org/web/20130504170854/http://www.theired.org/acit (Conference website)
    https://seekdl.org/conferences/details/International-Conference-on-Advances-in-Computer-and-Information-Technology-ACIT-2013 (Conference proceedings)

    Conference

    ConferenceSecond International Conference on Advances in Computer and Information Technology
    Country/TerritoryMalaysia
    CityKuala Lumpur
    Period04/05/1305/05/13
    OtherThe Second International Conference on Advances in Computer and Information Technology - ACIT 2013 is being organized by Institute of Research Engineers and Doctors (IRED). The aim of the conference is to provide the platform for Students, Engineers, Researchers and Scientists to share the knowledge and ideas in the recent trends in the field of Computer Science and Engineering.
    Internet address

    Fingerprint

    Dive into the research topics of 'The boundary iterative-deepening depth-first search algorithm'. Together they form a unique fingerprint.

    Cite this