算法--回溯算法

思想

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

过程

1. 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解
2. 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间
3. 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索

示例应用

0-1背包

/**
 * 计算背包最大承载重量
 *
 * @param items 物品重量数组
 * @param n     物品个数
 * @param w     背包可承载重量
 * @return 实际背包承载重量
 */
public int compute(int[] items, int n, int w) {
    // 记录实际背包承载重量
    int[] weight = new int[]{Integer.MIN_VALUE};
    // 记录当前状态是否记录过，如果是，就直接返回
    boolean[][] mem = new boolean[5][10];
    // 递归计算
    compute(items, n, w, weight, mem, 0, 0);
    return weight[0];
}

private void compute2(int[] items, int n, int w, int[] weight, boolean[][] mem, int i, int cw) {
    // cw==w 表示装满了，i==n 表示物品都考察完了
    if (cw == w || i == n) {
        if (cw > weight[0]) {
            weight[0] = cw;
        }
        return;
    }

    // 重复状态，直接返回
    if (mem[i][cw]) {
        return;
    }

    // 记录 (i, cw) 这个状态
    mem[i][cw] = true;

    // 选择不装第 i 个物品
    compute2(items, n, w, weight, mem, i + 1, cw);

    // 如果还没有满
    if (cw + items[i] <= w) {
        // 选择装第 i 个物品
        compute2(items, n, w, weight, mem, i + 1, cw + items[i]);
    }
}

8皇后

8皇后：有一个8x8的棋盘，希望往里放8个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。

/**
 * 下标表示行, 值表示queen存储在哪一列
 */
private int[] result = new int[8];

/**
 * 递归调用，从第一行开始
 *
 * @param row 当前考察的行数
 */
public void cal8queens(int row) {
    // 8 个棋子都放置好了，打印结果
    if (row == 8) {
        printQueens(result);
        return;
    }

    // 每一行都有8种放法
    for (int column = 0; column < 8; ++column) {
        // 有些放法不满足要求
        if (isOk(row, column)) {
            // 第row行的棋子放到了column列
            result[row] = column;
            // 考察下一行
            cal8queens(row + 1);
        }
    }
}

/**
 * 判断row行column列放置是否合适
 */
private boolean isOk(int row, int column) {
    int leftUp = column - 1, rightUp = column + 1;
    // 逐行往上考察每一行
    for (int i = row - 1; i >= 0; --i) {
        // 第i行的 column 列有棋子吗？
        if (result[i] == column) {
            return false;
        }

        // 考察左上对角线：第i行leftUp列有棋子吗？
        if (leftUp >= 0) {
            if (result[i] == leftUp) {
                return false;
            }
        }

        // 考察右上对角线：第i行rightUp列有棋子吗？
        if (rightUp < 8) {
            if (result[i] == rightUp) {
                return false;
            }
        }
        --leftUp;
        ++rightUp;
    }
    return true;
}

/**
 * 打印出一个二维矩阵
 */
private void printQueens(int[] result) {
    for (int row = 0; row < 8; ++row) {
        for (int column = 0; column < 8; ++column) {
            if (result[row] == column) {
                System.out.print("Q ");
            } else {
                System.out.print("* ");
            }
        }
        System.out.println();
    }
    System.out.println();
}

正则表达式

/**
 * 正则表达式：假定正则表达式中只包含“*”和“?”两种通配符
 *
 * @author cdrcool
 */
public class Pattern {
    /**
     * 是否匹配，默认false
     */
    private boolean matched = false;
    /**
     * 正则表达式
     */
    private char[] pattern;
    /**
     * 正则表达式长度
     */
    private int plen;

    public Pattern(char[] pattern, int plen) {
        this.pattern = pattern;
        this.plen = plen;
    }

    public boolean match(char[] text, int tlen) {
        matched = false;
        rmatch(0, 0, text, tlen);
        return matched;
    }

    private void rmatch(int ti, int pj, char[] text, int tlen) {
        // 如果已经匹配了，就不要继续递归了
        if (matched) {
            return;
        }

        // 正则表达式到结尾了
        if (pj == plen) {
            if (ti == tlen) {
                // 文本串也到结尾了
                matched = true;
            }
            return;
        }

        // * 匹配任意个字符
        if (pattern[pj] == '*') {
            for (int k = 0; k <= tlen - ti; ++k) {
                rmatch(ti + k, pj + 1, text, tlen);
            }
        }
        // ? 匹配 0 个或者 1 个字符
        else if (pattern[pj] == '?') {
            rmatch(ti, pj + 1, text, tlen);
            rmatch(ti + 1, pj + 1, text, tlen);
        }
        // 纯字符匹配才行
        else if (ti < tlen && pattern[pj] == text[ti]) {
            rmatch(ti + 1, pj + 1, text, tlen);
        }
    }
}

实际应用

• 深度优先搜索
• 正则表达式匹配