Breadth and depth first search - part 2

Breadth and depth first search - part 3

Search algorithms

The idea behind search algorithms is to simulate the exploration of a space of states or search space through the generation of successor states already explored.

Tree based search algorithms

Tree search algorithms are the heart of searching techniques. The basic principle is that a node is taken from a data structure, its successors examined and added to the data structure. By manipulating the data structure, the tree is explored in different orders for instance level by level (breadth-first search) or reaching a leaf node first and backtracking (depth-first search).

Definitions

- State - a representation of a physical configuration.
- Node - a data structure part of a search tree. A node has the following properties: father, sons, depth and path cost.

Types of problems

- Deterministic accessible - simple states problem.
- Deterministic inaccessible - multiple states problem.
- Non deterministic inaccessible - contingency problem (maybe) - sensors must be used during the execution process. The solution is a tree or a policy. Many times alternates between search and execution.
- Unknown search space - exploration problem (online).

The real world is extremely complex. The search space must be abstracted from the solution process.

Abstracting we have:

- Abstract state - the set of real states.
- Abstract operator - combination of real actions.
- Abstract solution - set of real paths that represents a solution in the real world.

A simple algorithm

function GeneralSearch(problem, strategy)

` return a solution or failure`

`Initialize the search tree using the initial state of the problem`

loop do

if there are no candidates for expansion then

` return failure`

`Choose a leaf node for expansion according to strategy`

if the node contains a goal state then

` return the corresponding solution`

`else`

expand the node and add the resulting nodes to the tree

end

Algorithm implementation

function GeneralSearch(problem, QueueingFunction)

nodes <- MakeQueue(MakeNode(InitialState[problem]))

loop do

if nodes is empty then

` return failure`

```
node <- RemoveFront(nodes) a leaf node for expansion according
to strategy
```

if GoalTest[problem] applied to State(node) succeeds then

` return node`

nodes <- QueueingFunction(nodes, Expand(node, Operators[problem]))

`end`

Search strategies

A search strategy is a choice made between the methods used to expand the nodes. Each method has its proper order of expansion. Strategies are evaluated according to following parameters:

- Time complexity - the number of generated or expanded nodes.
- Space complexity - maximum number of nodes presented in the memory.
- Optimality - the solution found has the minimum cost?

- b - maximum ramification factor of the search tree.
- d - depth of the solution that has the minimum cost.
- m - maximum depth of the search space (can be ∞) infinite.

The two strategies presented in this post (breadth and depth first search) are considered uninformed strategies because they only use the information available in the problem definition.

Breadth first search

The breadth first search expands the less deep node. The data structured used to implement this search algorithm is a queue.

Breadth first search properties

Is complete? Yes, if (b is finite).

Time: 1 + b^{2} + b^{3} + … + b^{d} = O(b^{d}). e.g.: exponential in d

Space: O(b^{d}) (maintains all the nodes in memory)

Optimal? Yes, if cost per step is 1; in general is not optimal.

Space is the big problem for can generate nodes at a rate of 1 MB / sec. 24 hours = 86 GB.

Depth first search

The depth first search expands the deepest node.

The data structure used to implement this search algorithm is a stack.

An important note about the depth first search is that it can execute infinite cycles so it’s mandatory to check the states already visited to avoid such infinite cycles.

Depth first search properties

Is complete? No. It is imperfect in spaces of infinite depth or in cyclic paths. Is complete only in a finite search space.

Time: O(bm). Is very bad if m is a lot greater than d. If solutions are dense can be fastest than the breadth first search.

Space: O(bm) e.g.: linear in space

Optimal? No.

Working problem: vacation in Romania

In this post let's explore a simple states problem as shown in the following picture:

Suppose we are taking a vacation in Romania. More specifically we are in the city called Arad. We want to go to Bucharest the capital city of Romania and our flight takes off tomorrow. Breaking down our problem, we have:

- Objective - go to Bucharest.
- Search space - several cities to get to Bucharest.
- Operator - drive through the cities.

A valid path could be: Arad, Sibiu, Fagaras, Bucharest. e.g.: Arad -> Zerind represents a complex set of possible paths, returns, pauses for resting, etc.

To guarantee the realizability, any real state in “Arad” must take us to some real state in “Zerind”.

The problem's formulation can be:

- Initial state - Arad
- Operator (or successor function S(x)) - eg.: Arad -> Zerind, Arad -> Sibiu, etc.
- Goal test - can be explicit or implicit as x = Bucharest or NoDirty(x).
- Path cost (additive) - can be the sum of distances, used operators, etc.

The solution is a sequence of operators that takes from the initial state to the goal state.

Implementing the breadth and depth first search in C#

The following methods use two classes implemented by Scott Mitchell [1]. The classes are: Node and EdgeToNeighbor.

I just added a new property called PathParent in the node class.

public static void BreadthFirstSearch(Node start, Node end)

{

Queue<Node> queue = new Queue<Node>();

queue.Enqueue(start);

` while(queue.Count != 0)`

{

` Node u = queue.Dequeue();`

` // Check if node is the end`

` if(u == end)`

{

Console.Write("Path found.");

` break;`

}

` else`

{

` u.Data = "Visited";`

` // Expands u's neighbors in the queue`

foreach(EdgeToNeighbor edge in u.Neighbors)

{

if(edge.Neighbor.Data == null)

{

` edge.Neighbor.Data = "Visited";`

` if(edge.Neighbor != end)`

{

edge.Neighbor.PathParent = u;

PrintPath(edge.Neighbor);

}

` else`

{

edge.Neighbor.PathParent = u;

PrintPath(edge.Neighbor);

` return;`

}

` Console.WriteLine();`

}

` /* shows the repeated nodes`

` else`

` {`

` Console.Write(edge.Neighbor.Key);`

` } */`

queue.Enqueue(edge.Neighbor);

}

}

}

}

public static void DepthFirstSearch(Node start, Node end)

{

Stack<Node> stack = new Stack<Node>();

stack.Push(start);

` while(stack.Count != 0)`

{

` Node u = stack.Pop();`

` // Check if node is the end`

` if(u == end)`

{

Console.WriteLine("Path found");

` break;`

}

` else`

{

` u.Data = "Visited";`

` // Store n's neighbors in the stack`

foreach(EdgeToNeighbor edge in u.Neighbors)

{

if(edge.Neighbor.Data == null)

{

` edge.Neighbor.Data = "Visited";`

` if(edge.Neighbor != end)`

{

edge.Neighbor.PathParent = u;

PrintPath(edge.Neighbor);

}

` else`

{

edge.Neighbor.PathParent = u;

PrintPath(edge.Neighbor);

` return;`

}

` Console.WriteLine();`

stack.Push(edge.Neighbor);

}

` /* shows the repeated nodes`

` else`

` {`

` Console.Write(edge.Neighbor.Key);`

` } */`

}

}

}

}

Summary

The formulation of a problem requires abstraction to avoid irrelevant details of the real world so that a search space can be defined and explored.

In a next post I'll dive in more details and explain how to use the breadth and depth search methods. We'll execute a test case using the Romania map shown in the picture above, print the traveled paths in the screen, calculate the shortest path possible between two cities using Dijkstra's algorithm and print such a path in the screen. Before that I recommend the reading of the excellent revision about data structures written by Scott Mitchell [1]. Although I only use the facts exposed in part 5 of Scott's article: From Trees to Graphs, it's worth to read starting in part 1. For now, look and think about the breadth and depth first search implementation in C#.

References

[1] Mitchell, Scott. An Extensive Examination of Data Structures. 2004. Available at <http://msdn2.microsoft.com/en-us/library/aa289152(VS.71).aspx>. Accessed on January 8, 2008.

[2] Artificial Intelligence Depot. Blind search. Available at <http://ai-depot.com/Tutorial/PathFinding-Blind.html>. Accessed on January 8, 2008.