Search and Navigation—Non-Optimal Algorithms

Non-optimal search techniques: depth-first and breadth-first search

To understand these 2 algorithms, we need to look at 2 simple ways we can create a 'to-do list' in a computer program

It is often much easier to solve a big problem as a bunch of much smaller pieces, much like you would try to do by creating to-do lists.

So if your big problem is to clean the house, you may end up writing a bunch of sticky notes for yourself:

My sticky notes for Cleaning the House

Take out the garbage.

Wash the kitchen floor.

Dump scary green food in the refrigerator into the garbage.

Rake the leaves and put them in bags.

Vacuum the rugs.

If you stick one on top of another, you can rip them off as you complete them

Algorithm To Clean the House:

While there are sticky notes in the pile,

Take a sticky note from the top, read it, and do the job

At any time you remember a new job, write it on a sticky and put it on top of the pile

When the pile is empty, the algorithm ends (you're done)

Congratulations—you implemented a stack!

A stack is a data structure in which the last item put (or pushed) into the structure is the first item to be removed from it (LIFO--last in, first out)

In our sticky note example, we put "dump scary food..." on the stack last so it will be the first job we encounter when we remove, or pop jobs off the stack

On a stack data structure, you can only push or pop jobs from the same end (in our sticky note example, the top of the pile)

How come? Because this makes them easy and efficient to understand, create and use

Another, very similar data structure, is a queue

A queue is data structure in which the first item put into the structure is the first item to be removed from it (FIFO--first in, first out)

Unlike a stack, you push jobs onto the queue from one side, and pop them from the other

You may need to click on the following video to start it

There are many ways to create stacks and queues in any programming language but we won't worry about that here

Just think of them as ways to organize the tasks that a program needs to complete

Non-optimal algorithms for searching networks

Non-optimal paths get you from the start to the goal, but not necessarily by incurring the least-cost

They are sufficient to get from the start to goal but maybe not the best possible path

A non-optimal search may find a least-cost path accidentally, but usually it doesn't, especially in larger networks

Our first non-optimal algorithm: depth-first search

To perform depth-first search:

Put the starting node on the empty stack

While the stack is not empty,

Pop a node off the stack

If the node is the goal, stop

Otherwise, expand the node by placing its children on the stack, ordered left to right

Let's work through this with a simple example

Even though each step in the algorithm is simple, the result you get is almost magical

That's what makes search so interesting

Be sure to go through all the examples slowly, and look at them as many times as you need to, until they make sense

We can see from the network and the tree diagrams that there are 2 possible paths from the start to the goal:

0 → 1 → 2 → 3

or

0 → 2 → 3

Don't worry about which one is shorter or faster—depth-first only guarantees to find a path if one exists (not necessarily the least-cost (best) path)

Of all possible start to goal paths, the path that is chosen depends entirely on how the nodes and links in the tree are arranged

Depth-first search uses a stack data structure to organize its work

Important: When you follow the examples in this topic, trace through the tree, not the network

Remember—each branch of the tree is a separate path through the network

In the tree, individual nodes are shown more than once if they occur on more than one path

All the search algorithms here operate on the tree!

Try this out

To replicate this example, follow these steps in Network Search

Make sure Depth First is the selected Search Type in the drop down list

In the app, click to create the nodes as you see them in this example (make sure that the Create Node button is selected)

When you drag the links between your nodes, use the following order:

0 → 1

1 → 2

0 → 2

2 → 3

Other orders will work too (try them), but this one will create a tree identical to the example (to keep things easier for you to follow)

When you finish your network, try clicking the Show Traversal button—it will flash the nodes that the search inspected on its way toward finding a path to the goal

And now, using sticky notes, here we go!

Put the starting node on the empty stack

Ok, Node 0, the starting node, is now on the stack

While the stack is not empty

The stack has one item on it so we keep going

Pop a node off the stack

 

We look at the item that we popped off the stack

If the node is the goal, stop

Nope, it's not the goal node, so we move on to the next step...

Otherwise, expand the node by placing its children on the stack, ordered left to right

In the tree, we see that the children of node 0 are 1 and 2

I put the nodes on the stack so that node 2 goes on before node 1 (because our self-imposed rule is that we want to look at the left-most child first, and 1 is the left-most child of 0 in the tree)

And now we go back up to the While statement...

While the stack is not empty,

There are 2 node on the stack now

Pop a node off the stack

We look at the item that we popped off the stack

 

If the node is the goal, stop

Nope, node 1 is not the goal node

Otherwise, expand the node by placing its children on the stack, ordered left to right

Node 1 has only 1 child—node 2

We put node 2 on the stack

But wait! Isn't node 2 already on the stack?

Yes—It is (at the bottom right now), but as part of the path that goes directly from node 0 to node 2

Right now, we're expanding the path that goes from node 1 to node 2

Going back to the top of the while loop, the stack is not empty so we pop off node 2

 

Remember, this is part of the path that has gone from 0 to 1 to 2

If the node is the goal, stop

No, its not

Otherwise, expand the node by placing its children on the stack, ordered left to right

Node 2 only has 1 child—node 3

We push node 3 onto the stack

And back at the top of the while loop, we see that the stack is still not empty, so...

Pop a node off the stack

 

And it's the goal node, so we stop!

It's easy to reconstruct the path to the goal node by tracing upward (there's no branching going up—only down)

Who needs a fancy computer when you've got sticky notes?

Our second non-optimal algorithm: breadth-first search

The only difference from depth-first is that breadth-first uses a queue instead of a stack

This creates a left to right sweeping search pattern across a level of a tree before descending to the next level

To perform breadth-first search:

Put the starting node on the empty queue

While the queue is not empty,

Pop a node off the queue

If the node is the goal, stop

Otherwise, put the children of the node at the back of the queue, ordered left to right

To try this out, remember to set the Search Type to Breadth First

Here's how the search works on our search tree: