BFS不知情的搜索问题 [英] BFS uninformed search issue

问题描述

我正在尝试避免无限循环，并且在找出问题所在时遇到了麻烦。应该可以找到3x2拼图板的解决方案。我怀疑问题可能出在我覆盖的equals方法上，但我不确定。遇到两个问题：

I am trying to avoid an infinite loop and am having trouble figuring out whats wrong. This is supposed to find a solution for a 3x2 puzzle board. I suspect the problem may be with my overridden equals method but I'm not sure. Running into two issues:

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

1) It keeps re-exploring already explored nodes.

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

推荐答案

您代码中唯一真正的错误是，您不会在 while 条件下检查队列是否为空，因此假设所有状态都可以从任何初始状态使用（这只是

The only real bug in your code is that you don't check if the queue is empty in the while condition, thus assuming that all states are available from any initial state (that's just not true).

我还应该提到，在处理完节点后将节点标记为已探究 不是最佳策略，因为在处理任何重复节点之前，它们可能会排队（来自不同的父节点）。请注意，尽管它们的所有子节点都已经处理过，但它们都将被打印为 current ，这看起来像是您的算法正在重新探索相同的节点。实际上，事实并非如此。只是浪费循环，仅此而已。

I should also mention that marking the node as "explored" after the node is processed is not the best strategy, because duplicate nodes may be enqueued (from different parents), before any of them is processed. Note that they all will be printed as current, though all of their children are already processed -- and this may look like your algorithm is re-exploring the same nodes. In fact, it doesn't. It's just wasting cycles, that's all.

这是更好的驱动程序版本，不允许在队列中重复：

Here's a better version of the driver that doesn't allow duplicates in a queue:

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

本质是每个节点在首次推送时都标记为已探索排队。但是，它仍然无法达到目标，因为
确实无法从此特定初始状态到达。

Essential is that each node is marked as "explored" when it is first pushed to the queue. However, it still does not reach the "goal", because it is really unreachable from this particular initial state.

这篇关于BFS不知情的搜索问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！