
Depthfirst, breadthfirst and depthfirst searching program
The following PROLOG code solves the water jugs and knight moves problems using depthfirst, breadthfirst and bestfirst search algorithms. It searches the space defined by the 'move' rule. Thus, since the move rules may be redefined, this code represents a generic searching program. I used the code from the class supplement, with minor modifications, for the search algorithms. These are the first three files attached below. Following that is the code for the ADT's stack, set, queue and priority queue, again taken from the class supplement with minor modifications. For the heuristic predicate of the priority queue, I simply used the distance (squared) between the current state and the goal state. Following the ADT's are the move rules, first for the water jug problem followed by the knight moves problem.
Description of problems:
The water jug problem consists of a small and a large jug, of arbitrary size. Legal moves consist of emptying either jug, filling either jug, emptying either jug into the other until the other is full, or until the first one is empty. The jugs begin with an arbitrary integer quantity of fluid in each, with the goal being to reach a given final state using only the moves described above. The final state is to have each jug contain any arbitrary integer quantity of fluid, and may be the same or different from the initial state.
The knight moves problem consists of moving a knight on a chessboard of arbitrary size from an arbitrary starting position to an arbitrary final position, using only legal knight moves (i.e. one up and two over).
Analysis:
Considering the water jugs problem, it is apparent that the depthfirst search is less efficient than the breadthfirst or bestfirst search. For example, in moving from the initial state of [1,4] to [empty, empty] (where the first number indicates the amount of liquid in the small jug, the second number is for the large jug), the depthfirst algorithm takes four moves:
[1,4] >[5,4]>[5,6]>[0,6]>[0,0]
while the other two search algorithms only take two moves:
[1,4]>[0,4]>[0,0].
This is because the depthfirst search plunges ahead with searching the descendants of the first child before going on to the next child, whereas the other two searches look at all the children before going on to the grandchildren, and it turns out the solution in this case is only one layer deep.
An example in which the breadthfirst search outperforms both the bestfirst and the depthfirst searches is in going from [3,2] to [1,5]. The depthfirst and bestfirst searches each take 10 moves while the breadthfirst takes 5 moves. Apparently I did not chose a good heuristic algorithm for this case.
The breadthfirst search also wins out in going from [0,0] to [3,2]. It only takes three moves while the other two take 14! Here the heuristic algorithm almost catches the best initial move, which is to go to [0,5]. However, it instead goes to the state [3,0], which has the same heuristic value as [0,5] and is at the same depth as [0,5] but is stumbled upon before [0,5], which means it is given precedence over [0,5]. This sets the bestfirst search off on the wrong path, and it takes a while for it to recover.
For the knight's path problem, the breadthfirst search is the winner for the examples I tried, and the depthfirst search is the loser. A better heuristic algorithm would have been to take into account that it is better for a knight to be at a distance of 5 from the goal than at a distance less than 5 but greater than zero (5 = 2 X 2 + 1 X 1), since then only one move is required to reach the goal.
