迭代加深搜索Java实施

Question

我一直在尝试在Java中实现迭代加深搜索。但是，由于某种原因，并非所有的孩子都被访问，导致结果不正确。到目前为止，这是我的代码：

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

因此，算法，您正在尝试实现迭代深度深度搜索

DLS方法中的所有第一行代码首先使在最小动作数中找到目标状态的可能性是不可能的。

您有：

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

如果电流等于目标状态，则希望深度等于0。如果深度大于0，则要继续搜索相邻的节点。

另外，我不确定您为什么要返回int，如果您返回节点对象，然后返回null(如果它不等于目标(会更有意义。

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

IDS方法：

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

总的来说，我提供的答案中，您不太遥远。我的示例使用局部变量作为节点对象的目标状态，如果您愿意，当然可以将其传递给参数。

您可以非常紧密地看到这是遵循的：

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

旁注：

我建议使用idastar算法

其中 f(node) = g(node) + h(node)：

g(node)：从开始节点

到达当前节点的动作量

h(node)：估计到达到目标状态的动作