This Java program,Implements Iterative Deepening.Iterative deepening depth-first search(IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches , the depth of the shallowest goal state. IDDFS is equivalent to breadth-first search, but uses much less memory; on each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.
Here is the source code of the Java program implements iterative deepening. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
package Search_Algorithm;
/**
*
* @author sam
*/
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
public class DepthLimitedSearch
{
private Stack<Integer> stack;
private int numberOfNodes;
private static final int MAX_DEPTH = 3;
public DepthLimitedSearch(int numberOfNodes)
{
this.numberOfNodes = numberOfNodes;
this.stack = new Stack<Integer>();
}
public void depthLimitedSearch(int adjacencyMatrix[][], int startNode)
{
int visited[] = new int[numberOfNodes + 1];
int element, destination;
int depth = 0;
System.out.println(startNode + " at depth " + depth);
stack.push(startNode);
visited[startNode] = 1;
depth = 0;
while (!stack.isEmpty())
{
element = stack.peek();
destination = element;
while (destination <= numberOfNodes)
{
if (depth < MAX_DEPTH)
{
if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 0)
{
stack.push(destination);
visited[destination] = 1;
depth++;
System.out.println(destination + " at depth " + depth);
element = destination;
destination = 1;
}
}
else
{
return;
}
destination++;
}
stack.pop();
depth--;
}
}
public static void main(String... arg)
{
int number_of_nodes, startNode;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_of_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= number_of_nodes; i++)
for (int j = 1; j <= number_of_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();
System.out.println("Enter the startNode for the graph");
startNode = scanner.nextInt();
System.out.println("The Depth limited Search Traversal of Max Depth 3 is");
DepthLimitedSearch depthLimitedSearch = new DepthLimitedSearch(number_of_nodes);
depthLimitedSearch.depthLimitedSearch(adjacency_matrix, startNode);
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}
THE OUTPUT:
Enter the number of nodes in the graph 7 Enter the adjacency matrix 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Enter the destination for the graph 7
At Depth 0 1 At Depth 1 1 2 3 At Depth 2 1 2 4 5 3 6 7 Goal Found at depth 2
No comments:
Post a Comment