迭代深化搜索 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

所以您要实现的算法是 Iterative deepening depth-first search

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

你有：

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

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

另外，我不确定你为什么要 return 一个 int，如果你 return 编辑 Node 对象然后 return 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 algorithm

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

g(node)：从起始节点到当前节点的移动量

h(node)：估计要走多少步才能达到目标状态

迭代深化搜索 Java 实现

Iterative Deepening Search Java Implementation

java

algorithm

search

nodes

iterative-deepening