算法设计与分析-回溯法

文章目录

• 回溯法
• • 1 概述
  • • 1.1 问题的解空间
    • 1.2 什么是回溯法
    • 1.3 回溯的算法实现及实例
    • 1.4 回溯法与深度优先遍历的异同
  • 2 求解0/1背包问题
  • • 蛮力法(略)
    • 回溯法
    • • 1.装入背包中物品重量和恰好为W
      • 2.装入背包中物品重量和不超过W
  • 3 求解装载问题
  • • 3.1 求解简单装载问题
    • 3.2 求解复杂装载问题
  • 4 求解子集和问题
  • • 4.1 求子集和问题的解
    • 4.2 判断子集和问题是否存在解
  • 5 求解n皇后问题
  • 6 求解图的m着色问题
  • 7 求解任务分配问题
  • 8 求解活动安排问题
  • 9 求解流水作业调度问题

回溯法 1 概述 1.1 问题的解空间

一个复杂问题的解决方案是由若干个小的决策步骤组成的决策序列，解决一个问题的所有可能的决策序列构成该问题的解空间。

应用回溯法求解问题时，首先应该明确问题的解空间。解空间中满足约束条件的决策序列称为可行解。

一般来说，解任何问题都有一个目标，在约束条件下使目标达到最优的可行解称为该问题的最优解。

问题的解由一个不等长或等长的解向量X={x1，x2，…，xn}组成，其中分量xi表示第i步的操作。

​ 所有满足约束条件的解向量组构成了问题的解空间。

​ 问题的解空间一般用树形式来组织，也称为解空间树或状态空间，树中的每一个结点确定所求解问题的一个问题状态。

​ 树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，以此类推。

例如，以下求集合{1，2，3}的幂集的解空间树：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vuH22Rh2-1654433074177)(https://gimg2.baidu.com/image_search/src=https://www.mshxw.com/skin/sinaskin/image/nopic.gif>

该解空间的每个叶子结点都构成一个解。

求解问题类型：

- 找所有解
- 找最优解

例 题目详情 - 7-1 人狼羊菜过河(*) (pintia.cn)

解空间树通常有两种类型：

子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。

（如上图求集合{1，2，3}的幂集的解空间树）

排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。

​ 注意：问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，然后再在该解空间树中搜索问题的解，而是只存储从根结点到当前结点的路径。

​ 实际上，有些问题的解空间因过于复杂或状态过多难以画出来。

1.2 什么是回溯法

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点（开始结点）出发搜索解空间树。

​ 首先根结点成为活结点（活结点是指自身已生成但其孩子结点没有全部生成的结点），同时也成为当前的扩展结点（扩展结点是指正在产生孩子结点的结点）。

在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。

​ 如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点（死结点是指由根结点到该结点构成的部分解不满足约束条件，或者其子结点已经搜索完毕）。

​ 此时应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。

​ 回溯法以这种方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。

当从状态si搜索到状态si+1后，如果si+1变为死结点，则从状态si+1回退到si，再从si找其他可能的路径，所以回溯法体现出走不通就退回再走的思路。

若用回溯法求问题的所有解时，需要回溯到根结点，且根结点的所有可行的子树都要已被搜索完才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

回溯法搜索解空间时，通常采用两种策略避免无效搜索，提高回溯的搜索效率:

• 用约束函数在扩展结点处剪除不满足约束的子树；
• 用限界函数剪去得不到问题解或最优解的子树。

这两类函数统称为剪枝函数。

归纳起来，用回溯法解题的一般步骤如下：

①针对所给问题，确定问题的解空间树，问题的解空间树应至少包含问题的一个（最优）解。

②确定结点的扩展搜索规则。

③以深度优先方式搜索解空间树，并在搜索过程中可以采用剪枝函数来避免无效搜索。

总结 回溯法 = 深度优先搜索 + 剪枝

1.3 回溯的算法实现及实例

• 递归实现
• 迭代实现

（1）解空间为子集树

例 有一个含n个整数的数组a，所有元素均不相同，设计一个算法求其所有子集（幂集）。

​ 例如，a[]={1，2，3}，所有子集是：{}，{3}，{2}，{2，3}，{1}，{1，3}，{1，2}，{1，2，3}（输出顺序无关）。

​ 解：显然本问题的解空间为子集树，每个元素只有两种扩展，要么选择，要么不选择。

​ 采用深度优先搜索思路。解向量为x[]，x[i]=0表示不选择a[i]，x[i]=1表示选择a[i]。

​ 用i扫描数组a，也就是说问题的初始状态是（i=0，x的元素均为0），目标状态是（i=n，x为一个解）。从状态（i，x）可以扩展出两个状态：

不选择a[i]元素 -> 下一个状态为（i+1，x[i]=0）。
选择a[i]元素 -> 下一个状态为（i+1，x[i]=1）。

面试题 08.04. 幂集 - 力扣（LeetCode）

int[] x;
List> list;

public List> subsets(int[] nums) {
  x = new int[nums.length];
  list = new ArrayList<>();
  dfs(nums, 0);
  return list;
}

public void dfs(int[] a, int n) {
  if (n == x.length) {
    ArrayList integers = new ArrayList<>();
    for (int i = 0; i < x.length; i++) {
      if (x[i] == 1) {
        integers.add(a[i]);
      }
    }
    list.add(integers);
    return;
  }
  x[n] = 1;  //选择a[i]
  dfs(a, n + 1);
  x[n] = 0;  //不选择a[i]
  dfs(a, n + 1);
}

例 设计一个算法在1，2，…，9（顺序不能变）数字之间插入+或-或什么都不插入，使得计算结果总是100的程序，并输出所有的可能性。

​ 例如：1+2+34–5+67–8+9=100。

  
static int N=9;

static void fun(char op[], int sum, int prevadd, int a[], int i) {
  if (i == N)        //扫描完所有位置
  {
    if (sum == 100)      //找到一个解
    {
      System.out.print(a[0]);    //输出解
      for (int j = 1; j < N; j++) {
        if (op[j] != ' ') {
          System.out.print(op[j]);
        }
        System.out.print(a[j]);
      }
      System.out.println("=100");
    }
    return;
  }
  op[i] = '+';      //位置i插入'+'
  sum += a[i];      //计算结果
  fun(op, sum, a[i], a, i + 1);    //继续处理下一个位置
  sum -= a[i];      //回溯
  op[i] = '-';      //位置i插入'-'
  sum -= a[i];      //计算结果
  fun(op, sum, -a[i], a, i + 1);    //继续处理下一个位置
  sum += a[i];      //回溯
  op[i] = ' ';      //位置i插入' '
  sum -= prevadd;      //先减去前面的元素值
  int tmp;        //计算新元素值
  if (prevadd > 0) {
    tmp = prevadd * 10 + a[i];    //如prevadd=5,a[i]=6,结果为56
  } else {
    tmp = prevadd * 10 - a[i];    //如prevadd=-5,a[i]=6,结果为-56
  }
  sum += tmp;        //计算合并结果
  fun(op, sum, tmp, a, i + 1);    //继续处理下一个位置
  sum -= tmp;        //回溯sum
  sum += prevadd;
}

public static void main(String[] args) {
  int[] a = new int[N];
  char[] op = new char[N];//op[i]表示在位置i插入运算符
  for (int i = 0; i < N; i++)    //为a赋值为1,2，...,9
  {
    a[i] = i + 1;
  }
  System.out.println("求解结果");
  fun(op, a[0], a[0], a, 1);  //插入位置i从1开始
}

（2）解空间为排列树

例 有一个含n个整数的数组a，所有元素均不相同，求其所有元素的全排列。

例如，a[]={1，2，3}，得到结果是（1，2，3）、（1，3，2）、（2，3，1）、（2，1，3）、（3，1，2）、（3，2，1）。

46. 全排列 - 力扣（LeetCode）

List> result;
public List> permute(int[] nums) {
  result=new ArrayList<>();
  dfs(nums,nums.length,0);
  return result;
}

void dfs(int[] a,int n,int i){
  if (i==n){
    //得到解
    ArrayList list = new ArrayList<>();
    for (int j = 0; j < a.length; j++) {
      list.add(a[i]);
    }
    result.add(list);
  }else {
    for (int j = i; j < n; j++) {
      swap(a,i,j);
      dfs(a,n,i+1);
      swap(a,i,j);
    }
  }
}
void swap(int[] a,int i,int j){
  int tmp=a[i];
  a[i]=a[j];
  a[j]=tmp;
}

包含重复数字的情况

47. 全排列 II - 力扣（LeetCode）

  List> ans = new LinkedList<>();
  boolean[] visited;

  public List> permuteUnique(int[] nums) {
    LinkedList list = new LinkedList<>();
    visited=new boolean[nums.length];
    Arrays.sort(nums);
    dfs(nums,list,0);
    return ans;
  }

  void dfs(int[] a,LinkedList nums, int n) {
    if (n == a.length) {
      ans.add(new LinkedList<>(nums));
      return;
    }
    for (int i = 0; i < a.length; i++) {
      if (visited[i]||i > 0 && a[i] == a[i-1]&&!visited[i-1]) {
        continue;
      }
      visited[i]=true;
      nums.add(a[i]);
      dfs(a,nums, n + 1);
      nums.removeLast();
      visited[i]=false;
    }
  }

剑指 Offer 38. 字符串的排列 - 力扣（LeetCode）

Set result;

public String[] permutation(String s) {
  result = new HashSet<>();
  char[] chars = new char[s.length()];
  s.getChars(0, s.length(), chars, 0);
  dfs(chars,chars.length-1,0);
  return result.toArray(new String[0]);
}

private void dfs(char[] chars,int n,int i) {
  if (i==n){
    result.add(new String(chars));
  }else {
    for (int j = i; j <=n; j++) {
      swap(chars,i,j);
      dfs(chars,n,i+1);
      swap(chars,i,j);
    }
  }
}
void swap(char[] chars,int i,int j){
  char tmp=chars[i];
  chars[i]=chars[j];
  chars[j]=tmp;
}

//method two
class Solution {
  List res = new LinkedList<>();
  boolean[] visited;

  public String[] permutation(String s) {
    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    visited = new boolean[chars.length];
    dfs(chars,new StringBuilder(),0);
    return res.toArray(new String[res.size()]);
  }

  void dfs(char[] c, StringBuilder builder, int n) {
    if (n == c.length) {
      res.add(builder.toString());
      return;
    }
    for (int i = 0; i < c.length; i++) {
      if (visited[i] || i > 0 && c[i] == c[i - 1] && !visited[i - 1]) {
        continue;
      }
      visited[i] = true;
      builder.append((char) c[i]);
      dfs(c,builder,n+1);
      builder.deleteCharAt(builder.length()-1);
      visited[i]=false;
    }
  }
}

1.4 回溯法与深度优先遍历的异同

相同点：

​ 回溯法在实现上也是遵循深度优先的，即一步一步往前探索，而不像广度优先遍历那样，由近及远一片一片地搜索。

不同点：

​ （1）访问序不同：深度优先遍历目的是“遍历”，本质是无序的。而回溯法目的是“求解过程”，本质是有序的。

​ （2）访问次数的不同：深度优先遍历对已经访问过的顶点不再访问，所有顶点仅访问一次。而回溯法中已经访问过的顶点可能再次访问。

​ （3）剪枝的不同：深度优先遍历不含剪枝，而很多回溯算法采用剪枝条件剪除不必要的分枝以提高效能。

2 求解0/1背包问题

【问题描述】有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定一个容量为W的背包。

​ 设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，而且满足重量限制具有最大的价值。

蛮力法(略) 回溯法 1.装入背包中物品重量和恰好为W

用w[1…n]/v[1…n]存放物品信息，x[1…n]数组存放最优解，其中每个元素取1或0，x[i]=1表示第i个物品放入背包中，x[i]=0表示第i个物品不放入背包中。

这是一个求最优解问题。找到更优解(op,tv) -> (x,maxv)。

  int N;      //n种物品
  int W;      //限制重量
  int w[];    //存放n个物品重量,不用下标0元素
  int val[];    //存放n个物品价值,不用下标0元素
  int best;    
  int[] x;

  void dfs(int[] a, int totalW, int totalV, int i) {
    if (totalW == W && best < totalV) {
      best = totalV;
      return;
    }
    if (i <= N) {
      if (totalW + w[i] <= W) {  //左剪枝
        a[i] = 1;
        dfs(a, totalW + w[i], totalV + val[i], i + 1);
      }
//      if (totalW+rw-w[i]) 加参数rw可右剪枝
      a[i] = 0;
      dfs(a, totalW, totalV, i + 1);
    }
  }

【算法分析】该算法不考虑剪枝时解空间树中有2^{(n+1)-1个结点（剪枝的结点个数不确定），所以最坏情况下算法的时间复杂度为O(2}n)。

2.装入背包中物品重量和不超过W

问题变为求背包中物品重量和不超过W的最大价值的装入方案：

前面左剪枝方式不变。
但右剪枝方式不再有效，改为采用上界函数进行右剪枝。

第i层结点：dfs(a，totalW，totalV，i)

上界函数bound(i)=tv+r
表示沿着该方向选择得到物品的价值上界
r表示剩余物品的总价值

上界函数bound(i)=tv+r
假设当前求出最大价值best，若bound(i)≤best，则右剪枝，否则继续扩展。
显然r越小，bound(i)也越小，剪枝越多，为了构造更小的r，将所有物品以单位重量价值递减排列!。

剪枝：

左剪枝：仅仅扩展tw+w[i]≤W的左孩子结点
右剪枝：仅仅扩展bound(i,tw,tv)>maxv的右孩子结点

2. 01背包问题 - AcWing题库

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

  int N;      //n种物品
  int W;      //限制重量
  int w[];    //存放n个物品重量,不用下标0元素
  int val[];    //存放n个物品价值,不用下标0元素
  int best;
  int[] x;

  public int knapsack(int v, int n, int[][] vw) {
    // write code here
    W = v;
    N = n;
    w = new int[n + 1];
    val = new int[n + 1];
    x = new int[n + 1];
    for (int i = 0; i < vw.length; i++) {
      w[i + 1] = vw[i][0];
      val[i + 1] = vw[i][1];
    }
    dfs(x, 0, 0, 1);
    return best;
  }

  void dfs(int[] a, int totalW, int totalV, int i) {
    if (i > N) {
      if (best < totalV) {
        best = totalV;
      }
    } else {
      if (totalW + w[i] <= W) {  //左剪枝
        a[i] = 1;
        dfs(a, totalW + w[i], totalV + val[i], i + 1);
      }
      if (bound(i, totalW, totalV) > best) {  //右剪枝
        a[i] = 0;
        dfs(a, totalW, totalV, i + 1);
      }
    }
  }

  double bound(int i, int totalW, int totalV)  //求上界
  {
    i++;          //从i+1开始
    while (i <= N && totalW + w[i] <= W)  //若序号为i的物品可以整个放入
    {
      totalW += w[i];
      totalV += val[i];
      i++;
    }
    if (i <= N) {
      return totalV + (W - totalW) * (val[i] /(double) w[i]);  //序号为i的物品不能整个放入
    } else {
      return totalV;
    }
  }

  public static void main(String[] args) {
    Main hs = new Main();
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int v = scanner.nextInt();
    int[][] ints = new int[n][2];
    Item[] items = new Item[n];
    for (int i = 0; i < n; i++) {
      items[i]=new Item();
      items[i].w = scanner.nextInt();
      items[i].v = scanner.nextInt();
      items[i].p = (double) items[i].v / items[i].w;
    }
    //将所有物品以单位重量价值递减排列
    Arrays.sort(items,(o1, o2) -> {return  (o1.p-o2.p)>0?-1:1;});
    for (int i = 0; i < n; i++) {
      ints[i][0]=items[i].w;
      ints[i][1]=items[i].v;
    }
    System.out.println(hs.knapsack(v, n, ints));
  }
}

class Item {
  int w;
  int v;
  double p;
}

3 求解装载问题 3.1 求解简单装载问题

【问题描述】有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1≤i≤n）的重量为wi。不考虑集装箱的体积限制，现要从这些集装箱中选出重量和小于等于W并且尽可能大的若干装上轮船。

​ 例如，n=5，W=10，w={5，2，6，4，3}时，其最佳装载方案是（1，1，0，0，1）或者（0，0，1，1，0），maxw=10。

【问题求解】采用带剪枝的回溯法求解。问题的表示如下：

​ int w[]={0，5，2，6，4，3}; //各集装箱重量，不用下标0的元素

​ int n=5，W=10;

求解的结果表示如下：

​ int maxw=0; //存放最优解的总重量

​ int x[MAXN]; //存放最优解向量

将上述数据设计为全局变量。

求解算法如下：

​ void dfs(int i，int tw，int rw，int op[])

其中参数i表示考虑的集装箱i，tw表示选择的集装箱重量和，rw表示剩余集装箱的重量和（初始时为全部集装箱重量和），op表示一个解，即对应一个装载方案。

最优解：x，maxw

左剪枝：仅仅扩展tw+w[i]≤W的左孩子结点
右剪枝：仅仅扩展tw+rw-w[i]>maxw的右孩子结点

(代码类似01背包)

3.2 求解复杂装载问题

【问题描述】有一批共n个集装箱要装上两艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且w1+w2+…+wn≤c1+c2。

​ 装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这两艘轮船。如果有，找出一种装载方案。

例如：

n=3，c1=c2=50，w={10，40，40}时，可以将集装箱1和2装到第一艘轮船上，而将集装箱3装到第二艘轮船上。
n=3，c1=c2=50，w={20，40，40}，则无法将这3个集装箱都装上轮船。

【问题求解】如果一个给定的复杂装载问题有解，则可以采用如下方式得到一个装载方案：

首先将第一艘轮船尽量装满，然后将剩余的集装箱装在第二艘轮船上。

可以用反证法证明其正确性。
如果这样做得不到一个装载方案，说明该复杂装载问题没有解！

算法思路（输入为w1，w2，…，wn，c1，c2）：

• （1）将尽可能多的集装箱装到第一艘轮船上，得到解向量x。
• （2）累计第一艘轮船装完后剩余的集装箱重量sum。
• （3）若sum<=c2，表示第二艘轮船可以装完，返回true；否则表示第二艘轮船不能装完，返回false。

#include 
#include 
#define MAXN 20		//最多集装箱个数
//问题表示
int w[]={0,10,40,40};		//各集装箱重量,不用下标0的元素
int n=3;
int c1=50,c2=50;
int maxw=0;			//存放第一艘轮船最优解的总重量
int x[MAXN];			//存放第一艘轮船最优解向量

void dfs(int i,int tw,int rw,int op[]) 	//求第一艘轮船的最优解
{  if (i>n)					//找到一个叶子结点
   {  if (tw>maxw)
      {  maxw=tw;				//找到一个满足条件的更优解
         for (int j=1;j<=n;j++)		//复制最优解
            x[j]=op[j];
      }
   }
   else						//尚未找完所有集装箱
   {  if (tw+w[i]<=c1)			//左孩子结点剪枝
      {  op[i]=1;				//选取第i个集装箱
         dfs(i+1,tw+w[i],rw-w[i],op);
      }
      if (tw+rw-w[i]>maxw)			//右孩子结点剪枝
      {  op[i]=0;				//不选取第i个集装箱,回溯
         dfs(i+1,tw,rw-w[i],op);
      }
   }
}

//在第一艘轮船装满后考虑第2艘轮船是否能够装完剩余的集装箱？
bool solve()			//求解复杂装载问题
{  int sum=0;			//累计第一艘轮船装完后剩余的集装箱重量
   for (int j=1;j<=n;j++)
     if (x[j]==0)
        sum+=w[j];
   if (sum<=c2)		//第二艘轮船可以装完
      return true;
   else				//第二艘轮船不能装完
      return false;
}
void main()
{  int op[MAXN];			//存放临时解
   memset(op,0,sizeof(op));
   int rw=0;
   for (int i=1;i<=n;i++)
      rw+=w[i];
   dfs(1,0,rw,op);			//求第一艘轮船的最优解
   printf("求解结果n");
   if (solve())			//输出结果
   {  printf("    最优方案n");
      dispasolution(n);
   }
   else printf("    没有合适的装载方案n");
}

4 求解子集和问题 4.1 求子集和问题的解

【问题描述】给定n个不同的正整数集合w=（w1，w2，…，wn）和一个正整数W，要求找出w的子集s，使该子集中所有元素的和为W。

​ 例如，当n=4时，w=（11，13，24，7），W=31，则满足要求的子集为（11，13，7）和（24，7）。

【问题求解】该问题的解空间树是一棵子集树。

​ 设解向量x=（x1，x2，…，xn），这里是求所有满足目标条件的解，所以一旦搜索到叶子结点（即i>n），如果相应的子集和为W，则输出x解向量。

当搜索到第i（1≤i≤n）的某个结点时，用tw表示选取的整数和，rw表示余下的整数和，即rw=w[i]+…+w[n]（其中包含w[i]），采用的剪枝函数如下：

左剪枝：通过检查当前整数w[i]加入后子集和是否超过W，若是则剪枝，即仅仅扩展满足tw+w[i]≤W的左孩子结点。
右剪枝：如果一个结点满足tw+rw-w[i]

void dfs(int i,int tw,int rw,int x[]) //求解子集和
{
   if (i>n)				//找到一个叶子结点
   {  if (tw==W)			//找到一个满足条件的解,输出它
         dispasolution(x);
   }
   else					//尚未找完所有整数
   {  if (tw+w[i]<=W)			//左孩子结点剪枝
      {  x[i]=1;			//选取第i个整数
         dfs(i+1,tw+w[i],rw-w[i],x);
      }
      if (tw+rw-w[i]>=W)		//右孩子结点剪枝
      {  x[i]=0;			//不选取第i个整数,回溯
         dfs(i+1,tw,rw-w[i],x);
      }
   }
}

4.2 判断子集和问题是否存在解

​ 采用回溯法一般是针对问题存在解时求出相应的一个或多个解，或者最优解。

​ 如果要判断问题是否存在解（一个或者多个），可以将求解函数改为bool类型，当找到任何一个解时返回true，否则返回false。需要注意的是当问题没有解时需要搜索所有解空间。

​ 另外一种方法是通过解个数来判断，如设置全局变量count表示解个数，初始化为0，调用搜索解的回溯算法，当找到一个解时置count++。

​ 最后判断count>0算法成立，若为真，表示存在解，否则表示不存在解。

5 求解n皇后问题

非递归回溯算法：

51. N 皇后 - 力扣（LeetCode）

void queens(int n) {
  int i = 1;    //i表示当前行,也表示放置第i个皇后
  q[i] = 0;    //q[i]是当前列,每个新考虑的皇后初始位置置为0列
  while (i >= 1)  //尚未回溯到头，循环
  {
    q[i]++;    //原位置后移动一列
    while (q[i] <= n && !place(i, q[i]))  //试探一个位置(i,q[i])
    {
      q[i]++;
    }
    if (q[i] <= n)  //为第i个皇后找到了一个合适位置(i,q[i])
    {
      if (i == n)  //若放置了所有皇后,输出一个解
      {
        dispasolution(n);
      } else    //皇后没有放置完
      {
        i++;  //转向下一行,即开始下一个新皇后的放置
        q[i] = 0;  //每个新考虑的皇后初始位置置为0列
      }
    } else {
      i--;  //若第i个皇后找不到合适的位置,则回溯到上一个皇后
    }
  }
}

  //测试(i,j)位置能否放皇后
  boolean place(int i, int j) {
    //第一个位置OK
    if (i == 1) {
      return true;
    }
    int k = 1;
    while (k < i) {
      if (j == q[k] || Math.abs(i - k) == Math.abs(j - q[k])) {
        return false;
      }
      k++;
    }
    return true;
  }

​ 【算法分析】该算法中每个皇后都要试探n列，共n个皇后，其解空间是一棵子集树，不同于前面一般的二叉树子集树，这里每个结点可能有n棵子树。

​ 对应的算法时间复杂度为O(n^n)。

6 求解图的m着色问题

​ 【问题描述】给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的两个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。

​ 【输入格式】第1行有3个正整数n、k和m，表示给定的图G有n个顶点和k条边，m种颜色。顶点编号为1，2，…，n。接下来的k行中，每行有两个正整数u、v，表示图G的一条边（u，v）。

​ 【输出格式】程序运行结束时，将计算出的不同的着色方案数输出。如果不能着色，程序输出-1。

【输入样例】
5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
【输出样例】
48

【问题求解】对于图G，采用邻接矩阵a存储，根据求解问题需要，这里a为一个二维数组（下标0不用），当顶点i与顶点j有边时，置a[i][j]=1，其他情况置a[i][j]=0。

​ 图中的顶点编号为1～n，着色编号为1～m。对于图G中的每一个顶点，可能的着色为1～m，所以对应的解空间是一棵m叉树，高度为n，层次i从1开始。

int[][] a; //邻接矩阵
int[] x;  //存放顶点对应颜色
int n;  //n个顶点
int count; //方案数
int m;  //m种颜色

//判断顶点i是否与相邻顶点存在相同的着色 注意条件i!=j(自己除外)
boolean same(int i) {
  for (int j = 1; j <= n; j++) {
    if (a[i][j] == 1 && x[j] == x[i]&&i!=j) {
      return false;
    }
  }
  return true;
}

void dfs(int i) {
  if (i > n) {
    count++;
  } else {
    for (int j = 1; j <= m; j++) {  //试探每一种着色
      x[i] = j;  //试探着色j
      if (same(i)) { //可以着色j，进入下一个顶点着色
        dfs(i + 1);
      }
      x[i] = 0;    //回溯
    }
  }
}

【算法分析】该算法中每个顶点试探1～m种着色，共n个顶点，对应解空间树是一棵m叉树（子集树），算法的时间复杂度为O(m^n)。

7 求解任务分配问题

【问题描述】有n（n≥1）个任务需要分配给n个人执行，每个任务只能分配给一个人，每个人只能执行一个任务。

​ 第i个人执行第j个任务的成本是c[i][j]（1≤i，j≤n）。求出总成本最小的分配方案。

【问题求解】这里采用回溯法求解。问题表示如下：

int n=4;
int c[MAXN][MAXN]={{0},{0,9,2,7,8},{0,6,4,3,7},
                   {0,5,8,1,8},{0,7,6,9,4} };
    //下标0的元素不用，c[i][j]表示第i个人执行第j个任务的成本

人员	任务1	任务2	任务3	任务4
1	9	2	7	8
2	6	4	3	7
3	5	8	1	8
4	7	6	9	4

考虑为第i个人员分配任务（i从1开始），由于每个任务只能分配给一个人员，为了避免重复分配，设计一个worker布尔数组，初始时均为false，当任务j分配后置worker[j]=true。求解结果表示如下：

  int n = 4;
  int[][] c = {{0, 0, 0, 0, 0}, {0, 9, 2, 7, 8}, {0, 6, 4, 3, 7},
      {0, 5, 8, 1, 8}, {0, 7, 6, 9, 4}};
  int[] x=new int[5];		//临时解
  int cost=0;		//临时解的成本
  int[] bestx=new int[5];	//最优解
  int mincost=Integer.MAX_VALUE;	//最优解的成本
  boolean[] worker=new boolean[5];	//worker[j]表示任务j是否已经分配人员

  void dfs(int i,int cost){
    if (i>n){
      if(cost
        mincost=cost;
        for (int j = 1; j <= n; j++) {
          bestx[j]=x[j];
        }
      }
    }else{
      for (int j = 1; j <=n; j++) {
        if(!worker[j]){
          worker[j]=true;
          x[i]=j;
          dfs(i+1,cost+c[i][j]);
          worker[j]=false;
        }
      }
    }
  }

【算法分析】该算法中每个人员试探1～n个任务，对应解空间树是一棵n叉树（子集树），算法的时间复杂度为O(n^n)

8 求解活动安排问题

【问题描述】假设有一个需要使用某一资源的n个活动所组成的集合S，S={1，…，n}。该资源任何时刻只能被一个活动所占用，活动i有一个开始时间bi和结束时间ei（bi

​ 一旦某个活动开始执行，中间不能被打断，直到其执行完毕。若活动i和活动j有bi≥ej或bj≥ei，则称这两个活动兼容。

​ 设计算法求一种最优活动安排方案，使得所有安排的活动个数最多。

【问题求解】

采用回溯法求解，相当于找到S={1，…，n}的某个排列即调度方案，使得其中所有兼容活动个数最多，显然对应的解空间是一个是排列树。
直接采用排列树递归框架实现，对于每一种调度方案求出所有兼容活动个数，通过比较求出最多活动个数maxsum，对应的调度方案就是最优调度方案bestx，即为本问题的解。

例如，下表的4个活动，若调度方案为（1，2，3，4），求所有兼容活动个数的过程如下：

活动编号	1	2	3	4
开始时间	1	2	4	6
结束时间	3	5	8	10

①置当前活动的结束时间laste=0，所有兼容活动个数sum=0。

②活动1：其开始时间为1，大于等于laste，属于兼容活动，选取它，sum增加1，sum=1，置laste=其结束时间=3。

③活动2：其开始时间为2，小于laste，属于非兼容活动，不选取它。

④活动3：其开始时间为4，大于等于laste，属于兼容活动，选取它，sum增加1，sum=2，置laste=其结束时间=8。

⑤活动4：其开始时间为6，小于laste，属于非兼容活动，不选取它。

⑥该调度方案的所有兼容活动个数sum为2。

求解过程

产生所有排列，每个排列x=(x[1],x[2],…,x[n])对应一种调度方案
计算每种调度方案的兼容活动个数sum
比较求出最大的兼容活动个数maxsum和最优方案bestx

int n;
Action[] a;
int[] x;  //临时解
int[] bestX;  //最优解
int maxSum = 0;
int sum = 0;  //一个调度方案中所有兼容活动个数,初值为0
int laste = 0; //一个调度方案中最后兼容活动的结束时间,初值为0

void dfs(int i) {
  if (i > n) {
    if (sum > maxSum) {
      maxSum = sum;
      for (int j = 1; j <= n; j++) {
        bestX[j] = x[j];
      }
    }
  } else {
    for (int j = i; j <= n; j++) {
      //第i层结点选择活动x[j]
      swap(x, i, j);  //排序树问题递归框架:交换x[i],x[j]
      //保存sum，laste以便回溯
      int sum1 = sum;
      int laste1 = laste;
      if (a[i].b >= laste) {
        laste = a[i].e;
        sum++;
      }
      dfs(i + 1);
      swap(x, i, j);
      sum = sum1;      //回溯
      laste = laste1;
    }
  }
}

void swap(int[] a, int i, int j) {
  int tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}

4167. 活动安排 - AcWing题库

【算法分析】该算法对应解空间树是一棵排列树，与求全排列算法的时间复杂度相同，即为O(n!)。超时！

考虑贪心法

9 求解流水作业调度问题

【问题描述】有n个作业（编号为1～n）要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi（1≤i≤n）。

​ 流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。可以假定任何作业一旦开始加工，就不允许被中断，直到该作业被完成，即非优先调度。

【输入格式】输入包含若干个用例。每个用例第一行是作业数n（1≤n≤1000），接下来n行，每行两个非负整数，第i行的两个整数分别表示在第i个作业在第一台机器和第二台机器上加工时间。以输入n=0结束。

【输出格式】每个用例输出一行，表示采用最优调度所用的总时间，即从第一台机器开始到第二台机器结束的时间。

【输入样例】

​ 4

​ 5 6

​ 12 2

​ 4 14

​ 8 7

​ 0

【输出样例】

​ 33

【问题求解】采用回溯法求解，对应的解空间是一个是排列树，相当于求出n个作业的一种排列使完成时间最少。

作业的编号是1～n。
数组x[]作为解向量即调度方案，即x[i]表示第i步执行的作业编号，初始时数组x的元素分别是1～n。
最优解向量用bestx[]存储。
最优解的最优调度时间用bestf表示。

一种排列（调度方案）的时间计算

f1数组：f1[i]表示第i步执行的作业x[i]在M1上执行完的总时间（含前面作业的执行时间）
f2数组： f2[i]表示第i步执行的作业x[i]在M2上执行完的总时间（含前面作业的执行时间）

​ 由于一个作业总是先在M1上执行后在M2执行，所以f2[n]就是执行全部作业的总时间。

f2[i-1]>f1：需要等待 -> f2[i]=f2[i-1]+b[x[i]]
f2[i-1]≤f1：不需等待 -> f2[i]=f1+b[x[i]]

算法结构

排列树递归回溯框架：在求一个方案的同时求其f2[n]时间！
剪枝：求出第i层的f2[i]即执行作业x[i]后的总时间,若f2[i]≥bestf （bestf为当前求出的执行全部作业的最优总时间），就没有必要从该结点向下扩展了，让其成为死结点，也就是说仅仅扩展满足f2[i]

进一步剪枝

x=(x[1], …
,x[i])为已经选择的作业,它们的b时间和为sum

tot-sum为所有未选择作业的b时间和

该调度方案的时间和≥f2[i]+tot-sum (时间下界：bound(i)表示)

总时间≥bound(i)≥bestf  剪枝
仅仅扩展bound(i) 
//超时 
int n;
int[] x;  //解向量 1~n 排列树
int[] a;  //a车间所需时间
int[] b;  //b车间...
int[] bestX;  //最优解向量
int bestF=Integer.MAX_VALUE; //最优调度时间
int f1;  //f1[i]表示第i步执行的作业x[i]在M1上执行完的总时间（含前面作业的执行时间）
int[] f2;  //f2[i]表示第i步执行的作业x[i]在M2上执行完的总时间（含前面作业的执行时间）

void dfs(int i) {
  if (i > n) {
    if (f2[n] < bestF) {
      bestF = f2[n];
      for (int j = 1; j <= n; j++) {
        bestX[j]=x[j];
      }
    }
  } else {
    for (int j = i; j <=n; j++) {
      swap(x,i,j);
      f1+=a[x[i]];
      f2[i]=Math.max(f1,f2[i-1])+b[x[i]];
      if (bound(i)   //剪枝
        dfs(i+1);
      }
      f1-=a[x[i]];
      swap(x,i,j);
    }
  }
}

void swap(int[] a, int i, int j) {
  int tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}

int bound(int i)   //求结点的下界值
{  int sum=0;
  for (int j=1;j<=i;j++)  //扫描所有选择的作业
    sum+=b[x[j]];    //累计所有选择作业的b时间
  return f2[i]+ Arrays.stream(b).sum()-sum;   //全部n个作业的b时间和为tot
}
 
4170. 加工生产调度 - AcWing题库
 
2751 – Saving Endeavour (poj.org)
 
import java.util.Arrays;
import java.util.Scanner;

public class Main{

  int n;
  int[] x;  //解向量 1~n 排列树
  int[] a;  //a车间所需时间
  int[] b;  //b车间...
  int[] bestX;  //最优解向量
  int bestF = Integer.MAX_VALUE; //最优调度时间
  int f1;  //f1[i]表示第i步执行的作业x[i]在M1上执行完的总时间（含前面作业的执行时间）
  int[] f2;  //f2[i]表示第i步执行的作业x[i]在M2上执行完的总时间（含前面作业的执行时间）


  void dfs(int i) {
    if (i > n) {
      if (f2[n] < bestF) {
        bestF = f2[n];
        for (int j = 1; j <= n; j++) {
          bestX[j] = x[j];
        }
      }
    } else {
      for (int j = i; j <= n; j++) {
        swap(x, i, j);
        f1 += a[x[i]];
        f2[i] = Math.max(f1, f2[i - 1]) + b[x[i]];
        if (bound(i) < bestF) {   //剪枝
          dfs(i + 1);
        }
        f1 -= a[x[i]];
        swap(x, i, j);
      }
    }
  }

  void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
  }

  int bound(int i)      //求结点的下界值
  {
    int sum = 0, c = 0;
    for (int j = 1; j <= i; j++)    //扫描所有选择的作业
    {
      sum += b[x[j]];      //累计所有选择作业的b时间
    }
    for (int j = 0; j < n; j++) {
      c += f2[j + 1];
    }
    return f2[i] + c - sum;    //全部n个作业的b时间和为tot
  }


  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    while (scanner.hasNext()) {
      Main product = new Main();
      int i = scanner.nextInt();
      product.n = i;
      product.a = new int[i + 1];
      product.b = new int[i + 1];
      product.x = new int[i + 1];
      for (int j = 0; j < i; j++) {
        product.x[j + 1] = j + 1;
      }
      product.bestX = new int[i + 1];
      product.f2 = new int[i + 1];
      for (int j = 0; j < i; j++) {
        product.a[j + 1] = scanner.nextInt();
      }
      for (int j = 0; j < i; j++) {
        product.b[j + 1] = scanner.nextInt();
      }
      product.dfs(1);
      System.out.println(product.bestF);
    }
//    for (int j = 0; j < product.n; j++) {
//      System.out.print(product.bestX[j+1]+" ");
//    }
  }
}
 
【算法分析】该算法的解空间树是一棵高度为n的排列树，对应算法的时间复杂度为O(n!)。