In [1]: from py_search.problems.nqueens import nQueens
...: from py_search.problems.nqueens import nQueensProblem
...: from py_search.problems.nqueens import LocalnQueensProblem
...: from py_search.uninformed import depth_first_search
...: from py_search.uninformed import breadth_first_search
...: from py_search.informed import best_first_search
...: from py_search.informed import beam_search
...: from py_search.optimization import simulated_annealing
...: from py_search.optimization import hill_climbing
...: from py_search.optimization import branch_and_bound
...: from py_search.optimization import local_beam_search
...: from py_search.utils import compare_searches
...:
...: print("###################")
...: print("BACKTRACKING SEARCH")
...: print("###################")
...: initial = nQueens(5)
...: print("Empty %i-Queens Problem" % initial.n)
...: print(initial)
...: print()
...: compare_searches(problems=[nQueensProblem(initial)],
...: searches=[depth_first_search,
...: breadth_first_search,
...: best_first_search,
...: beam_search])
...: print()
...: print("##########################")
...: print("LOCAL SEARCH / OPTIMZATION")
...: print("##########################")
...: initial = nQueens(10)
...: initial.randomize()
...: cost = initial.num_conflicts()
...: print("Random %i-Queens Problem" % initial.n)
...: print(initial)
...: print()
...:
...: def beam2(problem):
...: return local_beam_search(problem, beam_width=2)
...:
...: def steepest_hill(problem):
...: return hill_climbing(problem)
...:
...: def annealing(problem):
...: size = problem.initial.state.n
...: n_neighbors = (size * (size-1)) // 2
...: return simulated_annealing(problem,
...: initial_temp=1.8,
...: temp_length=n_neighbors)
...:
...: def greedy_annealing(problem):
...: size = problem.initial.state.n
...: n_neighbors = (size * (size-1)) // 2
...: return simulated_annealing(problem,
...: initial_temp=0,
...: temp_length=n_neighbors)
...:
...: compare_searches(problems=[LocalnQueensProblem(initial,
...: initial_cost=cost)],
...: searches=[best_first_search,
...: branch_and_bound,
...: beam2,
...: steepest_hill,
...: annealing, greedy_annealing])
...: print()
...: initial = nQueens(20)
...: initial.randomize()
...: cost = initial.num_conflicts()
...: print("Random %i-Queens Problem" % initial.n)
...: print(initial)
...: print()
...: compare_searches(problems=[LocalnQueensProblem(initial,
...: initial_cost=cost)],
...: searches=[steepest_hill,
...: annealing, greedy_annealing])
...:
###################
BACKTRACKING SEARCH
###################
Empty 5-Queens Problem
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
()
Problem Search Alg Goal Tests Nodes Expanded Nodes Evaluated Solution Cost Runtime
-------------- -------------------- ------------ ---------------- ----------------- --------------- ---------
nQueensProblem depth_first_search 54 134 0 0 0.0034
nQueensProblem breadth_first_search 1437 5225 0 0 0.1064
nQueensProblem best_first_search 790 3658 1400 0 0.1466
nQueensProblem beam_search 6 55 56 Failed Failed
()
##########################
LOCAL SEARCH / OPTIMZATION
##########################
Random 10-Queens Problem
| | | | |Q| | | | | |
| | | |Q| | | | | | |
| | | | | | | | | |Q|
| | | | | |Q| | | | |
| |Q| | | | | | | | |
| | |Q| | | | | | | |
| | | | | | |Q| | | |
|Q| | | | | | | | | |
| | | | | | | |Q| | |
| | | | | | | | |Q| |
()
Problem Search Alg Goal Tests Nodes Expanded Nodes Evaluated Solution Cost Runtime
------------------- ----------------- ------------ ---------------- ----------------- --------------- ---------
LocalnQueensProblem best_first_search 3 90 90 0 0.0039
LocalnQueensProblem branch_and_bound 3 90 94 0 0.0031
LocalnQueensProblem beam2 3 90 0 0 0.0034
LocalnQueensProblem steepest_hill 14 58 59 0 0.0018
LocalnQueensProblem annealing 26 30 31 0 0.0011
LocalnQueensProblem greedy_annealing 7 13 14 0 0.0005
()
Random 20-Queens Problem
| | | | | | | | |Q| | | | | | | | | | | |
| | | | | | | | | | | | | | |Q| | | | | |
| | |Q| | | | | | | | | | | | | | | | | |
| | | |Q| | | | | | | | | | | | | | | | |
| | | | | | | | | | | | |Q| | | | | | | |
| | | | | | | | | | | |Q| | | | | | | | |
| | | | | | | | | | | | | | | | | |Q| | |
| | | | | | | |Q| | | | | | | | | | | | |
| | | | | | | | | | | | | | | |Q| | | | |
|Q| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |Q|
| | | | | |Q| | | | | | | | | | | | | | |
| | | | | | |Q| | | | | | | | | | | | | |
| |Q| | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | |Q| |
| | | | | | | | | | | | | | | | |Q| | | |
| | | | | | | | | | | | | |Q| | | | | | |
| | | | | | | | | | |Q| | | | | | | | | |
| | | | |Q| | | | | | | | | | | | | | | |
| | | | | | | | | |Q| | | | | | | | | | |
()
Problem Search Alg Goal Tests Nodes Expanded Nodes Evaluated Solution Cost Runtime
------------------- ---------------- ------------ ---------------- ----------------- --------------- ---------
LocalnQueensProblem steepest_hill 13 193 194 0 0.0152
LocalnQueensProblem annealing 104 143 144 0 0.0117
LocalnQueensProblem greedy_annealing 7 15 16 0 0.0013