广度优先搜索实现不工作
我有一个广度优先搜索算法的实现问题，我有一个方法，给我一个0-8的整数数组，以随机顺序。 我还有一个整数m，它告诉我哪个数字是空白的。 以下是规则：
我得到一个数字块，如：
456 782 301 并且假设8是空白值，我可以用5,7,2和0交换它，因为它们直接在它旁边。 我必须使用广度优先搜索来解决这个难题。 这是我到目前为止编写的代码：
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 OPEN = new LinkedHashSet(); public static HashSet CLOSED = new HashSet(); 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(); } }
此代码立即结束，永远找不到答案。 也许我做错了什么？ 请帮忙。
请注意：这是我在StackOverFlow上的第一个问题，所以如果有人有任何批评，请告诉我，我会马上修复它们。
首先，你有一个没有做任何事情的参数， Vector solution ：
public static void breadthFirstSearch(int[] num, int m, Vector solution1)
你也传递了你所代表的零元素的位置m，然后将一个局部变量分配给那个位置，对我来说似乎有点无意义如果你要搜索的话就没有必要传递零位置无论如何。
更新广度优先搜索方法：
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() 。 您没有创建数组的完整副本，因此导致对原始数组进行修改。
因此这个赋值： int[] str = s;
必须改为：
int[] str = new int[s.length]; System.arraycopy(s, 0, str, 0, s.length);
这是一个完整方法的示例：
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; } }
侧面注意 （不是必需的）：
arrays的某些排列不会导致目标状态。 这个拼图本身可以有9! 配置，但实际上只有9!/2这些是可解决的。
我写了一个用于检查拼图奇偶校验的算法，可以作为一种预处理来完成，我用它来创建用于测试数据的随机实例。
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; }
对于矢量
你希望能够打印出达到目标状态所采取的路径，我建议为State一个类：
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; }
然后，当你有目标State你可以遍历所有以前的状态以查看它所采用的路径。
State current = GOAL; while(current != null){ System.out.println(Arrays.toString(current)); current = current.getPreviousState(); }
方法up（…）有一个错误：
你有：
str[p] = str[p-3];
我猜应该是：
str[p] = temp;