一、算法思想
分支定界是一种系统地搜索解空间的方法。它与回溯发的主要区别在于扩展节点的扩充方式。每个活动节点仅有一次机会变成扩展节点。当一个节点变为扩展节点时,从该节点移动一步即可到达的节点是生成的新节点。在省城的节点中,那些不可能导出最优可行解的节点被舍弃,剩余节点加入活动节点列表,然后从表中选择下一个节点作为下一个扩展节点。将选择的节点从表中删除,然后扩展。这种扩展股哟成一直持续到一个解找到了或活动表称为空表。
有两种常用的方法可以用来选择下一个扩展节点:
- 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 版权协议,转载请附上原文出处链接和本声明。