0

我一直在尝试在 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;
    }
4

1 回答 1

2

因此，您尝试实现的算法是迭代深化深度优先搜索

首先，您在DLS方法中的第一行代码使得以最少的移动次数找到目标状态的可能性变得不可能。

你有：

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

如果当前等于目标状态，则希望深度等于 0。但是，如果深度大于 0，则您希望继续搜索相邻节点。

另外，我不确定您为什么要返回一个 int，如果您返回 Node 对象，然后如果它不等于目标则返回 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;
    }

总体而言，您在我提供的答案中并不太远，您必须将 findNeighbours() 更新为用于查找相邻节点的代码。我的示例为目标状态使用了一个局部变量，它是一个节点对象，当然，如果您愿意，您可以将其作为参数传递。

您可以看到这非常接近伪代码：

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)：估计达到目标状态的移动次数

于 2017-04-29T11:03:07.313 回答