Back to tutorials.

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.

Try right clicking on a goal node and select 'View Proof Deduction'. A proof tree is a tree created from the path from the start node to the goal node, proving the correctness of the goal found. The proof tree window only allows you to view the tree - you cannot do any further queries.

There are other ways to customize the search, however. Under the 'Deduction Options' menu, you can choose 'Search Options'. This will open up a window like the one below, allowing you to alter several aspects of the search. These options do not affect user-defined searches.

• The first option allows you to choose whether the auto search will stop when it has found a goal node, or to continue until it reaches the maximum number of steps or runs out of paths to explore.
• That maximum number of steps is defined by the second option. Once the maximum is reached, you will have to restart the auto search in order to continue.
• Another bound for the search is the depth bound for the tree. This is different from the option above it, as it also applies to occasions when you might be stepping through the search. The depth bound is intended to halt the search before it goes down an infinite path. Once the algorithm reaches a node at the depth bound, that node will not be expanded, and will be removed from the frontier.
• Finally, the last option defines the heuristic by which atoms are chosen from nodes. The default, which is also used by Prolog, is that the first atom in the list is chosen. You can also choose a random goal, the goal with the fewest variables, or the atom with the fewest associated clauses. Some delaying is implemented, in that built-in atoms that are not yet ground but need to be are not chosen until they become ground.

Back to tutorials.