Iterative Deepening Search Java Implementation

Question

I have been trying to implement an Iterative Deepening Search in Java. However, for some reason, not all of the children, for each node are being visited, resulting in incorrect results. Here is my code so far:

public int IDS(Node start, Node goal){
        int depth = 0; //set starting depth to 0
        Node current=start; //current node is equal to start
        int goalNode=0; //goalNode is originally set to 0
        //List<Node> tempList=new ArrayList<Node>();

        while(goalNode==0){ //while goalNode is equal to 0
            List<Node> visited=new ArrayList<Node>(); //create an array list of nodes
            goalNode=DLS(current, goal, depth, visited); 
            depth++; //increment the depth
        }
        System.out.println("RESULT");
        return goalNode;
    }

    public int DLS(Node current, Node goal, int depth, List<Node> visited){
        if(depth>=0){
            if ( current == goal ){ //stop program
                System.out.println("REACHED GOAL");
                return current.value;
            }else{
                visited.add(current); //add the current node to visited list (in the beginning =start)

                List<Node> temp = Adjacency_List.get(current.value); //get children of current node

                for(Node node: temp){ //for each child
                    System.out.println("Current Node: "+current.value);
                    System.out.println(current.value + " - " + node.value);
                    if(node != null && !visited.contains(node)){
                        //tempList.add(node);
                        return DLS(node, goal, depth-1, visited);
                    }
                }
            }
        }else{
            return 0;
        }
        return 0;
    }

Answer 1

So the algorithm, you are trying to implement is the Iterative deepening depth-first search

First of all your first line of code within the DLS method makes the possibility of finding the goal state in the minimum number of moves impossible.

you have:

   if (depth >= 0) {
            if (current == goal) { //stop program
                System.out.println("REACHED GOAL");
                return -1;
            }

If the current was equal to the goal state then hopefully the depth would equal 0. If the depth is greater than 0 however, you want to continue searching the neighboring nodes.

Also, I'm not sure why you're returning an int, would make much more sense if you returned the Node object and then return null if it's not equal to the goal.

DLS:

  public Node DLS(Node current, int depth) {
        if (depth == 0 && current == goal) {
            return current;
        }
        if (depth > 0) {
            for (Node child : current.findNeighbours()) {
                Node found = DLS(child, depth - 1);
                if (found != null) {
                    return found;
                }
            }
        }
        return null;
    }

The IDS method:

  public Node IDS(Node root) {
        // loops through until a goal node is found
        for (int depth = 0; depth < Integer.MAX_VALUE; depth++) {
            Node found = DLS(root, depth);
            if (found != null) {
                return found;
            }
        }
        // this will never be reached as it 
        // loops forever until goal is found
        return null;
    }

Overall though, you're not too far off in the answer I provided you will have to update the findNeighbours() to the code you used for finding the adjacent nodes. My example uses a local variable for the goal state which is a node object, you can, of course, pass it as a parameter if you wish.

You can see that this follows the pseudocode very closely:

function IDDFS(root)
    for depth from 0 to ∞
        found ← DLS(root, depth)
        if found ≠ null
            return found

function DLS(node, depth)
    if depth = 0 and node is a goal
        return node
    if depth > 0
        foreach child of node
            found ← DLS(child, depth−1)
            if found ≠ null
                return found
    return null

Side note:

What I would recommend would be to use the IDAstar algorithm

Where f(node) = g(node) + h(node):

g(node): The amount of moves to get to the current node from the start node

h(node): An estimation of how many moves to reach the goal state