回溯算法

在许多情况下，回溯算法相当于穷举搜索的巧妙实现，但性能一般不理想。不过情况并不总是如此，即使是如此，在某些情况下它相对于蛮力穷举搜索的工作量也有显著的节省。

博弈-三连游戏棋

回溯算法经常用来实现战略游戏的策略，如西洋跳棋或国际象棋。作为一个例子，我们使用较简单的三连游戏棋来进行说明。

三连游戏棋（tic-tac-toe）：两人轮流在九格方盘上划“+”或“O”，谁最先把三个相同记号排成一条线（横线、直线、斜线）即是胜者。

极小极大策略
较一般的策略是使用一个赋值函数来给一个位置的“好坏”定值。能使计算机获胜的位置可以得到值+1；平局可得到0；使计算机输棋的位置得到值-1。通过考察盘面就能够确定输赢的位置叫做终端位置（terminal position）。

如果一个位置不是终端位置，那么该位置的值通过递归地假设双方最优棋步而确定。这叫做极大极小策略，因为下棋的一方（人）试图使这个位置的值极小，而另一方（计算机）却要使它的值极大。

位置P的后继位置（successor position）是通过从P走一步棋可以到达的任何位置。如果当在某个位置P计算机要走棋，那么它递归地求出所有的后继位置的值。计算机选择具有最大值的一步行棋，这就是P的值。为了得到任意后继位置的值，要递归地求出的所有后继位置的值，然后选择其中最小的值，这个最小值代表行棋的人的一方最赞成的应对。

代码如下：

 public static class MoveInfo{
        public int move;
        public int value;

        public MoveInfo(int m, int v){
            move = m;
            value = v;
        }
    }

    public MoveInfo findComputerMove(){
        int i, responseValue;
        int value, bestMove = 1;
        MoveInfo quickWinInfo;

        if(fullBoard()){
            // 平局
            value = DRAW;
        }else if((quickWinInfo = immediateCompWin()) != null){
            // 计算机赢棋的终端位置
            return quickWinInfo;
        }else {
            // 递归计算所有后继位置的值
            value = COMP_LOSS;
            for(i=1; i<=9; i++){
                if(isEmpty(i)){
                    place(i, COMP); // 标记计算机行棋
                    responseValue = findHumanMove().value; // 递归调用
                    unplace(i); // restore board

                    if(responseValue > value){
                        // update best move
                        value = responseValue;
                        bestMove = i;
                    }
                }
            }
        }

        return new MoveInfo(bestMove, value);
    }

    public MoveInfo findHumanMove(){
        int i, responseValue;
        int value, bestMove = 1;
        MoveInfo quickWinInfo;

        if(fullBoard()){
            value = DRAW;
        }else if((quickWinInfo = immediateHumanWin()) != null){
            return quickWinInfo;
        }else {
            value = COMP_WIN;
            for(i=1; i<=9; i++){
                if(isEmpty(i)){
                    place(i, HUMAN); // 标记人行棋
                    responseValue = findComputerMove().value;
                    unplace(i); // restore board

                    if(responseValue < value){
                        value = responseValue;
                        bestMove = i;
                    }
                }
            }
        }

        return new MoveInfo(bestMove, value);
    }

---

单词搜索

回溯
其实类似N皇后的问题，一步一步走棋，都是此步不通则返回上一状态并继续尝试。

public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited) {
        if (index == word.length() - 1) {
            return board[i][j] == word.charAt(index);
        }
        if (board[i][j] != word.charAt(index)) {
            return false;
        }

        for (int k = 0; k < direct.length; k++) {
            // 选择
            visited[i][j] = true;
            int newI = i + direct[k][0]; // 为了减少撤销选择步骤, 这里定义新的变量
            int newJ = j + direct[k][1]; // 为了减少撤销选择步骤, 这里定义新的变量
            // 回溯
            if (newI >= 0 && newI < board.length && newJ >= 0 && newJ < board[0].length && !visited[newI][newJ] &&
                    dfs(board, word, newI, newJ, index+1, visited)){
                return true;
            }
            // 撤销选择
            visited[i][j] = false;
        }

        return false;
    }

---