---

Announcements

Note although the text of this lab will appear on the Web soon.... the pictures may not appear till later.

---

Today's Topics

• Trees Revisited
• Depth First Search
• Breadth First Search
• Abstraction of Processes
• Generic Search

Prerequisites

Step 1. loaded (or evaluated) the init.lisp file that you downloaded in Lab 1.

Step 2. You should download the file ~gt7510f/2360/lab5.lisp at this time, also. After opening it in a Fred Buffer, you should evaluate this file.

---

Trees Revisited

In lab 4 we played a bit with trees with 2 children and then with trees with 4 children. In this lab we'll be using the "n-ary" Tree ADT. Meaning that a node can have as many or as few children as is needed. [NOTE: there was not restrictions on how many connections a node in a graph could have. Therefore our "special case" graph must also meet these conditions.]

The following is a example of a "n-ary" tree.

Figure 1

So our tree abstraction has the following specification. A tree is either empty or it consist of a tree node that

• Holds a indentifier
• The links to its children (if any)

The implementation looks like the following:.

                   The empty tree is represent by nil.

                   A tree node is of the following format

                             (  id  tree-node*  )

                   where there can be 0 or more tree-nodes ( that is what the '*' means)

                   tree-make

                   tree-empty

                   tree-id

                   tree-children

                   tree-dfs

                   tree-bfs

---

Depth First Search

The should look familiar to folks. The function tree-search from lab4 was doing depth first search. The depth first search code that appears here is just generalized to handle trees with n children.

The nodes in the following tree are labeled in the order that DFS would visit them.

Figure 2.

Additionally, the search function has been instrumented to optionally print out information along the course of the search. Ignore the code wrapped up inside the when and the :print argument if you just want to understand the searching aspects of the Lisp code.

There are three example trees, *tree1* ,*tree2* , and *tree3*, declared within the Lisp code. Try searching through them. For example:

                   (tree-dfs  'worf *tree1* )

                 or 

                   (tree-dfs  'worf *tree1* :print t )

Additionally, try to trace tree-dfs. Notice the size of the arguments passed to each recursive call. Do they successively get smaller or larger? We'll be comparing that to what appends with Breadth First search.

---

Breadth First Search

To do BFS we need to use a queue. Take the following tree

Figure 3

At node a the list of nodes to be examined later, if necessary, would be.

( b c d )

If a is not a solution then the first node on the queue should be examined. In this case, is b. So we'll pop b off the queue. So after b has been considered and rejected, the list should look like.

(c d e )

Where e is appended onto the end of the queue. This continues until the queue is empty or the item being search for is found. A Queue ADT is also contained within the file. It is based upon lists and largely consists of wrapping some new names around some familiar functions.

NOTE: the lexicographic order of the above nodes is the order in which BFS will visit them.

The BFS code included in lab5.lisp also contains extra "stuff" so that additional information may be printed out while the code is searching.

You should repeat the searches you made. For example:

                   (tree-bfs  'worf *tree1*  )

                 or 

                   (tree-bfs  'worf  *tree1*   :print t )

Also trace tree-bfs-hlp on some searches. Do the arguments get successively larger or smaller with each call? Compare this with DFS.

Compare the number of steps needed by each algorithm to complete it search task for a given target.

---

Abstraction of Processes

A first class datatype means that you can construct and use the datatype wherever you want. You can use it as an argument to a function. Or as the result of a function.

But what is a function? A Lisp integer represents a mathematical construct. You can say it describes that construct. A Lisp string represents a string. A function describes a process.

Notice that BFS and DFS mostly do the same thing. In fact, we could reconstruct DFS so that it too used a queue. However, instead of pushing successors onto the end of the queue it pushes successors onto the front of the queue. This will guarantee that the first successor's "children" are examined before the other successors, if any, are considered.

Think of how you would rewrite DFS to do this. For example, using the tree from the DFS section. The queue would go through the following stages.

                             ( 1 )      

                             ( 2 4 5 )  

                             ( 3 4 5 )

                             ( 4 5 )

                             ( 5 )

                             ( 6 7 )

                             ( 7 )

                             (   )

---

Generic Search

A generic description of a queue utilizing search process is:

                   If the queue is empty then return NIL ( search failed )

                   If when the element on the head of the queue is passed to goal-p

                             returns true then solution has been found.

                   Otherwise

                             Update the remainder of the queue with the head's 

                             successors and call recursively.

                   (generic-search  A (queue-make *tree1* )    B  C )     ; do DFS

                   (generic-search  D (queue-make *tree1* )    E F  )     ; do BFS