logo

Efficient and Debugged Java Program for IDSearch

Description of IDDFS algorithm in finding the shortest path in a grid given the source and destination.

4 Pages1456 Words442 Views
   

Added on  2022-12-01

About This Document

This is an efficient and debugged version of a Java program that implements the IDSearch algorithm. It takes into account the specific positions of the source and destination in the given matrix. The program uses iterative deepening to search for the goal at different depths.

Efficient and Debugged Java Program for IDSearch

Description of IDDFS algorithm in finding the shortest path in a grid given the source and destination.

   Added on 2022-12-01

ShareRelated Documents
The following is an efficient and debugged version of the java program that takes
into account the specific positions of the source and destination given in some
cases the goal appears first before the source.
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Stack;
public class IDSearch {
private Stack<Integer> stack;
private int numberOfNodes;
//private static SearchNode node;
private static SearchNode srcnode;
private static SearchNode destNode;
private int depth;
private int maxDepth;
private static int xsrc;
private static int ysrc;
private static int xdest;
private static int ydest;
private boolean goalFound = false;
private IDSearch()
{
stack = new Stack<Integer>();
}
static class SearchNode
{
int x,y, depth;
SearchNode(int x, int y)
{
this.x = x;
this.y = y;
//this.depth = depth;
}
//This method requires a new Node then establishes if the Node is a neighbour
//to the current Node or not.
private boolean neighbour(SearchNode curr)
{
if(curr.x == this.x + 1 || curr.x == this.y - 1)
{
return true;
}
return false;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof SearchNode)) return false;
SearchNode that = (SearchNode) o;
return x == that.x &&
y == that.y;
}
@Override
public String toString() {
return "SearchNode{" +
"x=" + x +
", y=" + y +
'}' + "depth" + this.depth;
}
Efficient and Debugged Java Program for IDSearch_1
}
public void iterativeDeepening( int matrixGrid[][], int source, int destination)
{
//numberOfNodes = matrixGrid[1].length - 1;
while (!goalFound && maxDepth < numberOfNodes)
{
depthLimitedSearch(matrixGrid, matrixGrid[xsrc][ysrc], destination);
maxDepth++;
}
System.out.println("\n Goal found at depth " + depth);
}
private void depthLimitedSearch(int matrixGrid[][], int source, int goal)
{
int element, destination = 1;
int[] visited = new int[numberOfNodes + 1];
stack.push(source);
depth = 0;
System.out.println("\nAt Depth " + maxDepth + "\t" );
System.out.println( "Frontier (" + (maxDepth - 1) + "," + maxDepth + ")");
System.out.print( source + "\t");
if( maxDepth == depth && goalFound )
{
return;
}
else
{
Outer:
while (!stack.isEmpty())
{
element = stack.peek();
while(destination < numberOfNodes && matrixGrid[element][destination]
!= 3)
{
if(depth < maxDepth && maxDepth < numberOfNodes)
{
if(matrixGrid[element][destination] == 0 &&
matrixGrid[element][destination] != 1 && matrixGrid[element][destination] != 2)
{
stack.push(destination);
visited[destination] = 3;
System.out.print(destination + "\t");
depth++;
if(matrixGrid[element][destination] == 3 || element ==
xdest && destination == ydest)
{
goalFound = true;
break Outer;
}
element = destination;
destination = 3;
break;
}
}
else
{
break;
}
destination++;
}
destination = stack.pop() + 1;
//depth--;
Efficient and Debugged Java Program for IDSearch_2

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
Java Program to Draw Shapes - Desklib
|10
|1283
|284

PriorityThreadQueue and ListManager
|4
|670
|24

Java Programs for Infix, Postfix and Interpreter
|88
|9426
|328

Implementation of Binary Search Tree in Java
|13
|706
|64

Java Programming Assignments with Solutions
|9
|904
|164

Vehicle Data Inventory System
|18
|2151
|53