Breadth First Search

Breadth First Search (BFS): is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. Fringe is a FIFO queue.

This Java program, to perform the bfs traversal of a given graph in the form of the adjacency matrix.the bfs traversal makes use of a queue.

Here is the source code of the Java program to perform the BFS traversal. The Java program is successfully compiled and run on a Linux system and Windows also.

package uninformed;

/**

 *

 * @author sam

 */

import java.util.InputMismatchException;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class BFS

{ 

    private Queue<Integer> queue;

    public BFS()

    {

        queue = new LinkedList<Integer>();

    }

    public void bfs(int adjacency_matrix[][], int source)

    {

        int number_of_nodes = adjacency_matrix[source].length - 1;

        

        

        

        int[] visited = new int[number_of_nodes + 1];

        int i, element, goalnode;

        Scanner scanner = new Scanner(System.in);

        System.out.print("ENTER THE GOAL NODE: ");

        goalnode = scanner.nextInt();

        visited[source] = 1;

        queue.add(source);

        while (!queue.isEmpty())

        {

            element = queue.remove();

            i = element;

            

            System.out.print(i + "\t");

            if(i == goalnode) return;

            while (i <= number_of_nodes)

            {

                if (adjacency_matrix[element][i] == 1 && visited[i] == 0)

                {

                    queue.add(i);

                    visited[i] = 1;

                }

                i++;

            }

        }

        System.out.println();

    }

    public static void main(String... arg)

    {

        int number_no_nodes, source;

        Scanner scanner = null;

        try

        {

            System.out.println("Enter the number of nodes in the graph");

            scanner = new Scanner(System.in);

            number_no_nodes = scanner.nextInt();

            int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];

            System.out.println("Enter the adjacency matrix");

            for (int i = 1; i <= number_no_nodes; i++)

                for (int j = 1; j <= number_no_nodes; j++)

                    adjacency_matrix[i][j] = scanner.nextInt();

            System.out.println("Enter the source for the graph");

            source = scanner.nextInt();

            System.out.println("The BFS traversal of the graph is ");

            BFS bfs = new BFS();

            bfs.bfs(adjacency_matrix, source);

        } catch (InputMismatchException inputMismatch)

        {

            System.out.println("Wrong Input Format");

        }

        scanner.close();

    }

}

Uninformed Search Algorithms and their Codes

This article helps the beginner of an AI course to learn the objective and implementation of Uninformed Search Strategies (Blind Search) which use only information available in the problem definition.

Uninformed Search includes the following algorithms:

• Breadth First Search (BFS)
• Uniform Cost Search (UCS)
• Depth First Search (DFS)
• Depth Limited Search (DLS)
• Iterative Deepening Search (IDS)
• Bidirectional Search (BS)

Background

This article covers several Search strategies that come under the heading of Uninformed Search. The term means that the strategies have no additional information about States beyond that provided in the problem definition. All they can do is generate successors and distinguish a goal state from a non-goal state. All Search strategies are distinguished by the order in which nodes are expanded.

To go ahead in these series, I will use some AI terminologies such as the following:

A problem can be defined by four components:

1. Initial State that the problem starts in
2. Goal State that the problem ends in
3. Finding sequences of actions that lead to Goal State
4. A path Cost to solve problem

Together, the initial state, goal state, actions and path cost define the state space of the problem (the set of all states reachable from the initial state by any sequence of actions). The path in the state space is a sequence of states connected by a sequence of actions. A solution to the problem is an action sequence that leads from the initial state to the goal state.

The process of looking at a sequence of actions that reaches the goal is called search. A search algorithm takes a problem as input and returns a solution in the form of an action sequences. The search starts from the initial state which represents the root node in the problem search space. The branches are actions and the nodes corresponding to the states in the problem state space.

A collection of nodes that are generated but not yet expanded is called the fringe; each element of fringe is a leaf node (i.e. with no successors in tree).

Let's start to explain the first two algorithms of blind search:

• Breadth First Search (BFS): is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. Fringe is a FIFO queue.
• Uniform Cost Search (UCS): modifies BFS by always expanding the lowest cost node on the fringe using path cost function g(n) (i.e. the cost of the path from the initial state to the node n). Nodes maintained on queue in order of increasing path cost.
• Depth First Search (DFS): always expands the deepest node in the current fringe of the search tree. Fringe is a LIFO queue (Stack).
• Depth Limited Search (DLS): The embarrassing failure of DFS in infinite state spaces can be alleviated by supplying DFS with a predetermined depth limit l, that is nodes at depth l are treated as if they have no successors.
• Iterative Deepening Depth First Search (IDS): is a general strategy often used in combination with depth first tree search that finds the best depth limit. It does this by gradually increasing limit first 0, then 1, then 2, and so on until the goal is found.
• Bidirectional Search (BS): The idea behind bidirectional search is to simultaneously search both forward from the initial state and backward from the goal state, and stop when the two searches meet in the middle. Here there are two fringes, one that maintains nodes forward and other that maintains nodes backward. Each fringe is implemented as LIFO or FIFO depends on the search strategy used in the search (i.e. Forward=BFS, Backward=DFS).

Given the graph below

The code for the breadth first search

package uninformed;

/**

 *

 * @author sam

 */

import java.util.InputMismatchException;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

 

public class BreadthFirstSearch

{ 

 

    private Queue<Integer> queue;

 

    public BreadthFirstSearch()

    {

        queue = new LinkedList<Integer>();

    }

 

    public void bfs(int adjacency_matrix[][], int source)

    {

        int number_of_nodes = adjacency_matrix[source].length - 1;

        

        

        

        int[] visited = new int[number_of_nodes + 1];

        int i, element, goalnode;

        Scanner scanner = new Scanner(System.in);

        System.out.print("ENTER THE GOAL NODE: ");

        goalnode = scanner.nextInt();

        visited[source] = 1;

        queue.add(source);

 

        while (!queue.isEmpty())

        {

            element = queue.remove();

            i = element;

            

            System.out.print(i + "\t");

            if(i == goalnode) return;

            while (i <= number_of_nodes)

            {

                if (adjacency_matrix[element][i] == 1 && visited[i] == 0)

                {

                    queue.add(i);

                    visited[i] = 1;

                }

                i++;

            }

        }

        System.out.println();

    }

 

    public static void main(String... arg)

    {

        int number_no_nodes, source;

        Scanner scanner = null;

 

        try

        {

            System.out.println("Enter the number of nodes in the graph");

            scanner = new Scanner(System.in);

            number_no_nodes = scanner.nextInt();

 

            int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];

            System.out.println("Enter the adjacency matrix");

            for (int i = 1; i <= number_no_nodes; i++)

                for (int j = 1; j <= number_no_nodes; j++)

                    adjacency_matrix[i][j] = scanner.nextInt();

 

            System.out.println("Enter the source for the graph");

            source = scanner.nextInt();

 

            System.out.println("The BFS traversal of the graph is ");

           BreadthFirstSearch bfs = new BreadthFirstSearch();

            bfs.bfs(adjacency_matrix, source);

 

        } catch (InputMismatchException inputMismatch)

        {

            System.out.println("Wrong Input Format");

        }

        scanner.close();

    }

}

Uniformed search strategies are very systematic, that all they can do expand nodes using the successor function and check whether state is a goal state or not.

Search strategies that we will talk about are:

1. Breadth-first search
2. Uniform-cost search
3. Depth-first search and Depth-limited search
4. Iterative deepening depth-first search
5. Bidirectional search

---

Breadth-first search (BFS)

• Description
  • A simple strategy in which the root is expanded first then all the root successors are expanded next, then their successors.
  • We visit the search tree level by level that all nodes are expanded at a given depth before any nodes at the next level are expanded.
  • Order in which nodes are expanded.

• 
  
• Performance Measure:
  • Completeness:
    • it is easy to see that breadth-first search is complete that it visit all levels given that d factor is finite, so in some d it will find a solution.
  • Optimality:
    • breadth-first search is not optimal until all actions have the same cost.
  • Space complexity and Time complexity:
    • Consider a state space where each node as a branching factor b, the root of the tree generates b nodes, each of which generates b nodes yielding b² each of these generates b³ and so on.
    • In the worst case, suppose that our solution is at depth d, and we expand all nodes but the last node at level d, then the total number of generated nodes is: b + b² + b³ + b⁴ + b^d+1 – b = O(b^d+1), which is the time complexity of BFS.
    • As all the nodes must retain in memory while we expand our search, then the space complexity is like the time complexity plus the root node = O(b^d+1).
• Conclusion:
  • We see that space complexity is the biggest problem for BFS than its exponential execution time.

Uniform-cost search (UCS)

• Description:
  • Uniform-cost is guided by path cost rather than path length like in BFS, the algorithms starts by expanding the root, then expanding the node with the lowest cost from the root, the search continues in this manner for all nodes.
  • Hints about UCS implementation can be found here.
  • You should not be surprised that Dijkstra’s algorithm, which is perhaps better-known, can be regarded as a variant of uniform-cost search, where there is no goal state and processing continues until the shortest path to all nodes has been determined.
• Performance Measure:
  • Completeness:
    • It is obvious that UCS is complete if the cost of each step exceeds some small positive integer, this to prevent infinite loops.
  •  Optimality:
    • UCS is always optimal in the sense that the node that it always expands is the node with the least path cost.
  • Time Complexity:
    • UCS is guided by path cost rather than path length so it is hard to determine its complexity in terms of b and d, so if we consider C to be the cost of the optimal solution, and every action costs at least e, then the algorithm worst case is O(b^C/e).
  • Space Complexity:
    • The space complexity is O(b^C/e) as the time complexity of UCS.
• Conclusion:
  • UCS can be used instead of BFS in case that path cost is not equal and is guaranteed to be greater than a small positive value e.

---

Depth-first search (DFS)

• Description:
  • DFS progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it hasn’t finished exploring.
  • Order in which nodes are expanded

• Performance Measure:
  • Completeness: 
    • DFS is not complete, to convince yourself consider that our search start expanding the left sub tree of the root for so long path (may be infinite) when different choice near the root could lead to a solution, now suppose that the left sub tree of the root has no solution, and it is unbounded, then the search will continue going deep infinitely, in this case we say that DFS is not complete.
  • Optimality:
    • Consider the scenario that there is more than one goal node, and our search decided to first expand the left sub tree of the root where there is a solution at a very deep level of this left sub tree, in the same time the right sub tree of the root has a solution near the root, here comes the non-optimality of DFS that it is not guaranteed that the first goal to find is the optimal one, so we conclude that DFS is not optimal.
  • Time Complexity:
    • Consider a state space that is identical to that of BFS, with branching factor b, and we start the search from the root.
    • In the worst case that goal will be in the shallowest level in the search tree resulting in generating all tree nodes which are O(b^m).
  • Space Complexity:
    • Unlike BFS, our DFS has a very modest memory requirements, it needs to story only the path from the root to the leaf node, beside the siblings of each node on the path, remember that BFS needs to store all the explored nodes in memory.
    • DFS removes a node from memory once all of its descendants have been expanded.
    • With branching factor b and maximum depth m, DFS requires storage of only bm + 1 nodes which are O(bm) compared to the O(b^d+1) of the BFS.
• Conclusion:
  • DFS may suffer from non-termination when the length of a path in the search tree is infinite, so we perform DFS to a limited depth which is called Depth-limited Search.

---

Depth-limited search (DLS)

• Description:
  • The unbounded tree problem appeared in DFS can be fixed by imposing a limit on the depth that DFS can reach, this limit we will call depth limit l, this solves the infinite path problem.
• Performance Measure:
  • Completeness:
    • The limited path introduces another problem which is the case when we choose l < d, in which is our DLS will never reach a goal, in this case we can say that DLS is not complete.
  • Optimality:
    • One can view DFS as a special case of the depth DLS, that DFS is DLS with l = infinity.
    • DLS is not optimal even if l > d.
  • Time Complexity: O(b^l)
  • Space Complexity: O(b^l)
• Conclusion:
  • DLS can be used when the there is a prior knowledge to the problem, which is always not the case, Typically, we will not know the depth of the shallowest goal of a problem unless we solved this problem before.

---

Iterative deepening depth-first search (IDS)

• Description:
  • It is a search strategy resulting when you combine BFS and DFS, thus combining the advantages of each strategy, taking the completeness and optimality of BFS and the modest memory requirements of DFS.
  • IDS works by looking for the best search depth d, thus starting with depth limit 0 and make a BFS and if the search failed it increase the depth limit by 1 and try a BFS again with depth 1 and so on – first d = 0, then 1 then 2 and so on – until a depth d is reached where a goal is found.
• Performance Measure:
  • Completeness:
    • IDS is like BFS, is complete when the branching factor b is finite.
  • Optimality:
    • IDS is also like BFS optimal when the steps are of the same cost.
  • Time Complexity:
    • One may find that it is wasteful to generate nodes multiple times, but actually it is not that costly compared to BFS, that is because most of the generated nodes are always in the deepest level reached, consider that we are searching a binary tree and our depth limit reached 4, the nodes generated in last level = 2⁴ = 16, the nodes generated in all nodes before last level = 2⁰ + 2¹ + 2² + 2³= 15
    • Imagine this scenario, we are performing IDS and the depth limit reached depth d, now if you remember the way IDS expands nodes, you can see that nodes at depth d are generated once, nodes at depth d-1 are generated 2 times, nodes at depth d-2 are generated 3 times and so on, until you reach depth 1 which is generated d times, we can view the total number of generated nodes in the worst case as:
      • N(IDS) = (b)d + (d – 1)b² + (d – 2)b³ + …. + (2)b^d-1 + (1)b^d = O(b^d)
    • If this search were to be done with BFS, the total number of generated nodes in the worst case will be like:
      • N(BFS) = b + b² + b³ + b⁴ + …. b^d + (b^{d + 1} – b) = O(b^{d + 1})
    • If we consider a realistic numbers, and use b = 10 and d = 5, then number of generated nodes in BFS and IDS will be like
      • N(IDS) = 50 + 400 + 3000 + 20000 + 100000 = 123450
      • N(BFS) = 10 + 100 + 1000 + 10000 + 100000 + 999990 = 1111100
      • BFS generates like 9 time nodes to those generated with IDS.
  • Space Complexity:
    • IDS is like DFS in its space complexity, taking O(bd) of memory.
• Conclusion:
  • We can conclude that IDS is a hybrid search strategy between BFS and DFS inheriting their advantages.
  • IDS is faster than BFS and DFS.
  • It is said that “IDS is the preferred uniformed search method when there is a large search space and the depth of the solution is not known”.

---

Bidirectional search

• Description:
  • As the name suggests, bidirectional search suggests to run 2 simultaneous searches, one from the initial state and the other from the goal state, those 2 searches stop when they meet each other at some point in the middle of the graph.
  • The following pictures illustrates a bidirectional search:

• Performance Measure:
  • Completeness:
    • Bidirectional search is complete when we use BFS in both searches, the search that starts from the initial state and the other from the goal state.
  • Optimality:
    • Like the completeness, bidirectional search is optimal when BFS is used and paths are of a uniform cost – all steps of the same cost.
    • Other search strategies can be used like DFS, but this will sacrifice the optimality and completeness, any other combination than BFS may lead to a sacrifice in optimality or completeness or may be both of them.
  • Time and Space Complexity:
    • May be the most attractive thing in bidirectional search is its performance, because both searches will run the same amount of time meeting in the middle of the graph, thus each search expands O(b^d/2) node, in total both searches expand O(b^d/2 + b^d/2) node which is too far better than the O(b^{d + 1}) of BFS.
    • If a problem with b = 10, has a solution at depth d = 6, and each direction runs with BFS, then at the worst case they meet at depth d = 3, yielding 22200 nodes compared with 11111100 for a standard BFS.
    • We can say that the time and space complexity of bidirectional search is O(b^d/2).
• Conclusion:
  • Bidirectional search seems attractive for its O(b^d/2) performance, but things are not that easy, especially the implementation part.
  • It is not that easy to formulate a problem such that each state can be reversed, that is going from the head to the tail is like going from the tail to the head.
  • It should be efficient to compute the predecessor of any state so that we can run the search from the goal.

---