TUTORIAL PLATFORM: June 2018

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:

Initial State that the problem starts in
Goal State that the problem ends in
Finding sequences of actions that lead to Goal State
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