Java 使用 DFS 解决 8-Puzzle
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/25230298/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Solving 8-Puzzle using DFS
提问by RK2015
I am looking for code in java that implement DFS and BFS for the 8-puzzle game by given initial state :
我正在寻找通过给定初始状态为 8 拼图游戏实现 DFS 和 BFS 的 Java 代码：
1 2 3
8 0 4
7 6 5
and Goal state
和目标状态
2 8 1
0 4 3
7 6 5
I need to print the solution path from initial to goal state (Not done yet)
我需要打印从初始状态到目标状态的解决方案路径（尚未完成）
This is the code I have. So far I have only been able to implement DFS. What my program does so far is it outputs SUCCESS once it finds the goal state. However it never gets to this point.
这是我的代码。到目前为止，我只能实现 DFS。到目前为止，我的程序所做的是在找到目标状态后输出 SUCCESS。然而，它永远不会达到这一点。
Can someone tell me where I am going wrong?
有人能告诉我我哪里出错了吗？
采纳答案by meriton
Ok, so your program is taking longer than expected. First we'll want to find out if it is stuck in an infinite loop, or just slow. To do that, let's have the program print its progress by adding the following to the main loop:
好的，所以您的程序花费的时间比预期的要长。首先，我们想知道它是否陷入无限循环，或者只是缓慢。为此，让程序通过将以下内容添加到主循环来打印其进度：
int statesVisited = 0;
while (OPEN.empty() == false && STATE == false) {
statesVisited++;
System.out.println(statesVisited);
We then see that the program visited a couple thousand states per second. Since our processor executes several billion instructions per second, this implies processing a state takes about a million cpu instructions. It shouldn't be that high, should it? So what could be causing this?
然后我们看到程序每秒访问了几千个状态。由于我们的处理器每秒执行数十亿条指令，这意味着处理一个状态需要大约一百万条 CPU 指令。应该不会那么高吧？那么是什么原因造成的呢？
Generally speaking, we'd now use a profiler to measure just what part of the code all this time is spent in, but since the program is so short we can try guessing first. My first guess is that printing every state we visit could be quite expensive. To verify this, let's print only every 1000th state:
一般来说，我们现在会使用分析器来衡量所有时间都花在了代码的哪一部分上，但由于程序太短，我们可以先尝试猜测。我的第一个猜测是打印我们访问的每个州可能会非常昂贵。为了验证这一点，让我们只打印第 1000 个状态：
while (OPEN.empty() == false && STATE == false) {
statesVisited++;
if (statesVisited % 1000 == 0) {
System.out.println(statesVisited);
}
We that change in place, we notice that the first 5000 states are visited in under second, so printing was indeed significant. We also notice something curious: While the first 5000 states are visited in under a second, for some reason the program seems to get slower and slower. At 20000 states visited, it takes about a second to visit 1000 states, and it keeps getting worse. This is unexpected, as processing a state should not get more and more expensive. So we know some operation in our loop is getting increasingly more expensive. Let's review our code to identify which operation it could be.
我们进行了更改，我们注意到前 5000 个状态在不到一秒的时间内被访问，因此打印确实很重要。我们还注意到一些奇怪的事情：虽然前 5000 个状态在不到一秒的时间内被访问，但出于某种原因，程序似乎变得越来越慢。在访问了 20000 个州时，访问 1000 个州需要大约一秒钟的时间，而且情况越来越糟。这是出乎意料的，因为处理状态不应该变得越来越昂贵。所以我们知道循环中的某些操作变得越来越昂贵。让我们回顾一下我们的代码，以确定它可能是哪个操作。
Pushing and popping takes constant time regardless of the size of the collection. But you also use Stack.search and LinkedList.contains. Both these operations are documented to require iterating over the entire stack or list. So, let's output the sizes of these collections:
无论集合的大小如何，推送和弹出都需要恒定的时间。但您也使用 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();
}
After waiting a little while, we see:
稍等片刻后，我们看到：
40000
25947
39999
So OPEN contains 25000 elements, and CLOSED nearly 40000. That explains why processing a state keeps getting slower and slower. We'll therefore want to choose data structures with a more efficient contains operation, such as a java.util.HashSetor java.util.LinkedHashSet(which is a hybrid between a hash set and a linked list, permitting us the retrieve elements in the order they were added). Doing this, we get:
所以 OPEN 包含 25000 个元素，而 CLOSED 包含近 40000 个。这就解释了为什么处理状态越来越慢。因此，我们希望选择具有更高效包含操作的数据结构，例如java.util.HashSetor 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();
}
which prints "SUCCESS" nearly instantly.
几乎立即打印“成功”。
回答by Dici
You shouldn't push in your open Stack combinations that were already added to it. (Plus, an ArrayDeque would be better, Stack is an old class, see he javadoc http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
您不应该推入已经添加到其中的开放堆栈组合。（另外，ArrayDeque 会更好，Stack 是一个旧类，请参阅 javadoc http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
Deque stack = new ArrayDeque(); )
Deque 接口及其实现提供了一组更完整和一致的 LIFO 堆栈操作，应优先使用此类。例如：
Deque stack = new ArrayDeque(); )
To avoid exploring countless times the same states, you must use a Set as your closed list and verify that the state you are trying to add in the open list were never added to the closed list.
为了避免无数次探索相同的状态，您必须使用 Set 作为您的关闭列表，并验证您尝试添加到打开列表中的状态从未添加到关闭列表中。
Also, you might be more comfortable using byte[] arrays (not int[] to save memory) rather than strings to perform your operations.
此外，您可能更喜欢使用 byte[] 数组（而不是 int[] 来节省内存）而不是字符串来执行您的操作。
To sum up, you could structure your code like that :
总而言之，您可以像这样构建代码：
public class Taquin {
private byte[][] state = new byte[3][3];
public Taquin(String s) { ... }
public List<Taquin> successors() { ... }
public boolean isSolvable(Taquin goal) { ... }
//Necessary to use the Set !////////////
public int hashCode() { ... }
public boolean equals(Object o) { ... }
public String toString() { ...state }
////////////////////////////////////////
public void solve(Taquin goal) {
if (isSolvable(goal)) {
Deque<Taquin> open = new ArrayDeque<>();
Set<Taquin> closed = new HashSet<>();
closed.add(this);
open.add(this);
Taquin current = this;
//if isSolvable is correct you should never encounter open.isEmpty() but for safety, test it
while (!current.equals(goal) && !open.isEmpty()) {
current = open.pop();
System.out.println(current);
for (Taquin succ : current.successors())
//we only add to the open list the elements which were never "seen"
if (closed.add(succ))
open.add(succ);
}
System.out.println("Success");
} else
System.out.println("No solution");
}
}
This has the advantage of being generic for any kind of search in a graph. If you wanted to solve another puzzle, you would just modify the method I didn't implement (which are actually part of a Node interface). If you wanted to change the algorithm for example A star which is often used for the 8-puzzle, you would just change the solve method. I hope this sample of code will help you.
这具有适用于图中任何类型搜索的通用性的优点。如果你想解决另一个难题，你只需修改我没有实现的方法（它们实际上是 Node 接口的一部分）。如果您想更改算法，例如经常用于 8 拼图的 A 星，您只需更改求解方法。我希望这个代码示例对你有所帮助。
回答by Pablo R. Mier
I would suggest you to use the Hipster libraryto solve the 8-puzzle easily, using BFS, DFS, A*, IDA* etc. There is a full example here(it may help you to design your search strategy).
我建议你使用Hipster 库来轻松解决 8-puzzle，使用 BFS、DFS、A*、IDA* 等。 这里有一个完整的例子（它可以帮助你设计你的搜索策略）。
If you are interested, the basic steps to solve the problem are first define the functions that allow you to traverse the state-space search problem and then pick up one algorithm to search over the state-space problem. In order to create a search problem, you can use the ProblemBuilderclass:
如果您有兴趣，解决问题的基本步骤是首先定义允许您遍历状态空间搜索问题的函数，然后选择一种算法来搜索状态空间问题。为了创建搜索问题，您可以使用ProblemBuilder该类：
SearchProblem p =
ProblemBuilder.create()
.initialState(Arrays.asList(5,4,0,7,2,6,8,1,3))
.defineProblemWithExplicitActions()
.useActionFunction(new ActionFunction<Action, List<Integer>>() {
@Override
public Iterable<Action> actionsFor(List<Integer> state) {
// Here we compute the valid movements for the state
return validMovementsFor(state);
}
}).useTransitionFunction(new ActionStateTransitionFunction<Action, List<Integer>>() {
@Override
public List<Integer> apply(Action action, List<Integer> state) {
// Here we compute the state that results from doing an action A to the current state
return applyActionToState(action, state);
}
}).useCostFunction(new CostFunction<Action, List<Integer>, Double>() {
@Override
public Double evaluate(Transition<Action, List<Integer>> transition) {
// Every movement has the same cost, 1
return 1d;
}
}).build();
Once you have your problem definition, you can select any algorithm to solve it:
有了问题定义后，您可以选择任何算法来解决它：
System.out.println(Hipster.createDijkstra(p).search(Arrays.asList(0,1,2,3,4,5,6,7,8)));
You can read more details about the 8-puzzle problem and how to solve it with Hipster in this presentation https://speakerdeck.com/pablormier/hipster-an-open-source-java-library-for-heuristic-search
您可以在此演示文稿中阅读有关 8 拼图问题以及如何使用 Hipster 解决它的更多详细信息https://speakerdeck.com/pablormier/hipster-an-open-source-java-library-for-heuristic-search
