Comparative analysis of AI-based search algorithms in solving 8 puzzle problems
Abstract Background The 8-puzzle problem is a well-known combinatorial search problem, often used to test the effectiveness of various artificial intelligence (AI) algorithms. This study aims to evaluate the performance of three AI-based search algorithms—Breadth-First Search (BFS), Depth-First Sear...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2024-11-01
|
| Series: | Bulletin of the National Research Centre |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s42269-024-01274-3 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850163227271364608 |
|---|---|
| author | Ghaniyyat Bolanle Balogun Daniel Ibisagba Amos Bajeh Taofik Olawale Debo Abdulraheem Muyideen Olumuyiwa James Peter |
| author_facet | Ghaniyyat Bolanle Balogun Daniel Ibisagba Amos Bajeh Taofik Olawale Debo Abdulraheem Muyideen Olumuyiwa James Peter |
| author_sort | Ghaniyyat Bolanle Balogun |
| collection | DOAJ |
| description | Abstract Background The 8-puzzle problem is a well-known combinatorial search problem, often used to test the effectiveness of various artificial intelligence (AI) algorithms. This study aims to evaluate the performance of three AI-based search algorithms—Breadth-First Search (BFS), Depth-First Search (DFS), and A* Search—in solving the 8-puzzle problem. The algorithms were implemented in Java, and their performance was measured in terms of solution length, the number of expanded nodes, and execution time. Results Experiments were conducted on eight randomly generated instances of the 8-puzzle problem. The findings reveal that both BFS and A* Search consistently identify optimal solutions in all cases. However, BFS was found to use more memory and operate slower than A* Search. Conversely, DFS demonstrated faster execution times and lower memory usage compared to BFS but was less reliable in finding optimal or feasible solutions. The study also explored the impact of different heuristic functions on the performance of A* Search. Among the heuristics tested, the Manhattan distance heuristic was determined to be the most effective, offering the best balance between accuracy and efficiency. Conclusions In conclusion, both BFS and A* Search are effective in finding optimal solutions, with A* Search being more efficient in terms of speed and memory usage. DFS, while faster and more memory-efficient, is less consistent in producing optimal solutions. The Manhattan distance heuristic significantly enhances the performance of A* Search, making it the preferred heuristic for the 8-puzzle problem. These results suggest that A* Search, particularly with the Manhattan distance heuristic, is a highly efficient choice for solving the 8-puzzle problem, especially in contexts where computational resources are limited. |
| format | Article |
| id | doaj-art-eeadd45bdfba4c6489dd2a676d56d658 |
| institution | OA Journals |
| issn | 2522-8307 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Bulletin of the National Research Centre |
| spelling | doaj-art-eeadd45bdfba4c6489dd2a676d56d6582025-08-20T02:22:20ZengSpringerOpenBulletin of the National Research Centre2522-83072024-11-0148111510.1186/s42269-024-01274-3Comparative analysis of AI-based search algorithms in solving 8 puzzle problemsGhaniyyat Bolanle Balogun0Daniel Ibisagba1Amos Bajeh2Taofik Olawale Debo3Abdulraheem Muyideen4Olumuyiwa James Peter5Department of Computer Science, Faculty of Communication and Information Sciences, University of IlorinDepartment of Computer Science, Faculty of Communication and Information Sciences, University of IlorinDepartment of Computer Science, Faculty of Communication and Information Sciences, University of IlorinDepartment of Computer Science, Faculty of Communication and Information Sciences, University of IlorinDepartment of Computer Science, Faculty of Communication and Information Sciences, University of IlorinDepartment of Mathematical and Computer Sciences, University of Medical SciencesAbstract Background The 8-puzzle problem is a well-known combinatorial search problem, often used to test the effectiveness of various artificial intelligence (AI) algorithms. This study aims to evaluate the performance of three AI-based search algorithms—Breadth-First Search (BFS), Depth-First Search (DFS), and A* Search—in solving the 8-puzzle problem. The algorithms were implemented in Java, and their performance was measured in terms of solution length, the number of expanded nodes, and execution time. Results Experiments were conducted on eight randomly generated instances of the 8-puzzle problem. The findings reveal that both BFS and A* Search consistently identify optimal solutions in all cases. However, BFS was found to use more memory and operate slower than A* Search. Conversely, DFS demonstrated faster execution times and lower memory usage compared to BFS but was less reliable in finding optimal or feasible solutions. The study also explored the impact of different heuristic functions on the performance of A* Search. Among the heuristics tested, the Manhattan distance heuristic was determined to be the most effective, offering the best balance between accuracy and efficiency. Conclusions In conclusion, both BFS and A* Search are effective in finding optimal solutions, with A* Search being more efficient in terms of speed and memory usage. DFS, while faster and more memory-efficient, is less consistent in producing optimal solutions. The Manhattan distance heuristic significantly enhances the performance of A* Search, making it the preferred heuristic for the 8-puzzle problem. These results suggest that A* Search, particularly with the Manhattan distance heuristic, is a highly efficient choice for solving the 8-puzzle problem, especially in contexts where computational resources are limited.https://doi.org/10.1186/s42269-024-01274-3Artificial intelligenceBased search algorithmsHeuristics function |
| spellingShingle | Ghaniyyat Bolanle Balogun Daniel Ibisagba Amos Bajeh Taofik Olawale Debo Abdulraheem Muyideen Olumuyiwa James Peter Comparative analysis of AI-based search algorithms in solving 8 puzzle problems Bulletin of the National Research Centre Artificial intelligence Based search algorithms Heuristics function |
| title | Comparative analysis of AI-based search algorithms in solving 8 puzzle problems |
| title_full | Comparative analysis of AI-based search algorithms in solving 8 puzzle problems |
| title_fullStr | Comparative analysis of AI-based search algorithms in solving 8 puzzle problems |
| title_full_unstemmed | Comparative analysis of AI-based search algorithms in solving 8 puzzle problems |
| title_short | Comparative analysis of AI-based search algorithms in solving 8 puzzle problems |
| title_sort | comparative analysis of ai based search algorithms in solving 8 puzzle problems |
| topic | Artificial intelligence Based search algorithms Heuristics function |
| url | https://doi.org/10.1186/s42269-024-01274-3 |
| work_keys_str_mv | AT ghaniyyatbolanlebalogun comparativeanalysisofaibasedsearchalgorithmsinsolving8puzzleproblems AT danielibisagba comparativeanalysisofaibasedsearchalgorithmsinsolving8puzzleproblems AT amosbajeh comparativeanalysisofaibasedsearchalgorithmsinsolving8puzzleproblems AT taofikolawaledebo comparativeanalysisofaibasedsearchalgorithmsinsolving8puzzleproblems AT abdulraheemmuyideen comparativeanalysisofaibasedsearchalgorithmsinsolving8puzzleproblems AT olumuyiwajamespeter comparativeanalysisofaibasedsearchalgorithmsinsolving8puzzleproblems |