39.回溯算法

回溯算法的本质是枚举，有规律 分步骤 的枚举所有解，

每一步有多个岔路口，当发现当前路走不通时，回到上一个路口，换条路继续走。

适用于缺乏规律，或还不了解其规律的搜索场景中。

分治算法实战

八皇后问题

8 * 8 的期盼,放8个棋子(皇后),棋子所在的行列对角线都不能有其他棋子.

八皇后问题要求找到所有满足这种要求的摆放方式.

首先我们知道,8个棋子,必然在8列上,于是我们只需要找到每列的棋子各属于第几行.

把问题划分成 8 个阶段,依次把棋子放在第1 到第8行.

放置的过程中,不停地检索当前放法是否符合要求,

如果满足,则继续跳下一行防止,如果不满足,则换一种放法继续尝试.

回溯算法非常适合递归实现

(后续补充代码,及leetcode题)

0-1背包

经典算法问题,很多场景可以抽象成这个问题模型

这个问题经典解法是 动态规划,

同时也可使用 回溯算法,更为简单但没那么高效.

0-1背包问题有多个变体,这里介绍最基础的.

一个背包总承载重量为Wkg,要存放有n个物体,重量不同不可分割.

要求在不超过总承载重量的情况下,存放尽可能多的物体.

对于每个物体都有两个选择,装或不装, n个物体 2的n次方种装法.

去掉总重量超过Wkg的装法,剩下的就是接近Wkg的.

要穷举出这些装法,把物品的装与不装视为n个阶段,对每个物品穷举

所有情况,当发现已选择的物品重量超过Wkg,就停止继续探测.具体看代码

// 先复制了一波java代码,回头理解了补充上自己的
public int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值
// cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了；
// w背包重量；items表示每个物品的重量；n表示物品个数
// 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数：
// f(0, 0, a, 10, 100)
public void f(int i, int cw, int[] items, int n, int w) {
  if (cw == w || i == n) { // cw==w表示装满了;i==n表示已经考察完所有的物品
    if (cw > maxW) maxW = cw;
    return;
  }
  f(i+1, cw, items, n, w);//当前物品不装进背包
  if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
    f(i+1,cw + items[i], items, n, w);//当前物品装进背包
  }
}

(后续补充代码,及leetcode题)

正则表达式

假设正则表达式中, 只有

‘*’ 匹配 0-任意多个任意字符(与现实不同,现实是前面的字符),

“.” 匹配 0或1 个任意字符(与现实不同,现实是前面的字符).

给一个字符串,再给一个正则表达式,返回字符串与表达式是否匹配.

依次考察正则表达式中每个字符,当不是通配符时,就直接跟字符串进行匹配,

如果相同则继续往下处理,如果不同,则回溯.

遇到通配符时,”*”匹配任意个字符串中的字符,

发现匹配不下去,就回到岔路口,重新选择一种匹配方案,再继续匹配.(这里没看懂)

// 先复制了一波java代码,回头理解了补充上自己的
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] == '*') { // *匹配任意个字符
      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);
      rmatch(ti+1, pj+1, text, tlen);
    } else if (ti < tlen && pattern[pj] == text[ti]) { // 纯字符匹配才行
      rmatch(ti+1, pj+1, text, tlen);
    }
  }
}