Solving Problems By Searching

Table of contents

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.

Restart
  • 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.

Restart

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.

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

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)

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

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 Depth-First Search

Iterative Deepening Depth-First 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 Depth-First Search. The depth-limit is varied from 0 to 5 and Depth Limited Search is applied with that limit.

Restart

Depth Limit :

  • Expanded Nodes
  • Frontier Nodes
  • Unexplored/Unknown Nodes

Bi-directional BFS

In bi-directional 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 bd/2 + bd/2 is smaller than bd

In the diagram below, we compare the performance between bi-directional 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 bi-directional BFS performs (as compared to standard BFS). Use the restart button to restart the simulation.

Restart

Standard BFS

Bi-directional 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

    Unexplored Nodes

      Explored Nodes