《数据结构、算法与应用 —— C++语言描述》学习笔记 — 回溯法

一、算法思想二、货箱装载1、问题描述2、回溯算法3、实现4、测试代码

一、算法思想

回溯法是搜索问题解的一种系统方法。前面我们做的迷宫老鼠应用使用了这种技术。回溯法首先需要定义问题的一个解空间。这个空间至少包含问题的一个最优解。在迷宫老鼠问题中，我们可以把从入口到出口的所有路径定义为解空间。在n个对象的0/1背包问题中，可以把 2 n 2^n 2n个长度为n的0/1向量集合定义为解空间。这个集合代表着向量x曲志伟0或1的所有可能。

回溯法求解的下一步是组织解空间，使解空间便于搜索。典型的组织方法是图或树。如图所示为 3*3 迷宫的解空间：

一旦确定了解空间的组织方法，这个空间即可安深度优先方式从开始节点进行搜索。在迷宫老鼠问题中，开始节点为入口节点(1,1)。开始节点既是一个活动节点，又是一个扩展节点。从扩展节点我们试着移动到一个新的节点。如果从当前的扩展节点移动到一个新节点，那么这个新节点就变成一个活动节点和新的扩展节点。而原来的扩展节点仍是一个活动节点。如果不能移动到一个新节点，那么当前的扩展节点就死掉，即不再是活动节点。然后我们回到最近的活动节点。这个活动节点变成了新的扩展节点。当我们已经找到了答案或者不再有活动节点时，搜索结束。

个人理解，在一个线程中，最多同时存在一个扩展节点，但是活动节点的个数没有限制。

当问题需要n个元素的一个子集来优化函数时，解空间树称为子集树。对n个对象的0/1背包问题来说，解空间树便是一个子集树。这样一棵树有 2 n 2^n 2n个叶节点，全部节点有 2 n + 1 − 1 2^{n+1}-1 2n+1−1个。因此，访问树中所有节点的每一个算法都要耗时 Ω ( 2 n ) Ω(2^n) Ω(2n)。当问题需要n个元素的一个排列来优化函数时，解空间树称为排列树。这样的树有 n ! n! n!个叶节点。遍历树中所有节点的每一个算法都要耗时 Ω ( n ! ) Ω(n!) Ω(n!)。

确定一个新到达的节点能否导致一个比当前最优解还要好的节，可加速对最优解的搜索过程，如果不能，则移动到该节点的任何一棵子树都是无意义的。这个节点可被立即杀死。用来杀死活动节点的策略被称为界定函数。

综上，回溯方法的步骤如下：

① 定义一个解空间，它包含对问题实例的解。

② 用适合于搜索的方式组织解空间

③ 用深度优先方式搜索解空间，利用界定函数避免进入无解的子空间。

回溯方法的实现有一个有意义的特性：在进行搜索的同时产生解空间。在搜索过程的任何时刻，仅保留从开始节点到当前有效节点的路径。

二、货箱装载

1、问题描述

有两艘船，n个货箱。第一艘船的载重量是 c 1 c_1 c1​，第二艘船的载重量是 c 2 c_2 c2​。 w i w_i wi​是货箱i的重量且 ∑ i = 1 n w i ≤ c 1 + c 2 \sum_{i=1}^{n}w_i \le c_1+c_2 ∑i=1n​wi​≤c1​+c2​。我们希望确定是否有一种办法可以把n个货箱全部装上船。如果有，找出这种办法。

当 ∑ i = 1 n w i = c 1 + c 2 \sum_{i=1}^{n}w_i = c_1+c_2 ∑i=1n​wi​=c1​+c2​时，两艘船的装载问题等价于子集之和问题，即有n个数字，要求找到一个子集（如果存在的话），使它的和为 c 1 c_1 c1​。当 c 1 = c 2 c_1=c_2 c1​=c2​且 ∑ i = 1 n w i = 2 c i \sum_{i=1}^{n}w_i = 2c_i ∑i=1n​wi​=2ci​时。两艘船的装载问题等价于分割问题，即有n个数字 a i a_i ai​，（ 1 ≤ i ≤ n 1\le i \le n 1≤i≤n），要求找到一个子集（如果存在的话），使得子集之和为 ( ∑ i = 1 n a i ) / 2 (\sum_{i=1}^{n}a_i)/2 (∑i=1n​ai​)/2。分割问题和子集问题都是 NP-复杂问题。而且即使问题被限制为整数，它们仍是 NP-复杂问题。

只要有一种方法能够把所有n个货箱装上船，就可以验证一下的装船策略行之有效：（1）尽可能将第一艘船装载到它的载重极限；（2）将剩余货箱装到第二艘船。为了尽可能地将第一艘船装满，需要选择一个货箱的子集，他们的总重量尽可能地接近 c i c_i ci​。这个选择可通过0/1背包问题解决 max ⁡ ∑ i = 1 n w i x i \max\sum_{i=1}^{n}w_ix_i maxi=1∑n​wi​xi​限制条件是 ∑ i = 1 n w i x i ≤ c i x i ∈ { 0 , 1 } , 1 ≤ i ≤ n \sum_{i=1}^{n}w_ix_i \le c_i\qquad x_i∈\{0, 1\}, 1 \le i \le n i=1∑n​wi​xi​≤ci​xi​∈{0,1},1≤i≤n

2、回溯算法

既然要找一个重量的子集，使子集之和尽量接近 c 1 c_1 c1​，那么可以使用一个子集空间，并将其组织成一棵二叉树。用深度优先搜索方式搜索子空间以求最优解。用界定函数防止无解节点的扩张。如果Z是树中j+1层的一个节点，那么从根到Z的路径便定义了 x i x_i xi​的值。使用这些值定义cw为 ∑ ( w i x i ) \sum(w_ix_i) ∑(wi​xi​)。

3、实现

这里我们保存在树节点中的数据为(当前货箱容量，未访问的所有货箱容量之和)。这样我们可以增加一个限制条件：当前货箱容量 + 未访问的所有货箱容量之和 + 已访问的需要可以放到船上的货箱容量之和 > 当前确定的最大容量。这样可以避免不必要的计算。

#pragma once#include <vector>#include <numeric>typedef std::pair<int, int> weightAndRestTotal;int maxLoad = 0;void loadAt(const std::vector<weightAndRestTotal> &solutionTree, int node, int capacity, int curLoad){using namespace std;if (solutionTree[node].first > capacity){return;}int load = curLoad + solutionTree[node].first;if (load > maxLoad){maxLoad = load;}else if (solutionTree[node].second + load <= maxLoad){return;}if (node * 2 + 1 >= solutionTree.size()){return;}loadAt(solutionTree, node * 2 + 1, capacity - solutionTree[node].first, curLoad + solutionTree[node].first);loadAt(solutionTree, node * 2 + 2, capacity - solutionTree[node].first, curLoad + solutionTree[node].first);}int maxLoading(const std::vector<int> &weight, int capacityOfBoat){using namespace std;// 构建树vector<weightAndRestTotal> solutionTree;int totalWeight = accumulate(weight.begin(), weight.end(), 0);solutionTree.push_back(make_pair(0, totalWeight));int num = 1;for (int i = 1; i < weight.size() + 1; ++i){totalWeight -= weight[i - 1];num *= 2;for (int j = 0; j < num; ++j){if (j % 2 == 0){solutionTree.push_back(make_pair(0, totalWeight));}else{solutionTree.push_back(make_pair(weight[i - 1], totalWeight));}}}loadAt(solutionTree, 0, capacityOfBoat, 0);return maxLoad;}

4、测试代码

我们使用暴力求解与上述算法的结果进行比较：

#include "CppUnitTest.h"#include "../../Algorithm/backtrackingMmethod/maxLoading.h"#include <vector>#include <random>#include <cmath>#include <numeric>using namespace Microsoft::VisualStudio::CppUnitTestFramework;using namespace std;int brute_force(const std::vector<int>& vec, int capacity);namespace MaxLoading{TEST_CLASS(MaxLoading){const int containerNum = 5;public:TEST_METHOD(Test){default_random_engine e(time(0));//default_random_engine e;uniform_int_distribution<unsigned int> u(0, 100);// vector sortvector<int> vec(containerNum);for (size_t i = 0; i < containerNum; ++i){vec[i] = u(e);}int capacity = int(u.max() * containerNum * 0.3);int load = maxLoading(vec, capacity);int expected = brute_force(vec, capacity);Assert::IsTrue(expected == load);}};}int brute_force(const std::vector<int>& vec, int capacity){int maxLoad = 0;// flag bits numint num = vec.size();unsigned int cond = 1;while (num > 0){cond *= 2;num--;}for (unsigned int i = 0; i < cond; ++i){int load = 0;for (int j = 0; j < vec.size(); ++j){if ((i >> j) & 0x1){load += vec[j];}if (load > maxLoad && load <= capacity){maxLoad = load;}}}return maxLoad;}

这么来看，回溯法的使用只是方便了解空间的搜索，减少一些不必要的解计算，并不能从本质上减少算法需要的复杂度。