Depth-first, breadth-first and depth-first searching program
The following PROLOG code solves the water jugs and knight moves problems using depth-first, breadth-first and best-first 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 chess-board 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).
Considering the water jugs problem, it is apparent that the depth-first search is less efficient than the breadth-first or best-first 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 depth-first algorithm takes four moves:
while the other two search algorithms only take two moves:
This is because the depth-first 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 breadth-first search out-performs both the best-first and the depth-first searches is in going from [3,2] to [1,5]. The depth-first and best-first searches each take 10 moves while the breadth-first takes 5 moves. Apparently I did not chose a good heuristic algorithm for this case.
The breadth-first 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 best-first search off on the wrong path, and it takes a while for it to recover.
For the knight's path problem, the breadth-first search is the winner for the examples I tried, and the depth-first 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.