[解決済み] 反復深化探索のJava実装

質問

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

解決方法は？

つまり、あなたが実装しようとしているアルゴリズムは 反復深化型深層優先探索

まず、最初のコードである DLS メソッドは、最小の移動回数でゴール状態を見つける可能性を不可能にしています。

がありますね。

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

もし、現在の状態が目標状態に等しければ、深さは0になるはずである。 しかし、深さが0より大きければ、隣接するノードの探索を続けたいところである。

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) : ゴール状態に到達するまでの移動回数の推定値