next up previous
Next: Knowledge Representation Up: AI Key Concepts - Previous: Further reading


  1. Implement the Search Algorithms described in this lecture in LISP and/or C. Comment on how suited each language would be for each type of search?
  2. How suited would PROLOG be in implementing the search algorithms. Comment on how this might be done and what difficulties might exist.
  3. Discuss the relative merits of depth first and breadth first searching methods. What memory overheads exist? How might searches be affected?

    Suggest some applications to which each is best suited.

  4. Steepest ascent hill climbing uses the basic Hill climbing algorithm but chooses the best successor rather than the first successor that is better. How will this improve matters?
  5. When will Hill climbing searches fail? Do Steepest ascent hill climbing always find solutions? How might some problems be overcome in the search?
  6. List 3 differences between simulated annealing and simple hill climbing methods.
  7. List examples where hill climbing and best first search behave (a) similarly (b) differently.
  8. Write an algorithm to perform a breadth first search for a graph making sure your algorithm works when a single node is generated at more than one level of the graph.
  9. When would best first search be worse than a simple breadth first search?
  10. Trace the constraint satisfaction procedure to solve the following cryptarithmetic problem:

  11. Discuss how constraint satisfaction might work it implemented its search strategy via: