CIS341 Lab Exercises March 2005

Search Exercise 1: Depth-first and Breadth-first

For this exercise you will be provided with some basic search programs which you will apply to specific problems. You can do the exercise in either Prolog or Java.

Prolog version

  1. Download the Prolog programs depth_first, breadth_first and maze and save them as .pl files.
    These files include examples of search programs from Bratko, ch 11.
  2. In order to run the programs you need to add two things: a definition of a successor relation s(Node, NextNode) which defines transitions between states in the state space, and a goal statement goal(...) which defines the goal state(s). An example of how to do this is provided in the maze file. Load the file maze.pl. This consists of a representation of a route-finding puzzle as follows:
  3. Load the two search programs in turn and run them by entering solve(i, Solution). Prolog will return the routes through the maze (in reverse) as values of Solution. Trace the programs to ensure you understand how the routes are calculated.
  4. Create a new file tube.pl using the same predicates as the maze file, representing a section of the London Underground network. Use the search programs to find routes between e.g., New Cross Gate and Oxford Circus.
  5. Go to Exercise 2 below.

Java versions

  1. Download the files Breadth.java, Breadth2.java, and Depth.java
  2. Each of these programs includes a representation of a maze as a two-dimensional array called map. If {node1, node2} occurs as a row in the array, this means that they are connected and node2 is a successor of node1.
  3. Compile and run the programs, and inspect the code to ensure you understand how they work.
  4. Modify the map array to represent a section of the London Underground. Test your program by setting e.g. the start node to New Cross Gate and the goal to Oxford Circus.
  5. The comments in Breadth2.java include various suggestions for improvement. Try and tackle some of them, especially if you intend to pick this topic for your project.
  6. Continue with Exercise 2.

Exercise 2