java - BFS 不知情的搜索问题

Question

我试图避免无限循环，但无法找出问题所在。这应该为 3x2 拼图板找到解决方案。我怀疑问题可能出在我重写的 equals 方法上，但我不确定。遇到两个问题:

1) 它不断地重新探索已经探索过的节点。

2) 在找到解之前队列为空，导致错误。

驱动类:

import java.util.*;

public class Driver {

    public static void main(String[] args){
        Node test = new Node(new int[]{1, 4, 2, 5, 3, 0}, null);
        BFS(test);
        System.out.println("done");
    }

    public static void BFS(Node initial){
        Queue<Node> queue = new LinkedList<>();
        ArrayList<Node> explored = new ArrayList<>();
        queue.add(initial);
        Node current = initial;
        while (!current.isGoal()){
            current = queue.remove();
            for (Node child: current.getChildren()){
                if (!explored.contains(child)) queue.add(child);
            }
            explored.add(current);
            current.print();
        }

        System.out.println("DONEDONEDONE");
        current.printTrace();
    }

    public static void DFS(Node initial){

    }
}

节点类:

import java.lang.reflect.Array;
import java.util.*;

public class Node {
    int[] state;
    Node parent;

    public Node(int[] initialState, Node parent){
        this.parent = parent;
        this.state = initialState;
    }

    public boolean isGoal(){
        int[] goal = {0,1,2,3,4,5};
        return Arrays.equals(this.state, goal);
    }

    public ArrayList<Node> getChildren(){
        ArrayList<Node> children = new ArrayList<>();
        Integer[] newInt = new Integer[getState().length];
        for (int i = 0; i < getState().length; i++) {
            newInt[i] = Integer.valueOf(getState()[i]);
        }
        int position = Arrays.asList(newInt).indexOf(0);
        switch(position){
            case 0:
                children.add(new Node(switchPos(0,3), this));
                children.add(new Node(switchPos(0,1), this));
                break;
            case 1:
                children.add(new Node(switchPos(1,0), this));
                children.add(new Node(switchPos(1,4), this));
                children.add(new Node(switchPos(1,2), this));
                break;
            case 2:
                children.add(new Node(switchPos(2,1), this));
                children.add(new Node(switchPos(2,5), this));
                break;
            case 3:
                children.add(new Node(switchPos(3,0), this));
                children.add(new Node(switchPos(3,4), this));
                break;
            case 4:
                children.add(new Node(switchPos(4,3), this));
                children.add(new Node(switchPos(4,5), this));
                children.add(new Node(switchPos(4,1), this));
                break;
            case 5:
                children.add(new Node(switchPos(5,2), this));
                children.add(new Node(switchPos(5,4), this));
                break;

        }
        return children;
    }

    public int[] getState(){
        return this.state;
    }

    public int[] switchPos(int index1, int index2){
        int[] newer = getState().clone();
        int temp = newer[index1];
        newer[index1] = newer[index2];
        newer[index2] = temp;
        return newer;

    }

    public void print(){
        System.out.println("---------");
        System.out.println(Arrays.toString(Arrays.copyOfRange(getState(), 0, 3)));
        System.out.println(Arrays.toString(Arrays.copyOfRange(getState(), 3, 6)));
        System.out.println("---------");
    }

    public void printTrace(){
        Stack<Node> stack = new Stack<>();
        Node current = this;
        while (current.parent != null){
            stack.push(current);
            current = current.parent;
        }
        while (!stack.isEmpty()){
            stack.pop().print();
        }
    }

    @Override
    public boolean equals(Object object){
        Node node2 = (Node) object;
        return (Arrays.equals(node2.getState(), this.getState()));
    }
}

Answer 1

你的代码中唯一真正的错误是你不检查队列是否在 while 条件下为空，因此假设所有状态都可以从任何初始状态获得(这是不正确的).

我还应该提到，在处理节点之后将节点标记为“已探索”并不是最好的策略，因为重复的节点可能会(来自不同的父节点)在它们中的任何一个被处理之前入队处理。请注意，它们都将打印为 current，尽管它们的所有子节点都已被处理——这可能看起来您的算法正在重新探索相同的节点。事实上，它没有。这只是在浪费周期，仅此而已。

这是一个更好的驱动程序版本，它不允许队列中出现重复项:

Queue<Node> queue = new LinkedList<>();
ArrayList<Node> explored = new ArrayList<>();
queue.add(initial);
Node current = initial;
explored.add(initial);
while (!queue.isEmpty() && !current.isGoal()){
    current = queue.remove();
    for (Node child: current.getChildren()){
        if (!explored.contains(child)) {
            queue.add(child);
            explored.add(child);
        }
    }
    current.print();
}

重要的是每个节点在第一次被推送到队列时都被标记为“已探索”。然而，它仍然没有达到“目标”，因为从这个特定的初始状态确实无法到达它。