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
- 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
- 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?