A Comparative Study of Informed and Uninformed Search Algorithm to Solve Eight-Puzzle Problem
- 1 Telkom University, Indonesia
Abstract
Problems in artificial intelligence can be solved using intelligent tracking methods through intelligent search mechanisms. Understandably, search algorithm performances are highly dependent on the problem solved. In this study, we evaluate and compare the performance of five uninformed and informed search (breadth-first search, depth first search, optimal search and best first search using two heuristic functions, namely mismatched tile and Manhattan distance) algorithms to solve the eight-puzzle game problem. For each algorithm, the numbers of raised and explored nodes were assessed and analyzed. Our experiment demonstrates that informed search with heuristic outperforms uninformed search significantly, both in terms of memory usage efficiency and computational power efficiency. On average, the informed search using heuristic requires only 5.33% of memory used by uninformed search and only 4.45% of computational power demanded by uninformed search. Boxplot analysis also confirms that informed search using heuristic also delivers more stable performance contrasted to uninformed search. These could be a concern for researchers and game developers to consider implementing the heuristically enhanced search algorithm to utilize memory and computational power efficiently to solve similar problems.
DOI: https://doi.org/10.3844/jcssp.2021.1147.1156
Copyright: © 2021 Wahyu Hidayat, Fitri Susanti and Dedy Rahman Wijaya. This is an open access article distributed under the terms of the
Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 3,130 Views
- 3,725 Downloads
- 3 Citations
Download
Keywords
- Comparative Study
- Uninformed Search
- Informed Search
- Heuristic
- 8-Puzzle Game