《数据结构、算法与应用 —— 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=1nwi≤c1+c2。我们希望确定是否有一种办法可以把n个货箱全部装上船。如果有,找出这种办法。
当 ∑ i = 1 n w i = c 1 + c 2 \sum_{i=1}^{n}w_i = c_1+c_2 ∑i=1nwi=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=1nwi=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=1nai)/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∑nwixi限制条件是 ∑ 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∑nwixi≤cixi∈{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) ∑(wixi)。
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;}
这么来看,回溯法的使用只是方便了解空间的搜索,减少一些不必要的解计算,并不能从本质上减少算法需要的复杂度。