Java Program to Implement Iterative Deepening

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.

  1. import java.util.InputMismatchException;
  2. import java.util.Scanner;
  3. import java.util.Stack;
  4.  
  5. public class IterativeDeepening
  6. {
  7.     private Stack<Integer> stack;
  8.     private int numberOfNodes;
  9.     private int depth;
  10.     private int maxDepth;
  11.     private boolean goalFound = false;
  12.  
  13.     public IterativeDeepening()
  14.     {
  15.         stack = new Stack<Integer>();
  16.     }
  17.  
  18.     public void iterativeDeeping(int adjacencyMatrix[][], int destination)
  19.     {
  20.         numberOfNodes = adjacencyMatrix[1].length - 1;
  21.         while (!goalFound)
  22.         {
  23.             depthLimitedSearch(adjacencyMatrix, 1, destination);
  24.             maxDepth++;
  25.         }
  26.         System.out.println("\nGoal Found at depth " + depth);
  27.     }
  28.  
  29.     private void depthLimitedSearch(int adjacencyMatrix[][], int source, int goal)
  30.     {
  31.         int element, destination = 1;
  32.         int[] visited = new int[numberOfNodes + 1];
  33.         stack.push(source);
  34.         depth = 0;
  35.         System.out.println("\nAt Depth " + maxDepth);
  36.         System.out.print(source + "\t");
  37.  
  38.         while (!stack.isEmpty())
  39.         {
  40.             element = stack.peek();
  41.             while (destination <= numberOfNodes)
  42.             {
  43.                 if (depth < maxDepth)
  44.                 {
  45.                     if (adjacencyMatrix[element][destination] == 1)
  46.                     {
  47.                         stack.push(destination);
  48.                         visited[destination] = 1;
  49.                         System.out.print(destination + "\t");
  50.                         depth++;
  51.                         if (goal == destination)
  52.                         { 
  53.                             goalFound = true;
  54.                             return;
  55.                         }
  56.                         element = destination;
  57.                         destination = 1;
  58.                         continue;
  59.                     }
  60.                 } else 
  61.                 {
  62.                     break;
  63.                 }
  64.                 destination++;
  65.             }
  66.             destination = stack.pop() + 1;
  67.             depth--;
  68.         }
  69.     }
  70.  
  71.     public static void main(String... arg)
  72.     {
  73.         int number_of_nodes, destination;
  74.         Scanner scanner = null;
  75.         try
  76.         {
  77.             System.out.println("Enter the number of nodes in the graph");
  78.             scanner = new Scanner(System.in);
  79.             number_of_nodes = scanner.nextInt();
  80.  
  81.             int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];   			        
  82.             System.out.println("Enter the adjacency matrix");
  83.             for (int i = 1; i <= number_of_nodes; i++)
  84.                 for (int j = 1; j <= number_of_nodes; j++)
  85.                     adjacency_matrix[i][j] = scanner.nextInt();
  86.  
  87.             System.out.println("Enter the destination for the graph");
  88.             destination = scanner.nextInt();
  89.  
  90.             IterativeDeepening iterativeDeepening = new IterativeDeepening();
  91.             iterativeDeepening.iterativeDeeping(adjacency_matrix, destination);
  92.         }catch (InputMismatchException inputMismatch)
  93.         {
  94.             System.out.println("Wrong Input format");
  95.         }
  96.         scanner.close();
  97.     }
  98. }


$javac IterativeDeepening.java
$java IterativeDeepening
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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.