Homework 3
Informed Search  

powered by FreeFind

Modified: 

Assignment

  1. Download Figure 4.17, the GENETIC-ALGORITHM for the 4-queens problem.

    Vary the probability of mutation and the number of generations for finding a suitably fit individual.

    1. The program is executed by run(number of generations), use 10 and 100 as some choices.
    2. Modify the PMUTATE variable to greater and lesser probabilities of mutation, use 0.0 as one choice.
  2. Modify the 4-queens problem to find a palindrome of length 6 constructed of digits 0 and 1. Run several times for different number of generations.

    Modify the palindrome problem to find a palindrome of length 6 constructed of digits 0..9. Run several times for different number of generations.

    Rates of convergence should be significantly different. Why?

  3. (Download A* for search for Bucharest) The text discusses the 8-puzzle. Use A* with the heuristic f(n) = g(n) + h(n) where g(n) is the search depth and h(n) is the number of tiles out of place from the goal to find the optimal solution path. The initial and goal states are:

    Initial            Goal

    283                123
    164                8  4
    7  5                765

    The goal should be found at depth 5 after 15 states are generated, including the initial state.

    Hint: The initial state is expanded to three other nodes by moving the blank as follows:

                                            Initial
                                            283      
                                            164         
                                            7  5     
         
    Left                                    Up                        Right
    283                                   283                       283
    164                                   1  4                       164
      75                                   765                       75

    The successor function should return all reachable states and could also return h(n) for each state returned.

Turn in

  1. Cover page - Your name, date, and Homework 3 should be on the first page. Staple all pages together.
  2. Printouts - Print the final Python programs for Assignment b and c and Shell executions showing solution path.