In this repository, we explore heuristic search algorithms, their capabilities and their importance in tackling complex computational problems.
Traditional search algorithms often ensure the discovery of optimal solutions. However, they might not always be practical for extensive problem spaces due to the potential for high computational time. Heuristic search algorithms come to our rescue by offering a trade-off: while they might not guarantee the best solution, they frequently provide sufficiently good solutions in much shorter times.
- Hill Climbing: A local search algorithm that starts with an initial solution and iteratively refines it. It might, however, get stuck in local maxima.
- Random Restart Hill Climbing: Enhances basic hill climbing by restarting from various random positions to avoid local optima.
- Simulated Annealing: Takes inspiration from the annealing process in metallurgy and sometimes allows worse solutions to escape local optima.
- Beam Search: A breadth-first search variation focusing on the best-performing candidates.
- Stochastic Beam Search: Introduces randomness in selecting the best candidates in beam search.
- Genetic Algorithms: Mimics the process of natural evolution, emphasizing the principle of natural selection.
- Modified Genetic Algorithm: An advanced version of the genetic algorithm with specific mutations for better navigation.
As a part of this notebook, we will employ the 8-Queens problem, a quintessential puzzle in computer science. This puzzle involves placing 8 queens on an 8x8 chessboard in such a way that no two queens threaten each other.
By the end of this notebook, we will conduct a comparative analysis of the algorithms, focusing on their running time and their prowess in solution discovery.
- Clone the Repository:
git clone [your-repository-link] - Navigate to the directory:
cd [repository-name] - Open the notebook with your preferred Jupyter interface and delve into the world of heuristic search algorithms!
Your feedback is invaluable! If you find any issues or have suggestions, please create an issue in this repository.
Happy Exploring!