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
CountryMalaysia
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