Homework Assignment #2

1. (40 points) For this assignment I am giving you C code that implements
IDA* search on the 8-puzzle tile problem.  I would like you to enhance this
code to run not only IDA* search but also breadth-first search, depth-first
search, and beam search (where the beam width is defined by a constant in
the code).  If you prefer to implement the program in C++ or Python instead of
C you can port the code to one of these languages.  However, the program
needs to be able to be compiled and run on one of the department Linux
machines.

   The existing code does not require any input.  It generates a random
initial state, searches for a solution using IDA*, and prints the generated
solution.  It also prints the number of nodes that were generated during
the search process.

   In addition to turning in the source code for your program, I would like
you to include a document that describes how to compile and run the program.
In addition, the document should compare the search algorithms in terms of
solution length and search space size for several sample problems.  Because
some of the searches require significant amounts of memory and/or computation
time, you might need to impose a limit on the amount of storage and/or time
that is spent before the algorithm gives up.  If you do this, mention these
limits in your report as well.


2.  (5 points) Describe how you would implement a genetic algorithm to
solve the eight-puzzle problem you implemented for this homework assignment.
What would the chromosome look like, what operators would you apply, and
what challenges would you face?  Would you expect a genetic algorithm to be
faster or produce better results than the other search methods?  Why or why not?