Tutorials
Definite Clause Deduction

## Tutorial Three: Search Trees

To avoid having to select each individual atom and clause to apply, there are methods to automatically search for a solution. Part of the purpose of this applet is to demonstrate the analogy between definite clause deduction and searching the branches of a tree.

To this end, the applet implements four basic search algorithms: Best First, Breadth First, Depth First, and Heuristic Depth First Search. A few basic concepts are involved in the explanation of the manner in which these algorithms operate.

First of all, the heuristic function h(n) is a function from the node n to a non-negative real number. It is an estimate of the path length from that node to a goal node. In this applet, the heuristic function is determined by the number of atoms in a node, since it is assumed that nodes with fewer atoms will be solved more quickly. The heuristic function, then, is always an underestimate, since the minimum path length to a goal node is at least the number of atoms. Each search algorithm maintains a frontier of nodes to search. The search strategy defines which node in the frontier will be the next to be expanded. When a node is expanded, if it is a goal node, the search is complete, since a path has been found. If not, its neighbours are added to the frontier.

• Best First Search: always chooses the element of the frontier with the lowest value of h(n), since it tries to choose the element that appears to be closest to the goal. It treats the frontier like a priority queue, ordered by the heuristic function.

• Breadth First Search: chooses the elements of the frontier in the order in which they were added. It is an example of a first in, first out system.

• Depth First Search: tries to search paths to their completion before trying new ones. When a path fails, the algorithm backtracks to the last point at which it could have chosen a different path, and then tries that one. In other words, when a node is expanded, the next node to be chosen is the first child of the previous node.

• Heuristic Depth First Search: as the name suggests, a version of depth first search that uses heuristic knowledge to guide the search. It makes the local best choice, searching the most promising child of the previous node, instead of the first child. Which child is most promising is determined by the value of h(n).

Try the different algorithms on the applet now, with the problem provided and the same list operations knowledge base as in the previous tutorial. You can choose different algorithms by clicking on them to the right of the applet. You cannot use two different algorithms while searching. Reset the search and choose a different one instead.

In the full version, the menu allowing you to switch between algorithms can be accessed from the 'Deduction Options' menu.

'Auto Search' will perform the entire search for you, while 'Step' and 'Fine Step' will show you the operations of the algorithm in more detail. 'Fine Step' chooses the node first, and then expands it, while 'Step' performs both at once. You can reset the search and try different algorithms on the same problem. Notice the order in which different algorithms find the goal nodes.