第五章 回溯法

回溯法在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。

算法搜索至解空间树的任一结点时，先判断该节点是否包含问题的解。

• 如果肯定不包含，则跳过对以该结点为根的子树的搜索（剪枝），逐层向其祖先节点回溯;

• 否则，进入该子树，继续按深度优先策略搜索

回溯法的解空间

为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能的解表示为满足某个约束条件的等长向量

X=(x1,x2,...,xn)X = (x_1, x_2, ... , x_n)

其中分量xi(1 <= i <= n)的取值范围是某个有限集合Si={ai1,ai2,...,ain}Si = \{a_{i1}, a_{i2}, ... , a_{in}\}, 所有可能的解向量构成了问题的解空间。

回溯法的思想

回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝 (Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索

回溯法的搜索过程涉及的结点（称为搜索空间)只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：

  • 用约束条件剪去得不到可行解的子树；
  • 用目标函数剪去得不到最优解的子树。

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

回溯法的解题步骤

  • 针对所给问题，定义问题的解空间
  • 确定易于搜索的解空间结构
  • 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
  • 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。
  • 在任何时刻，算法只保存从根结点到当前扩展结点的路径。
  • 如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))O(2^{h(n)})或O(h(n)!)内存 空间。

回溯法：子集树和排列树

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

    n皇后，背包问题

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

    TSP，枚举全排列

image-20240107002826392

n皇后问题

image-20240107004350460 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool judge(int map[],int line,int pos) {
  for(int i = 0;i < line;i++) {
    if(map[i] == pos || abs(map[i] - pos) == abs(i - line)) {
      return false;
    }
  }
  return true;
}

int queen(int map[],int line) {
  if(line == map.size()) {
    return 1;
  } 
  int sum = 0;
  for(int i = 0;i < map.size();i++) {
    if(judge(map,line,i)) {
      // 剪枝
      map[line] = i;
      sum += queen(map,line + 1);
      map[line] = -1; // 记得恢复状态
    }
  }
  return sum;
}

经过剪枝的时间复杂度为O(N!)O(N!)，未剪枝的复杂度为O(NN)O(N^N)

当然，可以设置三个数组保存列、左对角线、右对角线的棋子摆放情况，此时会减少一部分的遍历判断时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool column[N];
bool left[2*N-1];
bool right[2*N-1];
// 默认下标从0开始

int queen(int map[],int line) {
  if(line == map.size()) {
    return 1;
  } 
  int sum = 0;
  for(int i = 0;i < map.size();i++) {
    if(column[i] && left[line + i] && right[line - i + N - 1]) {
      // 剪枝
      map[line] = i;
      column[i] = false; 
      left[line + i] = false; 
      right[line - i + N - 1] = false;
      
      sum += queen(map,line + 1);
      map[line] = -1; 
      column[i] = true; 
      left[line + i] = true; 
      right[line - i + N - 1] = true;
      // 记得恢复状态
    }
  }
  return sum;
}

TSP旅行售货员

旅行商从驻地出发，经过每个需要访问的城市一次且只有一次，并最终返回出发点。
如何安排路线，使旅行总路程最短？

image-20240107195947925 image-20240107200017715 image-20240107200040550

剪枝条件

1

如果当前正在考虑的顶点j与当前路径中的末端结点i没有边相连，即w[i, j]= ∞,则不必搜索j所在分支

5

如果B(i) ≥ bestw， 则停止搜索**x[i]**分支及其下面的层

其中，bestw代表到目前为止，在前面的搜索中，从其它已经搜索过的路径中，找到的最佳完整回路的权和(总长度)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
select[0] = 1;
bestSelect[0] = 1;
currentSum = 0;
bestSum = 0;
// 城市1是第一个选中的
void TSP(int select[],int i) {
	if (i=map.size())  {
  	//已经搜索到叶节点，已经选择了最后1个城市
		if (map(select[n-1], select[n]) != -1 and map(select[n],select[0]) != -1) {
    	// 最后1个城市与前一城市相连、与第1个城市相连，组成1个满足条件的回路
      //比较当前回路与以前最佳回路，看当前回路是否更优
			if (currentSum + map(select[n-1], select[n]) + map(select[n],select[0]) < bestSum) { 
          //当前回路更优，更新最优搜索结果
					bestSum = currentSum + map(select[n-1], select[n]) + map(select[n],select[0]);
        	for (int j = 0;j < n;j++) {
            bestSelect[j]=select[j];
          }
      }
  	}	
  } else {
    // 还没有搜索到叶节点
    for(int j = i;j < n;j++) {
      // 两个剪枝条件
      if (map(select[i-1], select[j]) != -1 and currentSum + map[select[i-1],select[j]] < bestSum) {
        // 当前的j被选中，交换放到i的位置上继续递归，注意当前权值要加上
        swap(select[i],select[j]);
        currentSum += map[select[i-1],select[i]];
        TSP(select,i+1);
        swap(select[i],select[j])
        currentSum -= map[select[i-1],select[i]];
      }
    }
  }
}

时间复杂度为O((n−1)!)O((n-1)!)

image-20240107204803934

装载问题

image-20240107210156479

image-20240107210211906

可以发现，为1的左子树表示装上第一艘船，为0的右子树表示不装上第一艘船

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n = U; // 集装箱总数
int currentSum = 0;
int bestSum = 0;
int weight[n]; // 集装箱的重量
int capacity; // 第一艘船的最大容量
void backtrack(int i) {
  if(i > n) {
    // 到叶子节点
    if(currentSum > bestSum) {
      bestSum = currentSum;
    }
  } else {
    // 集装箱还没装完
    // 当前编号i的集装箱要装入第一艘船，且没超重
    if(currentSum + weight[i] <= capacity) {
      currentSum += weight[i];
      backtrack(i+1);
      currentSum -= weight[i];
    }
    
    // 当前编号i的集装箱不装入第一艘船，不用考虑超重，因为不装重量也不会改变
    backtrack(i+1);
  }
}

当然，对右子树还可以使用剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int n = U; // 集装箱总数
int currentSum = 0;
int bestSum = 0;
int remainSum = sum(weight);// 剩余的集装箱总重量
int weight[n]; // 集装箱的重量
int capacity; // 第一艘船的最大容量
void backtrack(int i) {
  if(i > n) {
    // 到叶子节点,因为右子树也剪枝，上界函数使每次到叶子节点都是最优值
    bestSum = currentSum
  } else {
    // 集装箱还没装完
    // 当前编号i的集装箱要装入第一艘船，且没超重
    remainSum -= weight[i];
    if(currentSum + weight[i] <= capacity) {
      currentSum += weight[i];
      backtrack(i+1);
      currentSum -= weight[i];
    }
    
    if(currentSum + remainSum > bestSum) {
      // 只有当前重量和剩余重量之和大于最优重量时才选择不放这个集装箱
      backtrack(i+1);
    }
    remainSum += weight[i];
  }
}

复杂度分析

由于bestSum可能被更新O(2n)O(2^n)次，改进后算法的计算时间复杂性为O(n2n)O(n2^n)

一般0-1背包问题

image-20240107215557690 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int n = U; // 货物总数
int currentSum = 0;
int currentValue = 0;
int bestValue = 0;
int weight[n]; // 货物的重量
int value[n]; // 货物的价值
int capacity; // 背包的最大容量
int bound(int i) {
  // 计算价值上界
  int remainSum = capacity - currentSum;
  int tempValue = currentValue;
  // 以物品单位价值减序装入物品,直到装不下完整的一个为止
  while(i <= n && w[i] <= remainSum) {
    remainSum -= w[i];
    tempValue += v[i];
    i++;
  }
  
  if(i<=n) {
    tempValue += remainSum * (v[i]/w[i]); 
  }
  return tempValue;
}

void bucket(int i) {
  if(i > n) {
    bestValue = currentValue;
  }
  
  if(currentSum + w[i] <= capacity) {
    currentSum += w[i];
    currentValue += v[i];
    bucket(i+1);
    currentSum -= w[i];
    currentValue -= v[i];
  } 
  
  if(bound(i+1) > bestValue) {
    bucket(i+1);
  }
}

M图着色问题

image-20240107220947322

image-20240107221002581

image-20240107220928165

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool judge(int i) {
  for(int j = 0;j < n;j++) {
    if(map[i][j] == 1 && select[i] == select[j]) {
      // 两个顶点之间有边连通，同时颜色相同
      return false;
    }
  } 
  return true
}
void color(int i) {
  if(i > n) {
    sum++;
  } else {
    for(int j = 1;j < colorNum;j++) {
      select[j] = i;
      if(judge(i)) {
        color(i + 1);
      }
      select[j] = -1;
    }
  }
}

image-20240107221631762

其实这是n皇后的一个改版.

第六章 分支限界

ub=v+(W−w)∗(vi/wi)ub = v+(W - w) * (v_i/w_i)

lb=(Σi=1k−12c[ri][ri−1]+Σri∈Uri行不在路径上的最小元素+Σrj∉Urj行最小两个元素)/2lb = (\Sigma^{k-1}_{i=1}2c[r_i][r_{i-1}] +\Sigma_{r_i\in U}r_i行不在路径上的最小元素+\Sigma_{r_j\notin U}r_j行最小两个元素) /2

自求多福吧，，，