类 State :
类 Node :
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(){ // 生成所有可能的移动（已测试 - 运行良好） 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){ // 检查两个节点是否相同 return Arrays.deepEquals(this.getState().getData(), node.getState().getData());}public boolean checkTree(Node node){ // 检查节点是否已被添加到树中 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;}}类 main :
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("从初始状态到目标状态没有路径"); } 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("步骤数: " + numSteps); }}我想从初始状态找到到目标状态的最短路径（几乎与n-拼图游戏相同）
当我尝试以2×2大小的拼图作为输入运行我的程序时，它运行得很好。
例如，输入为：
int[][] initialState = { {2,1}, {3,0} };int[][] goalState = { {0,1}, {2,3} };结果将是：
[[2, 1], [3, 0]][[2, 1], [0, 3]][[0, 1], [2, 3]]步骤数: 2然而，对于n x n大小的输入（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方法的编写目的是为了避免在生成状态时可能发生的循环。
有人能找出我的错误吗？
回答：
回答晚了，但希望能帮助到某人：
代码中存在的问题主要是以下几行：
for(int i=0; i<row; i++){ for(int j=0; j<col; j++){ if ( matrix[i][j] == 0) { rowX = i; colX = j; } }}这导致只检查值为0的元素（在状态数据中）的“后继”或邻居。你需要检查所有元素的邻居。请注意代码中的注释：
我还认为术语有点混乱。我认为如果每个数据元素都代表一个节点，那么int[][] initialState = { {2,1}, {3,0} };将代表4个节点。这样一组节点构成一棵树，代表一个独特的状态。
