回溯算法 | Notes

深度优先搜索利用的是回溯算法思想。
回溯算法大部分情况下都是用来解决广义的搜索问题：从一组可能的解中，选出一个满足要求的解。

回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧，利用剪枝，并不需要穷举搜索所有的情况，从未提高搜索效率。

回溯算法理解

对比贪心算法，在每次面对岔路口的时候，都做出看起来最优的选择，期望这一组选择是最终的最优解。但是贪心算法并不一定能得到最优解。

回溯的处理思想，类似枚举搜索。枚举所有的解，找到满足期望的解。为了有规律的枚举所有可能的解，避免遗漏和重复，把问题求解的过程分为多个阶段。每个阶段都有会面对一个岔路口，先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就退回到上一个岔路口，另选一种走法继续走。

回溯算法应用

八皇后问题¹

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

把这个问题分成8个阶段，依次将8个棋子放到第一行、第二行、第三行…第八行。在放置的过程中，不停地检查当前放法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放法，继续尝试。²

八皇后

//全局变量，下标表示行，值表示queen存在哪一列
int[] result = new int[8];
//记录目前是第几种解法
int count = 0;
//调用：cal8queens(0)
public void cal8queens(int row) {
    //8个棋子都放置好了，打印结果
    if(row == 8) {
        printQueens(result);
        //8行棋子都放好了，已经无法再往下递归
        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;
    int rightup = column + 1;
    //逐行往上考察每一行
    for(int i = row - 1; i >= 0; --i) {
        //1、第i行的column列有棋子么
        if(result[i] == column) return false;
        //2、考察左上对角线，第i行的leftup列有棋子么
        if(leftup >= 0) {
            if(result[i] == leftup) return false;
        }
        //3、考察右上对角线，第i行rightup列有棋子么
        if(rightup < 8) {
            if(result[i] == rightup) return false;
        }
        //行互减的绝对值等于列互减的绝对值
        --leftup;
        ++rightup;
    }
    return true;
}
//打印一个二维矩阵
private void printQueens(int[] result) {
    System.out.println("第" + ++count + "种解法：");
    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();
}

0-1背包
动态规划
回溯算法
一个背包，背包总的承载重量是Wkg。现在有n个物品，每个物品的重量不等，并且不可分割。期望选择几件物品，装载到背包中，在不超过背包所能装载重量的前提下，让背包中物品的总重量最大。

对于每个物品来说，都有两种选择，装进背包或者不装进背包。对于n各物品来说，总的装法就有2ⁿ种，去掉总重量超过Wkg的，从剩下的装法中选择总重量最接近Wkg的。
把物品依次排列，整个问题就分解成了n个阶段，每个阶段对应一个物品怎么选择，先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。

0-1背包

//存储背包中物品总重量的最大值
public int maxW = Integer.MIN_VALUE;
/**
* cw表示当前已经装进去的物品的重量综合；
* i表示考察到哪个物品了；
* w背包重量；
* items表示每个物品的重量；
* n表示物品个数；
* 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，调用方法 f(0,0,a,10,100)
* 借助递归回到上一个状态，装或者不装都只影响递归调用
*/
public void f01(int i, int cw, int[] items, int n, int w) {
        //cw==w表示装满了；i==n表示已考察完所有的物品
        if(cw == w || i == n) {
            if(cw > maxW)
                maxW = cw;
            return;
        }
        //当前物品不装进背包，考虑下一个时（i+1），cw不更新
        f01(i+1,cw,items,n,w);
        if(cw + items[i] <= w) {
            //当前物品装进背包，考虑下一个时（i+1），cw通过入参更新为cw+items[i]
            f01(i+1,cw+items[i],items,n,w);
        }
    }

变体：每个物品重量不同，价值不同，在不超过背包重量的情况下，让背包中的总价值最大。

正则表达式
背景假设，正则表达式中只包含“”和“？”这两种通配符，其中“”匹配任意多个（>=0个）任意字符，“？”匹配另个或者一个任意字符。

依次考察正则表达式中的每个字符，当是非通配符时，就直接跟文本的字符进行匹配，如果相同，则继续往下处理；如果不同，则回溯。
如果遇到特殊字符的时候，也就是岔路口，“*”，先随意的选择一种匹配方案，然后继续考察剩下的字符，如果中途发现无法继续匹配下去，就回溯到岔路口，重新选择一种匹配方案，然后再继续匹配剩下的字符。

正则表达式

public class Pattern {
        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] == '*') {
                //匹配任意个字符0~tlen-ti
                for(int k = 0; k <= tlen-ti; ++k) {
                    rmatch(ti+k,pj+1,text,tlen);
                }
            } else if(pattern[pj] == '?') {
                //匹配0个或者1个字符
                rmatch(ti,pj+1,text,tlen);//0个
                rmatch(ti+1,pj+1,text,tlen);//1个
            } else if(ti < tlen && pattern[pj] == text[ti]) {
                //纯字符匹配
                rmatch(ti+1,pj+1,text,tlen);
            }
        }
    }

回溯算法理解

回溯算法应用

参考