java - 在找到解决方案之前 BFS 队列为空

Question

此 BFS 的目标是找到 3x2 拼图游戏的解决方案(0 是空白区域，您只能将棋子移动到该空间)

开始:

1 4 2

5 3 0

目标:

0 1 2

3 4 5

问题是在找到解决方案之前我的队列就变空了，这怎么可能？搜索树中的路径之一必须在此处返回解决方案。如果我可以澄清任何事情，请告诉我。

节点类(代表游戏的状态):

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

public class Node {
    public int[] state = new int[6];
    private 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(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(right());
                children.add(down());
                break;
            case 1:
                children.add(down());
                children.add(left());
                children.add(right());
                break;
            case 2:
                children.add(down());
                children.add(left());
                break;
            case 3:
                children.add(up());
                children.add(right());
                break;
            case 4:
                children.add(up());
                children.add(left());
                children.add(right());
                break;
            case 5:
                children.add(up());
                children.add(left());
                break;

        }
        return children;
    }

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


    public int getBlankIndex() {
        for (int i = 0; i < state.length; i++)
            if (state[i] == 0) return i;
        return -1;
    }

    public Node up(){
        int[] newer = state.clone();
        int blankIndex = getBlankIndex();
        int temp = newer[blankIndex - 3];
        newer[blankIndex] = temp;
        newer[blankIndex - 3] = 0;
        return new Node(newer, this);
    }
    public Node down(){
        int[] newer = state.clone();
        int blankIndex = getBlankIndex();
        int temp = newer[blankIndex + 3];
        newer[blankIndex] = temp;
        newer[blankIndex + 3] = 0;
        return new Node(newer, this);
    }

    public Node left(){
        int[] newer = state.clone();
        int blankIndex = getBlankIndex();
        int temp = newer[blankIndex - 1];
        newer[blankIndex] = temp;
        newer[blankIndex - 1] = 0;
        return new Node(newer, this);
    }
    public Node right(){
        int[] newer = state.clone();
        int blankIndex = getBlankIndex();
        int temp = newer[blankIndex + 1];
        newer[blankIndex] = temp;
        newer[blankIndex + 1] = 0;
        return new Node(newer, this);
    }

    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){
        if (object instanceof Node) {
            Node node2 = (Node) object;
            return (Arrays.equals(node2.getState(), this.getState()));
        }
        return false;
    }
    @Override
    public int hashCode() {
        return this.hashCode();
    }
}

驱动程序类别:

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 (!queue.isEmpty() && !current.isGoal()){
            current = queue.remove();
            for (Node child: current.getChildren()){
                if (!explored.contains(child)) {
                    queue.add(child);
                    explored.add(current);
                }
            }
        }

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

}

Answer 1

这是一个非常令人惊讶的问题!

我还没看代码，看起来差不多没问题。我将回答这个问题:问题是在找到解决方案之前我的队列就变空了， 这怎么可能？

代码不是问题。问题是你的谜题无法解决。

有趣的是

parity(permutation) * (-1)^{manhattanMetric(positionOfZeroTile)}

是在整个游戏过程中保留的不变量。

让我简单解释一下这意味着什么。(本质上与这里的论点相同:https://en.wikipedia.org/wiki/15_puzzle)

排列的奇偶性为(-1)^{numberOfTranspositions}。换位次数本质上就是交换次数冒泡排序需要对序列进行排序。零图 block 位置的曼哈顿度量是零图 block 的 x 坐标添加了零图 block 的 y 坐标。

每次将图 block 与零交换时，排列的奇偶校验都会发生变化标志。

同时，左上角和零图 block 的位置改变+1或-1。在这两种情况下，(-1)^{manhattanDist} 也会更改符号。

因此，奇偶校验和 (-1)^{manhattanDist} 的乘积是常数。

如果你现在看看已解决的游戏

0 1 2
3 4 5

则转置次数为0，奇偶校验为1，曼哈顿距离为0。因此，不变量是 (+1)。

但是，如果你看看这个:

1 4 2
5 3 0

然后你可以计算出换位次数是偶数(冒泡排序!)，奇偶校验为(+1)，曼哈顿距离为2+1=3，因此不均匀。因此，不变量是(+1) * (-1)^3 = (-1)。

但是 (-1) 不是 (+1)。因此，无论如何，你的游戏原则上都是无法解决你的 BFS 有多好。

<小时/>

另一种(更直观但不太严格)快速查看您的谜题是否已“损坏”的方法就是在开始时交换两个非零的图 block 。

1 4 2
3 5

这几乎可以立即解决:

1 4 2       1   2         1 2
3   5       3 4 5       3 4 5

所以，如果您不想浪费时间寻找不存在的错误，下次不要跳过群论讲座；)