Skip to content

README.md

Latest commit

 

History

History
55 lines (44 loc) · 2.1 KB

README.md

File metadata and controls

55 lines (44 loc) · 2.1 KB

N Queens Local Search

This repository implements the following local search methods.

Ed changes

I am modifying this code to make it suitable for innovative approaches to this problem.

  • Hill Climbing
  • Random Restart
  • Simulated Annealing
  • Local Beam Search
  • Stochastic Beam Search
  • Min-conflicts

For demonstration, these algorithms are tested on the classic N Queens problem. To run these algorithms for N Queens, use command

$ python TestLocalSearch.py

Unlike other local search algorithms, Min-conflicts Algorithm is defined in the Constraint Satisfaction Problem(CSP) context so it is implemented separately from others. It runs extremely fast for N Queens problem even for large boards. To run this algorithm, use command

$ python TestMinConflicts.py

Most of these local search algorithms have parameters that can be tuned to work with a specific problem, shown in the following table:

Algorithm Parameter
Hill Climbing None
Random Restart Number of restarts allowed
Simulated Annealing Cooling schedule
Local Beam Search Beam width
Stochastic Beam Search Beam width, value-probability mapping

Implementation of these algorithms can be adapted according to specific problems to get better performance. For example, FastNQueens.py implements an adapted version of simulated annealing which runs 4 times faster than the standard implementation.

Sample output

Running local search for N Queens Problem
 - Please input the size of the board (4~15): 8 

fast_simulated_annealing
 - Accuracy: 10/10	Running time: 0.455810
hill_climbing
 - Accuracy:  1/10	Running time: 0.104400
random_restart
 - Accuracy:  5/10	Running time: 1.047240
simulated_annealing
 - Accuracy: 10/10	Running time: 1.364582
local_beam_search
 - Accuracy: 10/10	Running time: 1.838199
stochastic_beam_search
 - Accuracy: 10/10	Running time: 5.537936