Java: 使用 BFS 寻找最短路径时出现问题
Java: Trouble when using BFS to find a shortest path
Class 状态：
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;
}
}
Class节点：
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;
}
}
Class 主要 :
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 大小的无限循环(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方法
中不断向队列中添加节点
这让我很困惑，因为 class 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;
}
}
}
这导致检查 "successor" 或邻居，仅针对值为 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 个节点。
这些节点的集合创建了一棵树，代表一个独特的状态。
Class 状态：
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;
}
}
Class节点：
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;
}
}
Class 主要 :
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 大小的无限循环(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方法
中不断向队列中添加节点这让我很困惑，因为 class 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;
}
}
}
这导致检查 "successor" 或邻居，仅针对值为 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 个节点。
这些节点的集合创建了一棵树，代表一个独特的状态。