Solving Problems By Searching
Table of contents
 Node Expansion
 Getting in the shoes of a Search Agent
 Breadth First Search
 Depth First Search
 Step Costs
 Uniform Cost Search
 Depth Limited Search
 Iterative Deepening DepthFirst Search
 Bidirectional BFS
 A Star Search
Node Expansion
To search through a graph, a Search Agent needs to expand nodes. The nodes which can be expanded by the Agent together forms the frontier. Expanding a node refers to marking the node as 'expanded' or 'visited' and adding its immediate neighbors to the frontier.
In the following diagram, 'A' is the initial node and belongs to the frontier. Click on the frontier nodes to see how they are expanded.
 Expanded Nodes
 Frontier Nodes
 Unexplored/Unknown Nodes
Frontier Nodes
Getting in the shoes of a Search Agent
Let's see the prespective of a Search Agent as it searches through the graph.
Remember, the Agent can only see the nodes which are either expanded or currently present in the frontier.
Now that we know how nodes are expanded and how a search Agent perceives the graph, we are now ready to meet some Search Algorithms. In the above two visualizations, you decided which node to expand next(by clicking on them) but now we shall see some algorithms in action which can decide by themselves which node to expand next.
Breadth First Search
In Breadth First Search, the node which was discovered the earliest is expanded next i.e. the node which joined the frontier earlier, is expanded earlier.
To achieve this, Breadth First Search Algorithm uses a FIFO(First In First Out) Queue. The following graph is explored by a Breadth First Search Algorithm with 'A' as the initial node.
 Nodes waiting to be expanded

Node to be expanded next from the queue
FIFO Queue
Depth First Search
In Depth First Search, the node which was discovered the latest is expanded next i.e. the node which joined the frontier later, is expanded later.
To achieve this, Depth First Search Algorithm uses a LIFO(Last In First Out) Queue. The following graph is explored by a Depth First Search Algorithm with 'A' as the initial node.
 Nodes waiting to be expanded
 Node to be expanded next from the queue
LIFO Queue
Step Costs
Until now, all the edges in our graph had the same cost.(That's why we didn't bother to mention the cost on the graph). For those kind of graphs, Breadth First Search is optimal because it always pops the shallowest node first. For the case when some step costs are involved when exploring the nodes, the BFS algorithm needs be extended.
Associated cost of any node in the graph is calculated as the cost of the 'lowest cost path' from an initial node. Cost of the initial node is 0.
Below is a side by side comparison of both 'Lowest Cost Path' and the 'Breadth First Search Path' from the same initial node 'A'.
Note how BFS fails to derive the lowest cost path for many nodes. BFS successfully finds the paths with the minimum number of nodes from the initial node, but it doesn't take into account the costs of the steps.
Hover your mouse over any node to see the paths.
BFS Shortest Path
Breadth First Search
Lowest Cost Path
Uniform Cost Search (Extension of BFS)
Uniform Cost Search
For Unifrom Cost Search, instead of using a simple LIFO queue, A priority Queue is used where the cost of reaching that node from the initial node is considered as its priority. On each iteration, the node with the smallest cost is extracted from the frontier for expansion.
At any point of time in the process of a Uniform Cost Search, the costs of the explored nodes are always less than or equal to the costs of the frontier nodes (and also unexplored nodes as a matter of fact).
 Nodes waiting to be expanded
 Node to be expanded next from the queue
 Expanded Nodes
Priority Queue
costs >= 0
Explored Nodes
costs <= 0
Depth Limited Search
The Depth Limited Search is the same as Depth First Search except that there is an upper limit to the depth of the nodes which the algorithm traverses. The nodes which have depths greater than this limit is not expanded by the Depth Limited Search.
Given below is a Search Tree that is generated by a Depth first Search Algorithm on some graph. Try giving different limits to the Depth Limited Search Algorithm and notice that only the nodes with depths less than or equal to the given depth limit is searched.
Depth Limit :
 Expanded Nodes
 Frontier Nodes
 Unexplored/Unknown Nodes
Iterative Deepening DepthFirst Search
Iterative Deepening DepthFirst Search is a general strategy that is used to find the best depth limit. It does this by applying Depth Limited Search to the given problem with increasing depth limit. (0, 1, 2, 3 and so on.)
Given below is a search tree which is traversed using Iterative Deepening DepthFirst Search. The depthlimit is varied from 0 to 5 and Depth Limited Search is applied with that limit.
Depth Limit :
 Expanded Nodes
 Frontier Nodes
 Unexplored/Unknown Nodes
Bidirectional BFS
In bidirectional BFS, we run two simultaneous searches, one from the initial state and one from the goal state. We stop when these searches meet in the middle (ie, a node is explored by both the BFS)
The motivation behind this is that b^{d/2} + b^{d/2} is smaller than b^{d}
In the diagram below, we compare the performance between bidirectional BFS and standard BFS side by side. The total number of nodes generated for each strategy is given below the diagram.
Notice that the further apart the final node is from the initial node, the better bidirectional BFS performs (as compared to standard BFS). Use the restart button to restart the simulation.
Standard BFS
Bidirectional BFS
A Star Search

Frontier Nodes 
Node to be expanded next from the queue 
Expanded Nodes
Path
Priority Queue (Frontier)
Node  f(n)=g(n)+h(n)  g(n)  h(n)  Depth 
