最小重量机器设计问题（分支限界法超详细解法）

Seadeer_l

已于 2024-05-24 15:12:17 修改

阅读量4.3k

点赞数 46

分类专栏：算法设计文章标签：算法数据结构剪枝

于 2024-05-19 14:56:07 首次发布

本文链接：https://blog.csdn.net/Seadeer_l/article/details/139042713

版权

算法设计专栏收录该内容

1 篇文章

订阅专栏

最小重量机器设计问题（分支限界法超详细解法）

一、问题描述

设某一机器由 $n$ 个部件组成，每一种部件都可以从 $m$ 个不同的供应商处购得。设 $w_{ij}$ 是从供应商 $j$ 处购得的部件 $i$ 的重量， $c_{ij}$ 是相应的价格。

试设计一个优先队列式的分支限界算法，给出总价格不超过 $d$ 的最小重量机器设计。

二、问题分析

2.1 解空间树

对于这个问题我们首先分析解空间树：

为了方便分析，我们假定一个一个选择零件，每个零件有 $m$ 个选择。在解空间树中，第 $i$ 层的所有节点，表示对第 $i$ 个零件的全部可能选择，一层一层往下，表示对不同零件进行选择，直到达到叶节点表示对所有零件完成选择。完成某个零件的选择后，其下一个零件也有m个选择，因此其子节点有m个，表示下一个零件可以在不同的m个厂商中选择一个。从根节点到某一层节点的路径,记录下了到当前零件为止，前面所有零件的选择方案。解空间树如下图：

在零件选择时，我们关心两个指标，一个是零件价格总和，我们希望其不超过规定成本 $c$ （约束条件），另一个是零件重量总和，我们希望其越小越好（限界条件）。因此对每个节点我们关心的东西有 $current\_cost$ （cc）,和 $current\_weight$ （cw），除此外还要记录基本信息：零件序号 $i$ （也是层号），和零件的厂商序号 $j$ ，最后为了还原最优解，我们需要能还原路径，我们有两种办法：

一是在每个节点使用 $p a t h$ 数组存下迄今为止所有零件选择的序号，到达叶节点后直接输出即为解的选择方案；二是，从叶节点往回遍历，回到根节点，中间每个节点记录了每个零件的选择方案，使用这种方式需要指针记录下父节点。我们选择第二种方式。

注：前者还原路径时只花费 $O (1)$ 时间，但空间开销巨大，有 $n!$ 个节点，每个节点需要 $O (n)$ 空间来储存路径，额外空间开销为 $O (nn!)$ ；后者每个节点只付出O(1)空间代价来记录父节点指针，但时间上需要花费和层数相关的开销 $O (n)$ ，但相对整个算法来说， $O (n)$ 代价并不高。

因此我们的节点结构体定义如下：

struct node
{
	int cw;			//当前重量
	int cc;			//当前花费
	int i;			//零件序号（也是层数） 
	int j;			//厂商序号
	node* parent;	//父母节点
};

解空间树

2.2 分支限界算法思想

在解空间树确定后，接下来说明分支限界算法思想：

分支限界方法很简单，我们首先应该熟悉广度优先算法和最小代价算法（也叫Dijkstra算法）：

广度优先搜索算法 (BFS)

广度优先搜索能够遍历图或树中的节点。BFS从一个起始节点开始，首先访问其所有子节点，然后依次访问这些子节点的子节点，直到遍历完所有节点或找到目标节点。

在树搜索的步骤：
1. 将起始节点放入队列
2. 重复以下步骤，直到队列为空：
  - 从队列中取出一个节点作为当前节点。
  - 将当前节点的所有满足约束条件的子节点放入队列。
特点：
1. 无权图中，BFS可以找到从起始节点到目标节点的最短路径。
2. 依靠队列来实现，在子节点选择时按照进入队列顺序作为优先级遍历。

最小代价算法 (又叫Dijkstra算法)

最小代价算法以贪心策略逐步扩展最短路径，直到找到从起始节点到所有其他节点的最短路径，在BFS的基础上将队列换成优先队列即可实现。

在树搜索的步骤步骤：
1. 将起始节点放入优先队列
2. 重复以下步骤，直到优先队列为空：
  - 从优先队列中取出一个节点作为当前节点。
  - 将当前节点的所有满足约束条件的子节点放入优先队列，并自动根据指定优先函数调整优先级。
特点：
1. 比BFS可以更快找到从起始节点到目标节点的最短路径。
2. 依靠优先队列来实现，在子节点选择时按照优化目标值作为优先级遍历。

分支限界思想

在前二者的基础上，为了减少搜索空间，使用分支限界法来剪去那些没有必要的搜索分支。具体做法是：在将子节点即将加入队列或者优先队列时，除了约束条件判断外，还要额外判断是否满足限界条件，来决定是否将其加入队列。当子节点不满足限界条件时将被忽略，其所在子树也将不在搜索，即为剪枝。

若在BFS的基础上，添加界限函数（剪枝函数），则得到基于队列的分支限界算法，若在最小代价算法的基础上，添加界限函数（剪枝函数），则得到基于优先队列的分支限界算法。我们使用基于优先队列的分枝限界算法。

分支限界法的关键在于设计界限函数（剪枝函数）来忽略那些没有可能得到最优解的分枝，即剪枝。例如，我们求最小重量时，当前可能的最小重量为 $min\_weight$ ，若我们根据剪枝函数算出某一分支的下界 $lower\_bound$ 值大于 $min\_weight$ ，该分支能得到的最小重量一定大于等于其下界，而当下界大于当前最小重量时，说明分支能得到的最小重量大于当前最小重量，那自然我们没有理由再去考虑它，因此直接忽略即可。

2.3 剪枝函数设计

剪枝函数设计时，需要考虑两个因素，一个是界限计算的时间，第二个是计算出的界限值与实际求解目标的接近程度。时间越短，接近程度越近越好。但往往二者是无法同时达到最优的，是相互矛盾的，类似于时间与空间代价的关系。

关于本问题，目的是求出最小重量，因此我们需要设计下界函数 $L B ()$ ，作为一种最简单的方案，我们可以直接使用当前已选择零件的全部重量和作为该分支解的下界，好处是求解时间为 $O (1)$ ，但显然与该分支的真实最小重量接近程度不高。

作为改进，我们在当前已选择零件重量和的基础上，加上剩下未选择零件中最小重量的重量值之和，显然一定不大于真实最小重量，为了减少求解后者的时间，我们先将每一层剩下零件的最小重量和计算出并存在数组中 $l b$ ，那么在 $L B ()$ 函数中直接读取该数组，实现 $O (1)$ 时间复杂度，但第一次计算数组 $l b$ 花费时间为 $O(n^2)$ ，不过可以在数据输入时顺便完成 $l b$ 数组计算。

//计算节点分枝的重量下界
int LB(node n)
{
return n.w + lb[n.i + 1];
}

//lb的初始化，输入时顺便计算
for (int i = 0; i < n; i++)
{
	int minw = INT_MAX;
	for (int j = 0; j < m; j++){
		cin >> w[i][j];
		//记录下第i个零件的最小重量
		if (w[i][j] < minw)
			minw = w[i][j];
	}
	//初始化lb数组
    lb[i] = minw;
}

//计算lb数组
for(int i=n-2;i<0;i++)
    lb[i] = lb[i+1]+lb[i];

算法设计

步骤如下：

将起始节点放入优先队列
重复以下步骤，直到优先队列为空：
- 从优先队列中取出一个节点作为当前节点。
- 若当前节点不是叶节点，将当前节点的所有满足约束条件的子节点放入优先队列，并自动根据指定优先函数调整优先级。
- 若当前节点是叶节点，更新最优解。

注：一定要申请内存，否则临时变量每次循环结束时会被释放，导致节点丢失无法还原路径

void BranchBound()
{
	priority_queue<node> q;//小根堆
	node root(0, 0, -1, 0, NULL);//优先队列初始化,放入根节点
	q.push(root);

	//分枝限界的最小代价搜索
	while (!q.empty()) {
		node* curNode = new node(q.top()); //为每个访问过的节点申请内存，以便后续求解路径  注：见上注
		q.pop();

		//到达叶子节点
		if (curNode->i == n - 1)
		{
			//满足剪枝函数和约束条件
			if (curNode->w < bestw && curNode->c <= d)
			{
				//最小重量更新
				bestw = curNode->w;
				//最优路径更新
				for (node* t = curNode; t->i != -1; t = t->parent)
					bestx[t->i] = t->j + 1;//+1是因为j从0开始计数
			}
		}

		//未到达叶节点
		else
		{
			//子节点加入优先队列


			for (int j = 0; j < m; j++) {
                //临时变量child在每次循环后被释放
				node child(curNode->w + w[curNode->i + 1][j], curNode->c + c[curNode->i + 1][j], curNode->i + 1, j, curNode);
				//约束条件与限界条件，不满足的被忽略剪枝
				if (child.c <= d && LB(child) < bestw)
					q.push(child);
			}
		}
	}

	//输出结果
	if (bestw == INT_MAX){
		cout << "无法满足成本约束条件" << endl;
		return;
	}
	cout << bestw << endl;
	for (int i = 0; i < n; i++)
		cout << bestx[i] << " ";
}

三、测试数据

题解示例：

Input

第一行有3个正整数n、m和d。

接下来的2n行，每行几个数。前n行是c，后n行是w。

Output

将计算的最小重量及每个部件的供应商输出

4
1 3 1

示例 1

**输入文件 **

输出文件:

4
1 2 3 3

示例 2

**输入文件 **

输出文件:

2
1 3

示例 3

**输入文件 **

输出文件:

无法满足成本约束条件

示例 4

**输入文件 **

输出文件 :

3
1 3 2

示例 5

输出文件:

**输出文件 **

9
1 2 2 3

四、代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct node
{
	int w;			//当前重量和
	int c;			//当前花费和
	int i;			//零件序号（也是层数） 
	int j;			//厂商序号
	node* parent;	//父母节点

	//用于赋值
	node(int w,int c, int i,int j,node* p):w(w),c(c),i(i),j(j),parent(p){	}
	//重载运算符<，用于优先队列中排序优先级
	bool operator<(const node& a) const {
		if (w != a.w)
			return w > a.w;//w大，则优先级高
		else if (i != a.i)
			return a.i > i;//w相同则比较层级，倾向于层数更深的节点，这样可以更快到达叶节点
		else
			return j > a.j;//前二者均相同，按厂商序号排
	}

};

class MinWeight
{
private:
	int n;						//零件数
	int m;						//厂商数
	int d;						//成本约束
	int bestw;					//最优重量
	vector<int>lb;				//下界数组，lb[i]表示第i到n零件最小的重量和
	vector<int>bestx;			//解
	vector<vector<int>> w, c;	//重量价值数组

public:
	MinWeight()
	{
		cin >> n >> m >> d;

		bestx.resize(n);
		w.resize(n); c.resize(n);
		for (int i = 0; i < n; i++)
		{
			w[i].resize(m);
			c[i].resize(m);
		}
		
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				cin >> c[i][j];

		//lb的初始化，输入w时顺便计算
		lb.resize(n);
		for (int i = 0; i < n; i++)
		{
			int minw = INT_MAX;
			for (int j = 0; j < m; j++) {
				cin >> w[i][j];
				//记录下第i个零件的最小重量
				if (w[i][j] < minw)
					minw = w[i][j];
			}
			//初始化lb数组
			lb[i] = minw;
		}

		//计算lb数组
		for (int i = n - 2; i >= 0; i--)
			lb[i] = lb[i + 1] + lb[i];

		bestw = INT_MAX;//初始化最小重量
	}

	void BranchBound()
	{
		priority_queue<node> q;//小根堆
		node root(0, 0, -1, 0, NULL);//优先队列初始化,放入根节点
		q.push(root);

		//分枝限界的最小代价搜索
		while (!q.empty()) {
			node* curNode = new node(q.top()); //为每个访问过的节点申请内存，以便后续求解路径  
			q.pop();

			//到达叶子节点
			if (curNode->i == n - 1)
			{
				//满足剪枝函数和约束条件
				if (curNode->w < bestw && curNode->c <= d)
				{
					//最小重量更新
					bestw = curNode->w;
					//最优路径更新
					for (node* t = curNode; t->i != -1; t = t->parent)
						bestx[t->i] = t->j + 1;//+1是因为j从0开始计数
				}
			}

			//未到达叶节点
			else
			{
				//子节点加入优先队列


				for (int j = 0; j < m; j++) {
                    //临时变量不存储
					node child(curNode->w + w[curNode->i + 1][j], curNode->c + c[curNode->i + 1][j], curNode->i + 1, j, curNode);
					//约束条件与限界条件，不满足的被忽略剪枝
					if (child.c <= d && LB(child) < bestw)
						q.push(child);
				}
			}
		}

		//输出结果
		if (bestw == INT_MAX){
			cout << "无法满足成本约束条件" << endl;
			return;
		}
		cout << bestw << endl;
		for (int i = 0; i < n; i++)
			cout << bestx[i] << " ";
	}
	private:
		//计算节点分枝的重量下界
		int LB(node x)
		{
			if (x.i == n - 1)
				return x.w;
			return x.w + lb[x.i + 1];
		}
};


int main()
{
	MinWeight ex;
	ex.BranchBound();
}
···