IDA*: Iterative Deepening A* implementation

Question

I created a generic version of IDA*. I am attempting to create the following code with exceptional quality and performance. I'm hoping to try and create short code tutorials regarding. However, the quality of my code may not be up to standard for a tutorial on the subject. I attempted to closely follow the pseudocode from here. Please let me know if you can think of any improvements I can make to the following.

public interface Node<T extends Node<T>> {
    public T[] getChildren();
    public T[] getVisitedNodes();
    public int getCost();
}
public class IDAStar {
    /**
     * Takes in a Node<T> vb, a Heuristic using the Node<T>(This is an anonymous function) and a Goal.
     * Returns a List of the visited nodes or null if it could not find the desired node.
     * Note: This could run forever if it can't find the given node and there are an infinite number of nodes to process.
     * @param vb
     * @param h
     * @param g
     * @return
     */
    public static <T extends Node<T>> List<T> IDA_Star(T vb, Heuristic<T> h, Goal<T> g)
    {
            int bound=h.getHeuristic(vb);
            while(true)
            {
                    IDAStarRet<T> found=search(vb, 0, bound, h, g);
                    switch(found.getSearchReturn())
                    {
                            case BOUND:
                                    bound=found.getHeuristic();
                                    break;
                            case FOUND:
                                    return found.getVisitedNodes();
                            case NOT_FOUND:
                                    return null;
                    }
            }
    }
    private static <T extends Node<T>> IDAStarRet<T> search(T currentNode, int currentCost, int bound, Heuristic<T> h, Goal<T> goal) {
            int estimatedCost=currentCost+h.getHeuristic(currentNode);
            IDAStarRet<T> ret=new IDAStarRet<T>();

            //If estimatedCost is greater than the bound, return and set the new bound appropriately.
            if(estimatedCost>bound)
            {
                    ret.setSearchReturn(SEARCHRETURN.BOUND);
                    ret.setHeuristic(estimatedCost);
                    return ret;
            }

            //Check if the currentNode is the goal.
            if(goal.isGoal(currentNode))
            {
                    ret.setSearchReturn(SEARCHRETURN.FOUND);
                    ret.setVisitedNodes(Arrays.asList(currentNode.getVisitedNodes()));
                    return ret;
            }

            //Set to an arbitrarily large value, to make sure that any available values replace this.
            int min=Integer.MAX_VALUE;

            //Iterate through all of the current nodes children.
            //Should I sort the children based on the heuristic here?
            //Note: This was a bad idea.  Sorting decreased the speed significantly.
            for(T successor:currentNode.getChildren())
            {
                    //Get the return value for each of the children.
                    IDAStarRet<T> t=search(successor, currentCost+successor.getCost(), bound, h, goal);
                    switch(t.getSearchReturn())
                    {
                            case BOUND:
                                    if(t.getHeuristic()<min)
                                            min=t.getHeuristic();
                                    break;
                            case FOUND:
                                    return t;
                            case NOT_FOUND:
                                    continue;
                    }
            }

            //If the minimum did not change, then the node could not be found.
            if(min==Integer.MAX_VALUE)
            {
                    ret.setSearchReturn(SEARCHRETURN.NOT_FOUND);
            }
            else
            {
                    ret.setHeuristic(min);
                    ret.setSearchReturn(SEARCHRETURN.BOUND);
            }
            return ret;
    }
    public static interface Heuristic <T>
    {
            public int getHeuristic(T item);
    }
    public static interface Goal <T>
    {
            public boolean isGoal(T n);
    }
    private static enum SEARCHRETURN { BOUND, FOUND, NOT_FOUND };
    /**
     * Returns a value associated with IDA*.
     * If it is found, it will return a list of visited nodes.
     * Otherwise it will return a heuristic or NOT FOUND.
     *
     * @param <T>
     */
    private static class IDAStarRet <T extends Node<T>> {
            private SEARCHRETURN sr;
            private int newHeuristic;
            private List<T> visitedNodes;
            public SEARCHRETURN getSearchReturn()
            {
                    return sr;
            }
            public void setSearchReturn(SEARCHRETURN sr)
            {
                    this.sr=sr;
            }

            public void setHeuristic(int newHeuristic)
            {
                    this.newHeuristic=newHeuristic;
            }
            public int getHeuristic()
            {
                    return newHeuristic;
            }

            public void setVisitedNodes(List<T> visitedNodes)
            {
                    this.visitedNodes=visitedNodes;
            }
            public List<T> getVisitedNodes()
            {
                    return this.visitedNodes;
            }

    }    
}

Answer 1

My answer is primarily speed based and a little bit on the design. The Heuristic and Goal should not be an inner interface. This is because multiple algorithms use a Heuristic and Goal. As such, they should be an outer interface so that other algorithms can use them.

public interface Goal <T>
{
        public boolean isGoal(T n);
}

public interface Heuristic <T>
{
        public int getHeuristic(T item);
}

To choose the more appropriate path quicker, I thought it may be a good idea to sort the values by heuristic. I made sure that calculating the heuristic was not done multiple times, however; doing this caused a significant slow down in the algorithm when it takes any time to calculate the heuristic. I avoided multiple calls to the heuristic by storing the results in a Map. However, when the performance was measured; this was significantly slower than the previous version.

Furthermore to reduce the number of duplicate paths, I keep track of all visited nodes in a sequence. I'm not sure if this should be abstracted to this function or to the "GetChildren" function. Since it requires little overhead and it is fast I decided to include it in the search. To keep overhead small I used a HashSet as follows:

private static <T extends Node<T>> IDAStarRet<T> search(T currentNode, int currentCost, int bound, Heuristic<T> h, Goal<T> goal, HashSet<T> visitedNodes) {
    IDAStarRet<T> ret=new IDAStarRet<T>();

    //Check if the currentNode is the goal.
    if(goal.isGoal(currentNode))
    {           
        ret.setSearchReturn(SEARCHRETURN.FOUND);
        ret.setVisitedNodes(currentNode.getVisitedNodes());
        return ret;
    }
    int estimatedCost=currentCost+h.getHeuristic(currentNode);

    //If estimatedCost is greater than the bound, return and set the new bound appropriately.
    if(estimatedCost>bound)
    {
        ret.setSearchReturn(SEARCHRETURN.BOUND);
        ret.setHeuristic(estimatedCost);
        return ret;
    }
    //Add the current node to the list of visited nodes.  This node will never be reached again during this sequence.
    visitedNodes.add(currentNode);

    //Set to an arbitrarily large value, to make sure that any available values replace this.
    int min=Integer.MAX_VALUE;
    List<T> successors=currentNode.getChildren();
    for(T successor:successors)
    {
        if(!visitedNodes.contains(successor))
        {
            //Get the return value for each of the children.
            IDAStarRet<T> t=search(successor, currentCost+successor.getCost(), bound, h, goal, visitedNodes);
            switch(t.getSearchReturn())
            {
                case BOUND:
                    if(t.getHeuristic()<min)
                        min=t.getHeuristic();
                    break;
                case FOUND:
                    return t;
                case NOT_FOUND:
                    continue;
            }
        }
    }



    //If the minimum did not change, then the node could not be found.
    if(min==Integer.MAX_VALUE)
    {
        ret.setSearchReturn(SEARCHRETURN.NOT_FOUND);
    }
    else
    {
        ret.setHeuristic(min);
        ret.setSearchReturn(SEARCHRETURN.BOUND);
    }
    //Remove this visited node from the list of nodes.
    //This makes it so that other sequences can still contain this node and possibly be less than the currentBound.
    visitedNodes.remove(currentNode);
    return ret;
}

Some possible improvements with regards to speed for this problem would include multi-threading in which the hashset would have to use a concurrent set to prevent issues with multithreading.