《数据结构、算法与应用 —— C++语言描述》学习笔记 — 分支定界

《数据结构、算法与应用 —— C++语言描述》学习笔记 — 分支定界

《数据结构、算法与应用 —— C++语言描述》学习笔记 — 分支定界

• 一、算法思想
• 二、货箱装载

一、算法思想

分支定界是一种系统地搜索解空间的方法。它与回溯发的主要区别在于扩展节点的扩充方式。每个活动节点仅有一次机会变成扩展节点。当一个节点变为扩展节点时，从该节点移动一步即可到达的节点是生成的新节点。在省城的节点中，那些不可能导出最优可行解的节点被舍弃，剩余节点加入活动节点列表，然后从表中选择下一个节点作为下一个扩展节点。将选择的节点从表中删除，然后扩展。这种扩展股哟成一直持续到一个解找到了或活动表称为空表。

有两种常用的方法可以用来选择下一个扩展节点：

• FIFO
• 最小耗费或最大收益法

回想我们前面解决迷宫老鼠问题，如果我们修改为：使用队列保存所有活动节点；每扩展一个节点，就将其所有可用的相邻接点加入队列中。我们就不需要重复将相同的节点变为扩展节点，而只需要处理队列中的节点即可。

二、货箱装载

我们还是以货箱装载为例，对比两种实现：

#pragma once
#include 
#include 
#include 

typedef std::pair weightAndRestTotal;
typedef std::pair nodeAndCurWeight;

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));
			}
		}
	}

	int maxLoad = 0;
	queue nodes;
	nodes.push({0, 0 });
	while (!nodes.empty())
	{
		auto node = nodes.front();
		nodes.pop();

		if (node.first * 2 + 1 >= solutionTree.size())
		{
			continue;
		}

		if (solutionTree[node.first].first + node.second > capacityOfBoat)
		{
			continue;
		}

		int load = node.second + solutionTree[node.first].first;
		if (load > maxLoad)
		{
			maxLoad = load;
		}
		else if (solutionTree[node.first].second + load <= maxLoad)
		{
			continue;
		}

		nodes.push({ node.first * 2 + 1, load });
		nodes.push({ node.first * 2 + 2, load });
	}

	return maxLoad;
}

正如前面所说，二者的区别仅在于解空间的遍历顺序。不过分支定界中，我们可以支持更富有变化的节点扩展策略，如使用按重量排序的优先级队列保存过程中数据等。