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

  • Post author:
  • Post category:其他


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



一、算法思想

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

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

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

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



二、货箱装载

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

#pragma once
#include <vector>
#include <numeric>
#include <queue>

typedef std::pair<int, int> weightAndRestTotal;
typedef std::pair<int, int> nodeAndCurWeight;

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

	int maxLoad = 0;
	queue<nodeAndCurWeight> 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;
}

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



版权声明:本文为weixin_37950545原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。