implement the Local Beam Search algorithm to solve the n-queens problem. The following will be the outline of your implementation: Your program should start with k random initial states. At each step, generate all successors of the current k states and select the best k successors to move forward with. The successors will be chosen based on heuristic values (number of attacking pairs). If any of these k states has zero attacking pairs, the algorithm should stop and print the solution. If local minima are reached, the algorithm will stop and print the board configuration. Your program will print the final board configuration, the number of attacking pairs in the board, and the total time required to reach the final state. Note, in the n-queens problem, corresponds to a column, and the value at each index represents the row position of the queen in that column. each queen can only move vertically within its own column. The state of the board is represented by a one-dimensional array where each index The initial random state will have one queen in each row. As such, to calculate the number of attacks/conflicts, you need to check the rows and diagonals. Execute your program with n = 8, 12, 16, and 20. For each of this n, use these values of k: 1, 3, 5, and 7. For each of these combinations of k and n, execute your program several times starting with a different initial random state Now, answer the following questions. You should use graphs and/or tables to explain and justify your answers. 1) 2) 3) 4) How does varying the value of k affect the ability of the program to find solutions (zero attacking pairs) for different values of n? Using the results of your experiment, explain what are the limitations and/or benefits of simple hill- climbing and local beam search? What trend do you observe in the runtime for different values of k for a fixed value of n? Comment on the trade-off between the ability of finding solutions vs speed as you increase the value of k. What trend do you observe in the runtime for different values of n for a fixed value of k? Do you think the local beam search algorithm will work for very large value of n? Justify your answer
implement the Local Beam Search
-
Your program should start with k random initial states.
-
At each step, generate all successors of the current k states and select the best k successors to move
forward with. The successors will be chosen based on heuristic values (number of attacking pairs).
-
If any of these k states has zero attacking pairs, the algorithm should stop and print the solution.
-
If local minima are reached, the algorithm will stop and print the board configuration.
Your program will print the final board configuration, the number of attacking pairs in the board, and the total time required to reach the final state. Note, in the n-queens problem,
corresponds to a column, and the value at each index represents the row position of the queen in that column.
each queen can only move vertically
within its own column. The state of the board is represented by a one-dimensional array where each index
The initial random state will have one queen in each row. As such, to calculate the number of attacks/conflicts,
you need to check the rows and diagonals.
Execute your program with n = 8, 12, 16, and 20. For each of this n, use these values of k: 1, 3, 5, and 7. For
each of these combinations of k and n, execute your program several times starting with a different initial
random state
Now, answer the following questions. You should use graphs and/or tables to explain and justify your answers.
1) 2) 3) 4)
How does varying the value of k affect the ability of the program to find solutions (zero attacking pairs)
for different values of n?
Using the results of your experiment, explain what are the limitations and/or benefits of simple hill-
climbing and local beam search?
What trend do you observe in the runtime for different values of k for a fixed value of n? Comment on
the trade-off between the ability of finding solutions vs speed as you increase the value of k.
What trend do you observe in the runtime for different values of n for a fixed value of k? Do you think
the local beam search algorithm will work for very large value of n? Justify your answer
Step by step
Solved in 2 steps with 2 images
