我正在寻找Java代码，用于实现8数码游戏的深度优先搜索（DFS）和广度优先搜索（BFS），给定初始状态如下：
1 2 38 0 47 6 5和目标状态
2 8 10 4 37 6 5我需要打印从初始状态到目标状态的解路径（尚未完成）
这是我目前的代码。我到目前为止只能实现DFS。我的程序目前的功能是在找到目标状态时输出SUCCESS。然而，它从未达到这一步。
有人能告诉我我哪里做错了么？
回答：
好的，你的程序运行时间比预期的长。首先，我们需要找出它是陷入了无限循环，还是只是运行得慢。为了做到这一点，让我们通过在主循环中添加以下代码来让程序打印其进度：
int statesVisited = 0; while (OPEN.empty() == false && STATE == false) { statesVisited++; System.out.println(statesVisited);然后我们看到程序每秒访问几千个状态。由于我们的处理器每秒执行几十亿条指令，这意味着处理一个状态大约需要一百万条CPU指令。这不应该这么高，对吗？那么是什么导致了这一点呢？
一般来说，我们现在会使用性能分析器来测量代码中花费了多少时间，但由于程序很短，我们可以先尝试猜测。我的第一个猜测是打印我们访问的每个状态可能非常昂贵。为了验证这一点，让我们每1000个状态打印一次：
while (OPEN.empty() == false && STATE == false) { statesVisited++; if (statesVisited % 1000 == 0) { System.out.println(statesVisited); }有了这个变化，我们注意到前5000个状态在不到一秒内被访问，因此打印确实很重要。我们还注意到一些奇怪的事情：虽然前5000个状态在不到一秒内被访问，但不知为何程序似乎变得越来越慢。在访问了20000个状态时，访问1000个状态大约需要一秒，而且情况越来越糟。这出乎意料，因为处理一个状态不应该变得越来越昂贵。所以我们知道循环中的某个操作变得越来越昂贵。让我们回顾一下我们的代码，以确定可能是哪个操作。
推入和弹出操作无论集合大小如何都是常数时间。但你还使用了Stack.search和LinkedList.contains。这两个操作都记录需要遍历整个堆栈或列表。所以，让我们输出这些集合的大小：
if (statesVisited % 1000 == 0) { System.out.println(statesVisited); System.out.println(OPEN.size()); System.out.println(CLOSED.size()); System.out.println(); }稍等一会儿后，我们看到：
400002594739999所以OPEN包含25000个元素，而CLOSED接近40000个。这就解释了为什么处理一个状态变得越来越慢。因此，我们需要选择具有更高效的contains操作的数据结构，比如java.util.HashSet或java.util.LinkedHashSet（这是一个哈希集和链表的混合体，允许我们按添加顺序检索元素）。这样做，我们得到：
public static LinkedHashSet<String> OPEN = new LinkedHashSet<String>();public static HashSet<String> CLOSED = new HashSet<String>();public static boolean STATE = false;public static void main(String args[]) { int statesVisited = 0; String start = "123804765"; String goal = "281043765"; String X = ""; String temp = ""; OPEN.add(start); while (OPEN.isEmpty() == false && STATE == false) { X = OPEN.iterator().next(); OPEN.remove(X); int pos = X.indexOf('0'); // get position of ZERO or EMPTY SPACE if (X.equals(goal)) { System.out.println("SUCCESS"); STATE = true; } else { // generate children CLOSED.add(X); temp = up(X, pos); if (!(temp.equals("-1"))) OPEN.add(temp); temp = left(X, pos); if (!(temp.equals("-1"))) OPEN.add(temp); temp = down(X, pos); if (!(temp.equals("-1"))) OPEN.add(temp); temp = right(X, pos); if (!(temp.equals("-1"))) OPEN.add(temp); } }}/* * MOVEMENT UP */public static String up(String s, int p) { String str = s; if (!(p < 3)) { char a = str.charAt(p - 3); String newS = str.substring(0, p) + a + str.substring(p + 1); str = newS.substring(0, (p - 3)) + '0' + newS.substring(p - 2); } // Eliminates child of X if its on OPEN or CLOSED if (!OPEN.contains(str) && CLOSED.contains(str) == false) return str; else return "-1";}/* * MOVEMENT DOWN */public static String down(String s, int p) { String str = s; if (!(p > 5)) { char a = str.charAt(p + 3); String newS = str.substring(0, p) + a + str.substring(p + 1); str = newS.substring(0, (p + 3)) + '0' + newS.substring(p + 4); } // Eliminates child of X if its on OPEN or CLOSED if (!OPEN.contains(str) && CLOSED.contains(str) == false) return str; else return "-1";}/* * MOVEMENT LEFT */public static String left(String s, int p) { String str = s; if (p != 0 && p != 3 && p != 7) { char a = str.charAt(p - 1); String newS = str.substring(0, p) + a + str.substring(p + 1); str = newS.substring(0, (p - 1)) + '0' + newS.substring(p); } // Eliminates child of X if its on OPEN or CLOSED if (!OPEN.contains(str) && CLOSED.contains(str) == false) return str; else return "-1";}/* * MOVEMENT RIGHT */public static String right(String s, int p) { String str = s; if (p != 2 && p != 5 && p != 8) { char a = str.charAt(p + 1); String newS = str.substring(0, p) + a + str.substring(p + 1); str = newS.substring(0, (p + 1)) + '0' + newS.substring(p + 2); } // Eliminates child of X if its on OPEN or CLOSED if (!OPEN.contains(str) && CLOSED.contains(str) == false) return str; else return "-1";}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();}这几乎立即打印出”SUCCESS”。
