IDA*：反复深化A*实施

Question

我创建了IDA*的通用版本。我正在尝试创建以下代码，具有非常高的质量和性能。我希望尝试创建有关的简短代码教程。但是，我的代码的质量可能不符合关于这个主题的教程的标准。我试图密切跟踪来自这里的伪代码。请让我知道，如果你能想到任何改进，我可以对以下。

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

我的回答主要是基于速度和一点点的设计。启发式和目标不应该是一个内部接口。这是因为多个算法使用一个启发式和目标。因此，它们应该是一个外部接口，以便其他算法可以使用它们。

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

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

为了更快地选择更合适的路径，我认为用启发式来排序这些值可能是个好主意。但是，我确保不多次计算启发式，这样做会导致算法在任何时间计算启发式时明显减慢。通过将结果存储在Map中，我避免了对启发式的多次调用。但是，在衡量性能时，这比以前的版本要慢得多。

此外，为了减少重复路径的数量，我在一个序列中跟踪所有已访问的节点。我不确定这是应该抽象到这个函数还是"GetChildren“函数。由于它所需的开销很小，而且速度很快，所以我决定将它包含在搜索中。为了减少开销，我使用了一个HashSet，如下所示：

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;
}

对于这个问题，在速度方面可能会有一些改进，包括多线程，其中hashset必须使用并发集来防止多线程问题。