Empirical study prove that breadth-first search is more effective memory usage than depth-first search in frontier boundary cyclic graph

Al Refai Mohammed N., Jamhawi Zeyad

Abstract


Memory consumption, of opened and closed lists in graph searching algorithms, affect in finding the solution. Using frontier boundary will reduce the memory usage for a closed list, and improve graph size expansion. The blind algorithms, depth-first frontier Searches, and breadth-first frontier Searches were used to compare the memory usage in slide tile puzzles as an example of the cyclic graph. This paper aims to prove that breadth-first frontier search is better than depth-first frontier search in memory usage. Both opened and closed lists in the cyclic graph are used. The level number and nodes count at each level for slide tile puzzles are changed when starting from different empty tile location. Eventually, the unorganized spiral path in depth-first search appears clearly through moving inside the graph to find goals.


Keywords


Breadth-first search; Depth first search; Frontier boundary; Queue; Slide tiles puzzle; Stack

Full Text:

PDF


DOI: http://doi.org/10.11591/ijai.v10.i2.pp%25p

Refbacks

  • There are currently no refbacks.


View IJAI Stats

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.