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

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

《数据结构、算法与应用 —— 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 1le 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 maxsum_{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_iqquad 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 
#include 

typedef std::pair weightAndRestTotal;
int maxLoad = 0;

void loadAt(const std::vector &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 &weight, int capacityOfBoat)
{
	using namespace std;

	// 构建树
	vector 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 
#include 
#include 
#include 

using namespace Microsoft::VisualStudio::CppUnitTestframework;
using namespace std;
int brute_force(const std::vector& 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 u(0, 100);

			// vector sort
			vector 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& vec, int capacity)
{
	int maxLoad = 0;

	// flag bits num
	int 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;
}

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