Conference Proceedings

International Conference on Advances in Computer and Information Technology - ACIT 2013

The Boundary Iterative-Deepening Depth-First Search Algorithm

Author(s) : ANG LI-MINN, K.P. SENG, L.S. YEONG, LIM KAI L, S. I. CH’NG

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.

Conference Title : International Conference on Advances in Computer and Information Technology - ACIT 2013
Conference Date(s) : May 04-05, 2013
Place : Hotel Shangri-La, Kuala Lumpur, Malaysia
No fo Author(s) : 5
DOI : 10.15224/978-981-07-6261-2-26
Page(s) : 119 - 124
Electronic ISBN : 978-981-07-6261-2
Views : 764   |   Download(s) : 178