Итеративная углубленная поисковая реализация 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, будет гораздо больше смысла, если вы вернете объект Node, а затем вернете ноль, если он не равен цели.

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): Оценка количества ходов для достижения целевого состояния