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 failureInitialize the search tree using the initial state of the problemloop do
if there are no candidates for expansion then
return failureChoose a leaf node for expansion according to strategyif the node contains a goal state then
return the corresponding solutionelseexpand 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 strategyif GoalTest[problem] applied to State(node) succeeds then
return nodenodes <- QueueingFunction(nodes, Expand(node, Operators[problem]))
endSearch 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 + b2 + b3 + … + bd = O(bd). e.g.: exponential in d
Space: O(bd) (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 queueforeach(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 stackforeach(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.
