Stack and Backing Up

• How would you search this tree?
• It turns out there is a good exhaustive method in this case called depth first search.
• The idea is you go to the end (deep), if that fails, backup and try another path.
• You can implement this with a stack.
• A stack is also known as a Last In First Out (LIFO) Structure.
• It's like a stack of plates. You put plate A on, then plate B, then C. The first one you take out is C, then B, then A.
• Depth first search works the same way.
• You start at S, choose a path, and stack the other option.
• You repeat this from each position.
• When you get to the end (say 1 3), the stack has (2 2) on top of (4 3). You pop the stack and move to that place.
• This way you will eventually find an answer (if there is one) for any tree.
• Note that by converting it to a tree I remove the possibility of going back and forth from one spot to another.
• A stack is typically implemented with a series of items (the stack) and a pointer to the top of the stack.
• When you add something to the stack (push), you put a new item in the series and increment the pointer.
• When you take something from the stack (pop), you remove the last item from the series and decrement the pointer.
• How would you do this in Clips?