Java:使用 BFS 寻找最短路径时出现问题

Question

类状态:

import java.util.Arrays;

public class State {
private int data[][];

public int[][] getData() {
    return data;
}

public void setData(int[][] data) {
    this.data = data;
}
public void swap(int row1, int col1, int row2, int col2){
    int temp = this.data[row1][col1];
    this.data[row1][col1] = this.data[row2][col2];
    this.data[row2][col2] = temp;

}
public State copyState() {
    int height = this.data.length;
    int width = this.data[0].length;
    int[][] temp = new int[height][width];
    for (int i = 0; i < height; i++) {
        for(int j=0; j< width; j++){
            temp[i][j] = this.data[i][j];
        }
    }
    State target = new State(temp);
    return target;      
}

public State(int[][] data) {
    super();
    this.data = data;
}
}

类节点:

public class Node {
private State state;
private Node parent;
private ArrayList<Node> children;

public Node(State state){
    this.state = state;
    parent = null;
    children = new ArrayList<>();
}

public State getState() {
    return state;
}
public void setState(State state) {
    this.state = state;
}
public Node getParent() {
    return parent;
}
public void setParent(Node parent) {
    this.parent = parent;
}
public ArrayList<Node> getChildren() {
    return children;
}
public void addChild(Node node){
    node.setParent(this);
    this.children.add(node);
}
public ArrayList<Node> returnSuccessor(){ // generate all possible moves(has been tested - work well)
    ArrayList<Node> result = new ArrayList<>();
    int[][] matrix = this.getState().getData();
    int row = matrix.length;
    int col = matrix[0].length;
    int rowX = 0;
    int colX = 0;

    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            if ( matrix[i][j] == 0) {
                rowX = i;
                colX = j;
            }
        }
    }

    if( (colX-1) >= 0 ){
        State temp = this.getState().copyState();
        temp.swap(rowX, colX, rowX, colX-1);
        Node left = new Node(temp);
        result.add(left);
    }
    if ( (colX+1) < col ){
        State temp = this.getState().copyState();
        temp.swap(rowX, colX, rowX, colX+1);
        Node right = new Node(temp);
        result.add(right);
    }
    if ( (rowX-1) >= 0 ){
        State temp = this.getState().copyState();
        temp.swap(rowX, colX, rowX-1, colX);
        Node top = new Node(temp);
        result.add(top);
    }
    if ( (rowX+1) < row ){
        State temp = this.getState().copyState();
        temp.swap(rowX, colX, rowX+1, colX);
        Node down = new Node(temp);
        result.add(down);
    }

    return result;
}


public void printState(){
    System.out.println(Arrays.deepToString(this.getState().getData()));
}

public boolean equal(Node node){ // check whether 2 nodes are the same
    return Arrays.deepEquals(this.getState().getData(), node.getState().getData());
}
public boolean checkTree(Node node){ // check whether a node has been added into the tree or not
    if (this.equal(node)) { 
        return true;
    }
    ArrayList<Node> children = this.getChildren();
    boolean result = false;
    if (children.size() > 0){
        for(int i=0; result == false && i< children.size(); i++){
            result = children.get(i).checkTree(node);
        }
    }
    return result;
}
}

主要类:

public class main {
public static void BFS(Node root, Node goal) throws InterruptedException{
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while(queue.size()>0){
    Node temp = queue.poll();
    if (temp.equal(goal)) {
        goal.setParent(temp.getParent());
        break;
    }
    else{
        ArrayList<Node> successor = temp.returnSuccessor();
        for(int i=0; i< successor.size(); i++){
            boolean check = root.checkTree(successor.get(i));
            if (check == false){
                queue.add(successor.get(i));
                temp.addChild(successor.get(i));
            }
        }
    }
  }
}
public static void main(String[] args) throws InterruptedException {
    int[][] initialState = { {2,1}, {3,0} };
    int[][] goalState = { {0,1}, {2,3} };
    Node root = new Node(new State(initialState));
    Node goal = new Node(new State(goalState));
    BFS(root,goal);
    Node temp = goal;
    if(temp.getParent() ==  null){
        System.out.println("There is no such a way to go from the initial state to the goal state");
    }
    else{
        ArrayList<Node> listSteps = new ArrayList<>();
        while(temp != null){
            listSteps.add(temp);
            temp = temp.getParent();
    }
        for (int i=listSteps.size()-1; i>=0; i--){
            listSteps.get(i).printState();
            Thread.sleep(1000);
        }
        int numSteps = listSteps.size()-1;
        System.out.println("Number of steps: " + numSteps);
    }
}

我想找到一条从初始状态到目标状态的最短路径(与n-puzzle游戏几乎相同)

当我尝试以 2x2 大小的拼图作为输入运行我的程序时，它运行良好。

例如输入:

int[][] initialState = { {2,1}, {3,0} };
int[][] goalState = { {0,1}, {2,3} };

结果将是:

[[2, 1], [3, 0]]
[[2, 1], [0, 3]]
[[0, 1], [2, 3]]
Number of steps: 2

但是，它有一个 nxn size(n>2) 的无限循环

示例输入:

int[][] initialState = { {7,2,4}, {5,0,6}, {8,3,1} };
int[][] goalState = { {0,1,2}, {3,4,5}, {6,7,8} };

在DFS方法中不断向队列中添加节点

这让我感到困惑，因为 Node 类中的方法 checkTree 的编写目的是为了避免在生成状态时可能发生的循环。

有人能找出我的错误是什么吗？

Answer 1

迟到的答案，但我希望它能帮助别人:
发布的代码中的基本问题是这些行:

for(int i=0; i<row; i++){
    for(int j=0; j<col; j++){
        if ( matrix[i][j] == 0) {
           rowX = i;
           colX = j;
        }
    }
}

这会导致仅针对值为 0 的元素(在状态数据中)检查“后继者”或邻居。您需要检查所有元素的邻居。注意代码中的注释:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class Main {

    public static void BFS(Node root, Node goal) throws InterruptedException{
        Queue<Node> queue = new LinkedList<>();
        Set<Node> visited = new HashSet<>(); //**use to flow which nodes were tested
        queue.add(root);
        while(queue.size()>0){
            Node temp = queue.poll();
            if (temp.equals(goal)) {
                goal.setParent(temp.getParent());
                break;
            }
            else{
                List<Node> successor = temp.returnSuccessor();
                for(int i=0; i< successor.size(); i++){
                    //** made redundant by using visited boolean check = root.checkTree(successor.get(i));
                    Node node = successor.get(i);
                    if (visited.add(node)){ //** successful add indicates it was not visited before
                        queue.add(node);
                        temp.addChild(node);
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws InterruptedException {

        int[][] initialState = { {0,1}, {2,3}, {4,5} };
        int[][] goalState = {{3,4}, {5,0}, {1,2}};

        Node root = new Node(new State(initialState));
        Node goal = new Node(new State(goalState));
        BFS(root,goal);

        if(goal.getParent() ==  null){
            System.out.println("There is no such a way to go from the initial state to the goal state");
        }
        else{
            ArrayList<Node> listSteps = new ArrayList<>();
            while(goal != null){
                listSteps.add(goal);
                goal = goal.getParent();
            }
            for (int i=listSteps.size()-1; i>=0; i--){
                System.out.println(listSteps.get(i));
            }
            int numSteps = listSteps.size()-1;
            System.out.println("Number of steps: " + numSteps);
        }
    }
}

class State {
    private int data[][];

    public int[][] getData() {  return data;}

    public void setData(int[][] data) { this.data = data;   }
    public void swap(int row1, int col1, int row2, int col2){
        int temp = data[row1][col1];
        data[row1][col1] = data[row2][col2];
        data[row2][col2] = temp;
    }

    public State copyState() { //**simpler version of
        int i = 0;
        int[][] temp = new int[data.length][];
        for (int[] row : data) {
            temp[i++] = Arrays.copyOf(row, row.length); //**simpler way to copy array
        }
        return new State(temp);
    }

    public State(int[][] data) {
        super();
        this.data = data;
    }
}

class Node {
    private State state;
    private Node parent;
    private ArrayList<Node> children;

    public Node(State state){
        this.state = state;
        parent = null;
        children = new ArrayList<>();
    }

    public State getState() {   return state; }
    public void setState(State state) { this.state = state; }
    public Node getParent() { return parent;}
    public void setParent(Node parent) { this.parent = parent;  }
    public ArrayList<Node> getChildren() {  return children;    }
    public void addChild(Node node){
        node.setParent(this);
        children.add(node);
    }

    public List<Node> returnSuccessor(){
        List<Node> result = new ArrayList<>();
        int[][] matrix = getState().getData();
        int row = matrix.length;
        int col = matrix[0].length;

        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                   /* need to check possible move for ALL nodes
                    * if ( matrix[i][j] == 0) {
                    rowX = i;
                    colX = j;
                   }*/

                    if( (j-1) >= 0 ){
                        State temp = getState().copyState();
                        temp.swap(i, j, i, j-1);
                        Node left = new Node(temp);
                        result.add(left);
                    }
                    if ( (j+1) < col ){
                        State temp = getState().copyState();
                        temp.swap(i, j, i, j+1);
                        Node right = new Node(temp);
                        result.add(right);
                    }
                    if ( (i-1) >= 0 ){
                        State temp = getState().copyState();
                        temp.swap(i, j, i-1, j);
                        Node top = new Node(temp);
                        result.add(top);
                    }
                    if ( (i+1) < row ){
                        State temp = getState().copyState();
                        temp.swap(i, j, i+1, j);
                        Node down = new Node(temp);
                        result.add(down);
                    }
            }
        }
        return result;
    }

    //override toString rather than creating
    @Override
    public String toString(){
        return Arrays.deepToString(getState().getData());
    }

    //**override equals rather than creating your own equal
    @Override
    public boolean equals(Object node){

           if (node == this) { return true; }
           if (node == null) { return false;}
           if (!(node instanceof Node)) {return false; }
        return Arrays.deepEquals(getState().getData(), ((Node)node).getState().getData());
    }

    //** override hashCode so each Node has a unique one
    @Override
    public int hashCode() {
        return toString().hashCode();
    }
}  

我还觉得术语有点困惑。我认为如果每个数据元素代表一个节点，它就会被清除，所以 int[][] initialState = { {2,1}, {3,0} }; 代表 4 个节点。这些节点的集合创建了一棵树，代表一个独特的状态。