我正在使用Java通过深度优先搜索（DFS）来解决8数码问题。

这是我想到的解决方案：

    public static boolean found = false;        public void solveDepthFirst(EightPuzzle currentState, int lastMove){            if(currentState.goal()){                System.out.println(currentState);                found = true;//找到解决方案时停止DFS（即使不是最优解）                return;            }            for(int i=0;i<numMoves;++i){                if(found) return;                EightPuzzle e = currentState.move(i);//0 = 上，1 = 下，2 = 左，3= 右                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 是一个已访问节点的HashSet。

这个程序会导致堆栈空间不足。当我使用-xss10m将堆栈空间从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;//找到解决方案时停止DFS（即使不是最优解）            return;        }        for (int i = 0; i < 4; ++i) {            if (found)                return;            EightPuzzle e = currentState.move(i);// 0 = 上，1 = 下，2 =                                                    // 左，                                                    // 3= 右            if (!e.equals(currentState) && i != currentState.getLastMove()                    && !visitedNodes.contains(e)) {                stack.push(e); // queue.add(e);            }            if (!visitedNodes.contains(currentState.toString())) {                visitedNodes.add(currentState);            }        }    }}

当你使用递归调用而不是迭代设计时，性能会显著下降。

之后，你可以通过使用优先级队列进一步优化（但这将不再是真正的DFS）。可以使用的启发式方法是曼哈顿距离。这样，最先搜索的解决方案将是最接近目标的。这种方法更有效，但不是严格的DFS。

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/PriorityQueue.html