我使用Java来使用DFS解决8-Puzzle问题。
这就是我想到的:
public static boolean found = false;
public void solveDepthFirst(EightPuzzle currentState, int lastMove){
if(currentState.goal()){
System.out.println(currentState);
found = true;//to stop DFS when a solution is found (even if not optimal)
return;
}
for(int i=0;i<numMoves;++i){
if(found) return;
EightPuzzle e = currentState.move(i);//0 = up, 1 = down, 2 = left, 3= right
if(!e.equals(currentState) && i != lastMove
&& !visitedNodes.contains(e.toString())){
solveDepthFirst(e, i);
}
if(!visitedNodes.contains(currentState.toString())){
visitedNodes.add(currentState.toString());
}
}
}
e.equals(currentState)检查是否可以移动。(如果currentState.move(i)越界,则move()返回相同的状态)
i!=lastMove确保如果你在上一次移动中向右移动,现在就不会向左移动(因为它没有意义)
visitedNodes是已访问节点的哈希集。
堆栈空间不足。当我使用-xs10m将堆栈空间从128k增加到10m时,算法运行良好。然而,我相信还有很多其他的优化可以做。
任何提示都将不胜感激。
首先,您可以创建一个堆栈,而不是递归调用。将lastMove添加到EightPuzzle类中。
这就是你得到的:
// Queue<EightPuzzle> queue = new PriorityQueue<EightPuzzle>();
Stack<EightPuzzle> stack = new Stack<EightPuzzle>();
public void solveDepthFirst() {
while (true) {
EightPuzzle currentState = stack.pop(); // queue.poll();
if (currentState.goal()) {
System.out.println(currentState);
found = true;// to stop DFS when a solution is found (even if
// not
// optimal)
return;
}
for (int i = 0; i < 4; ++i) {
if (found)
return;
EightPuzzle e = currentState.move(i);// 0 = up, 1 = down, 2 =
// left,
// 3= right
if (!e.equals(currentState) && i != currentState.getLastMove()
&& !visitedNodes.contains(e)) {
stack.push(e); // queue.add(e);
}
if (!visitedNodes.contains(currentState.toString())) {
visitedNodes.add(currentState);
}
}
}
}
当使用递归调用而不是迭代设计时,性能会显著下降。
之后,您可以使用PriorityQueue进行进一步优化(但这不是真正的DFS)。要使用的启发式方法可以是曼哈顿距离。这样,要搜索的第一个解决方案最接近目标。它更高效,但不是严格的DFS。
http://docs.oracle.com/javase/1.5.0/docs/api/java/util/PriorityQueue.html
我认为,在继续递归调用之前,通过标记已访问的状态,可以大大加快搜索速度。除此之外,这个谜题没有太多的优化:你只需要尝试所有可能的动作。