广度优先搜索实现不工作 [英] Breadth-First Search implementation not Working
问题描述
我对广度优先搜索算法的实现有问题，我有一个方法，它以0-8的顺序给出一个0到8的整数数组。我还有一个整数m，它告诉我哪个数字是空白的。以下是规则：
I have a problem with the implementation of the breadth-first search algorithm, I have a method that gives me an array of integers from 0-8, in random order. I also have an integer m that tells me which number is blank. Here are the rules:
我得到一个数字块，例如：
I get a block of numbers, like:
456
782
301
让我们说8是空值，我可以用5,7,2和0交换它，因为它们就在它旁边。我必须使用广度优先搜索来解决这个难题。这是我到目前为止编写的代码：
And lets say that 8 is the blank value, I can swap it with 5, 7, 2, and 0. since they are directly next to it. I have to use breadth-first search to solve this puzzle. Here is the code I have written so far:
package application;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Vector;
public class Solution {
/******************************************
* Implementation Here
***************************************/
/*
* Implementation here: you need to implement the Breadth First Search
* Method
*/
/* Please refer the instruction document for this function in details */
public static LinkedHashSet<int[]> OPEN = new LinkedHashSet<int[]>();
public static HashSet<int[]> CLOSED = new HashSet<int[]>();
public static boolean STATE = false;
public static int empty;
public static void breadthFirstSearch(int[] num, int m, Vector solution1) {
int statesVisited = 0;
for(int i : num) {
if(num[i] == m) {
empty = i;
}
}
int[] start = num;
int[] goal = {0,1,2,3,4,5,6,7,8};
int[] X;
int[] temp = {};
OPEN.add(start);
while (OPEN.isEmpty() == false && STATE == false) {
X = OPEN.iterator().next();
OPEN.remove(X);
int pos = empty; // get position of ZERO or EMPTY SPACE
if (compareArray(X,goal)) {
System.out.println("SUCCESS");
STATE = true;
} else {
// generate child nodes
CLOSED.add(X);
temp = up(X, pos);
if (temp != null)
OPEN.add(temp);
temp = left(X, pos);
if (temp != null)
OPEN.add(temp);
temp = down(X, pos);
if (temp != null)
OPEN.add(temp);
temp = right(X, pos);
if (temp != null)
OPEN.add(temp);
if(OPEN.isEmpty())
System.out.println("Ending loop");
}
}
}
public static boolean compareArray(int[] a, int[] b) {
for(int i: a)
if(a[i] != b[i])
return false;
return true;
}
public static int[] up(int[] s, int p) {
int[] str = s;
if (p > 3) {
int temp = str[p-3];
str[p-3] = str[p];
str[p] = temp;
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return null;
}
public static int[] down(int[] s, int p) {
int[] str = s;
if (p < 6) {
int temp = str[p+3];
str[p+3] = str[p];
str[p] = temp;
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return null;
}
public static int[] left(int[] s, int p) {
int[] str = s;
if (p != 0 && p != 3 && p != 6) {
int temp = str[p-1];
str[p-1] = str[p];
str[p] = temp;
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return null;
}
public static int[] right(int[] s, int p) {
int[] str = s;
if (p != 2 && p != 5 && p != 8) {
int temp = str[p+1];
str[p+1] = str[p];
str[p] = temp;
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return null;
}
public static void print(String s) {
System.out.println(s.substring(0, 3));
System.out.println(s.substring(3, 6));
System.out.println(s.substring(6, 9));
System.out.println();
}
}
此代码刚刚结束，从未找到答案。也许我做错了什么？请帮助。
This code just immediately ends, and never finds an answer. Perhaps I have done something wrong? Please help.
请注意：这是我关于StackOverFlow的第一个问题，所以如果有人有任何批评，请告诉我，我会马上修复它们。
Please Note: This is my first question on StackOverFlow, so if anyone has any criticisms please tell me and I will fix them right away.
推荐答案
首先，你有一个没有做任何事情的参数，矢量解决方案 in：
First of all, you have a parameter which isn't doing anything, Vector solution in:
public static void breadthFirstSearch(int[] num, int m, Vector solution1)
你也传递了你所代表的零元素的位置为m，然后将一个局部变量赋值给那个位置，似乎对我来说有点无意义，如果你要去搜索它，就没有必要传递零位。
Also you are passing in the position of the zero element which you are representing as m, then assigning a local variable to that position, seems a little pointless to me there's no need to pass in the zero position if you're going to search for it anyway.
更新广度优先搜索方法：
Updated breadth first search method:
public static void breadthFirstSearch(int[] num) {
for (int i : num) {
if (num[i] == 0) {
empty = i;
}
}
int[] start = num;
int[] goal = {1, 2, 3, 4, 5, 6, 7, 8, 0};
int[] X;
int[] temp = {};
OPEN.add(start);
while (OPEN.isEmpty() == false && STATE == false) {
X = OPEN.iterator().next();
OPEN.remove(X);
int pos = empty; // get position of ZERO or EMPTY SPACE
if (Arrays.equals(X, goal)) {
System.out.println("SUCCESS");
STATE = true;
} else {
// generate child nodes
CLOSED.add(X);
temp = up(X, pos);
if (temp != null) {
OPEN.add(temp);
}
temp = left(X, pos);
if (temp != null) {
OPEN.add(temp);
}
temp = down(X, pos);
if (temp != null) {
OPEN.add(temp);
}
temp = right(X, pos);
if (temp != null) {
OPEN.add(temp);
}
if (OPEN.isEmpty()) {
System.out.println("Ending loop");
}
}
}
}
你的程序的主要问题是你的移动方法 up（）， down（）， left（）， right（）。您没有创建数组的完整副本，因此导致对原始数组进行修改。
The main issue with your program was that within your movement methods up(), down(), left(), right(). You weren't creating complete copies of the arrays, thus resulting in modifications happening to the original array.
因此，此赋值：
int [] str = s;
必须更改为：
int[] str = new int[s.length];
System.arraycopy(s, 0, str, 0, s.length);
以下是完整方法的示例：
Here's an example of a completed method:
public static int[] up(int[] s, int p) {
int[] str = new int[s.length];
System.arraycopy(s, 0, str, 0, s.length);
if (p > 3) {
int temp = str[p - 3];
str[p - 3] = str[p];
str[p] = temp;
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && !CLOSED.contains(str)) {
return str;
} else {
return null;
}
}
SIDE NOTE （不是必要）：
数组的某些排列不会导致目标状态。这个拼图本身可以有 9！配置的总数，但实际上只有 9！/ 2 这些是可以解决的。
There are certain permutations of the array which won't result in the goal state. This puzzle itself can have a total number of 9! configurations, but actually only 9!/2 of these are solvable.
我写了一个算法来检查奇偶校验的谜题，可以作为一种预处理来完成，我用它来创建随机实例来测试数据。
I wrote an algorithm for checking the parity of the puzzle, which can be done as a kind of preprocessing, I used it in order to create random instances for testing the data.
public boolean isSolvable(int[] puzzle) {
boolean parity = true;
int gridWidth = (int) Math.sqrt(puzzle.length);
boolean blankRowEven = true; // the row with the blank tile
for (int i = 0; i < puzzle.length; i++) {
if (puzzle[i] == 0) { // the blank tile
blankRowEven = (i / gridWidth) % 2==0;
continue;
}
for (int j = i + 1; j < puzzle.length; j++) {
if (puzzle[i] > puzzle[j] && puzzle[j] != 0) {
parity = !parity;
}
}
}
// even grid with blank on even row; counting from top
if (gridWidth % 2 == 0 && blankRowEven) {
return !parity;
}
return parity;
}
对于向量
您希望能够打印出达到目标状态的路径，我建议您为州 this：
You want to be able to print out the path that has been taken to get to the goal state, I would recommend having a class for the State such:
private State previousState;
private int[] current;
public State(int[] current, State previousState) {
this.current = current;
this.previousState = previousState
}
public State getPreviouState(){
return previousState;
}
public int[] getCurrentState(){
return currentState;
}
然后当你有目标州你可以遍历所有以前的状态以查看它所采用的路径。
Then when you have the goal State you can loop through all the previous States to see the path it took.
State current = GOAL;
while(current != null){
System.out.println(Arrays.toString(current));
current = current.getPreviousState();
}
这篇关于广度优先搜索实现不工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
