-
2021-07-25 22:02:22
实验名称
优先队列式分支限界法求解0-1背包问题。实验目的
优先队列式分支限界法求解0-1背包问题,得到不同规模数据实验的时间对比,并进行时间复杂度分析。实验原理
使用优先队列式的分支限界算法,能准确的找出限定容量背包所能装载的商品的最大价值, 并计算出程序运行所需要的时间。实验步骤
①根据每个物品的重量和价值计算出物品的单价,根据单价将物品进行排序;
②搜索解空间建立二叉树,从根节点开始;
③广度优先遍历二叉树,并用极大堆表示活结点的优先级,选取扩展结点,找出可行解;
④应当检查左儿子结点是否是可行结点(即上界大于当前最优值且加上该物品的重量不超过背包容量),如果是则将它加入到活结点优先队列中,而当前扩展结点的右儿子一定是可行结点,仅当右儿子满足上界约束时才将它加入到活结点优先队列中;
⑤对优先队列进行堆结构的维护,使得堆顶元素依然是优先级最高的结点;
⑥重复②③④步骤直到优先队列为空,输出结果。时间复杂度分析
每一个物品都有放入与不放两种决策,求解上界函数的时间复杂度为O(n),因此遍历解空间树的时间复杂度为O(n^2)。实验心得
通过这次实验,我加深了对分支界限法的学习,同时巩固了随机数据生成方法和文件读写操作的知识。#include <iostream> #include <stdio.h> #include<algorithm> #include <time.h> #include <windows.h> #include<fstream> #include<queue> using namespace std; ifstream ifile; ofstream ofile; int n; double c; double bestp = 0.0;//最优价值best price int bestx[1001];//最优解 struct WP{ int id; double pre; int v; int w; }; WP wp[1001]; double bound(int i,int cw,int cp) { double leftw= c-cw; double b = cp; while(i<=n && wp[i].w<=leftw) { leftw-=wp[i].w; b+=wp[i].v; i++; } if(i<=n) b+=wp[i].pre*leftw; return b; } bool cmp(WP a,WP b) { return a.pre>b.pre; } void init() { ifile>>n>>c; for(int i=1;i<=n;i++) { ifile>>wp[i].w>>wp[i].v; wp[i].pre=wp[i].v*1.0/wp[i].w*1.0; wp[i].id=i; } sort(wp+1,wp+n+1,cmp); bestp=0; } struct Node { int weight; int value; int level; int x[1001]; friend bool operator< (Node a, Node b) { return a.value < b.value; } }; priority_queue<Node> prique; void enPriQueue(Node pnode, int flag) { Node node; node.weight =pnode.weight; node.value = pnode.value; node.level = pnode.level+1; for (int i = 0; i < node.level; i++) node.x[i] = pnode.x[i];//把自己父节点的x转移到自己创建的新的x数组里 node.x[node.level] = flag;//自己结点的x取1还是0,通过传入的flag识别 if(flag==1){ node.value+=wp[node.level].v; node.weight+=wp[node.level].w; } if (node.level == n)//判断是否是叶子结点 { if (node.value > bestp) { for (int j = 1; j < n + 1; j++) bestx[j] = node.x[j];//更新track数组,把叶子结点x数组里记录取不取的值传入track数组中 bestp = node.value; } return; } else { prique.push(node);//不是叶子结点就入队 } return; } int prioritybbnap() { Node liveNode; liveNode.weight = 0; liveNode.value = 0; liveNode.level = 0; liveNode.x[0] = 0;//第一层不表示商品取舍信息 prique.push(liveNode);//把根结点入优先队列 do { if(bound(liveNode.level+1,liveNode.weight,liveNode.value)>bestp) { if (liveNode.weight + wp[liveNode.level].w <= c)//是否能进左子树 enPriQueue(liveNode,1); enPriQueue(liveNode,0);//进入右子树 } liveNode = prique.top();//把队列里value最大的赋值给liveNode prique.pop();//出队--优先级为背包中价值 } while (!prique.empty());//空就停止循环 return 0; } int main() { LARGE_INTEGER frequency; double v,beginoftime,endoftime,dt,t; //10 ifile.close(); ifile.open("10.txt"); cout<<"10 SISE:\n"; init(); QueryPerformanceFrequency(&frequency); v=(double)frequency.QuadPart; QueryPerformanceCounter(&frequency); beginoftime=frequency.QuadPart; prioritybbnap(); QueryPerformanceCounter(&frequency); endoftime=frequency.QuadPart; dt=(double)(endoftime-beginoftime); cout<<bestp; t=dt/v; cout<<endl<<"Time is "<<t*1000<<"ms\n"; //100 ifile.close(); ifile.open("100.txt"); cout<<"100 SISE:\n"; init(); QueryPerformanceFrequency(&frequency); v=(double)frequency.QuadPart; QueryPerformanceCounter(&frequency); beginoftime=frequency.QuadPart; prioritybbnap(); QueryPerformanceCounter(&frequency); endoftime=frequency.QuadPart; dt=(double)(endoftime-beginoftime); cout<<bestp; t=dt/v; cout<<endl<<"Time is "<<t*1000<<"ms\n"; //1000 ifile.close(); ifile.open("1000.txt"); cout<<"1000 SISE:\n"; init(); QueryPerformanceFrequency(&frequency); v=(double)frequency.QuadPart; QueryPerformanceCounter(&frequency); beginoftime=frequency.QuadPart; prioritybbnap(); QueryPerformanceCounter(&frequency); endoftime=frequency.QuadPart; dt=(double)(endoftime-beginoftime); cout<<bestp; t=dt/v; cout<<endl<<"Time is "<<t*1000<<"ms\n"; return 0; }
#include <iostream> #include <time.h> #include <fstream> using namespace std;//RAND_MAX=32767 int w[1000]={0}; int v[1000]={0}; int c,n; int Size[4]={10,100,1000};//文件大小 void print(ofstream &outfile,int n,int c)//输出到文件 { outfile<<n<<" "<<c<<endl; for(int i=0;i<n;i++) { outfile<<w[i]<<' '<<v[i]<<endl; } } int main() { int n=0; //ifstream ofstream out_10("10.txt"),out_100("100.txt"),out_1000("1000.txt");//输入代查找数据; srand(time(NULL));//时间种子 //生成测试文件 for(int i=0;i<Size[0];i++) { w[i]=rand()%10+1;//得到[0,10)内的数 v[i]=rand()%200+1; } print(out_10,Size[0],20); for(int i=0;i<Size[1];i++) { w[i]=rand()%10+1; v[i]=rand()%200+1; } print(out_100,Size[1],20); for(int i=0;i<Size[2];i++) { w[i]=rand()%10+1; v[i]=rand()%200+1; } print(out_1000,Size[2],20); }
更多相关内容 -
优先队列式分支限界法.cpp
2021-12-05 22:15:59优先队列式分支限界法.cpp -
采用优先队列式分枝限界法求解0/1背包问 题.pdf
2020-05-25 17:26:47采用优先队列式分枝限界法求解0/1背包问题,算法设计第五章,描述的很清晰,里面有完整代码,由于害怕你弄混,所以完整运行的代码参考我的博客文章即可 -
优先队列式分支限界法
2021-06-23 23:04:11*类描述:最小堆(队列中元素类型) *参数描述: x,用于记录当前解; s,表示节点在排列树中的层次,从排列树的根节点到该节点的路径为x[0:s], 需要进一步搜索的顶点是x[s+1:n-1]。 cc,表示当前费用, lcost,是...";
cout << v[1];
}
}
/*****************************************************************
* 类描述:最小堆(队列中元素类型)
* 参数描述:
x,用于记录当前解;
s,表示节点在排列树中的层次,从排列树的根节点到该节点的路径为x[0:s],
需要进一步搜索的顶点是x[s+1:n-1]。
cc,表示当前费用,
lcost,是子树费用的下界,
rcost,是x[x:n-1]中顶点最小出边费用和。
*****************************************************************/
class MinHeapNode
{
public:
char name; // 节点的序号
int rcost, // x[s:n-1]中顶点最小出边费用和
lcost, // 子树费用的下界
cc; // 当前费用
int s, // 根节点到当前节点的路径为x[0:s]
*x; // 需要进一步搜索的顶点是x[s+1:n-1]
// 构造节点并递增序号
MinHeapNode()
{
num += 1;
name = num + 'A';
}
// 最小堆中使用下界排序
bool operator<(const MinHeapNode &MH) const
{
return lcost > MH.lcost;
}
// 打印节点信息
void printNode(priority_queue pq)
{
cout << "============== Node: " << name << " ==============" << endl;
cout << "最小出边和(rcost):" << rcost << "\t子树费用的下界(lcost):" << lcost
<< "\t当前费用(cc):" << cc << " \t节点所在层(s):" << s << endl;
cout << "当前解是(x):";
for (int i = 0; i < n - 1; ++i)
cout << x[i] << "-";
cout << x[n - 1] << endl;
// 输出优先级队列
if (!pq.empty())
{
cout << "-- 当前优先队列:";
for (int i = 0; i < pq.size(); ++i)
{
cout << pq.top().name << "(" << pq.top().lcost << ")-";
pq.pop();
}
cout << pq.top().name << "(" << pq.top().lcost << ")" << endl;
}
else
{
cout << "(优先级队列为空)" << endl;
}
cout << "-- 当前最优值(bestC):" << bestC << endl;
}
};
/*****************************************************************
* 算法描述:核心算法
算法开始时创建一个最小堆,表示活节点优先队列。堆中每个节点的lcost
值是优先队列的优先级。接着计算出图中每个顶点的最小费用出边并用Minout记录。
如果所给的有向图中某个顶点没有出边,则该图不可能有回路,算法即告结束。
如果每个顶点都有出边,则根据计算出的Minout作算法初始化。
*****************************************************************/
int BBTSP()
{
priority_queue pq; // 优先级队列
MinHeapNode E; // 最小堆节点
int cc, rcost, MinSum, *MinOut, b;
int i, j;
MinSum = 0; // 最小出边费用和
MinOut = new int[n + 1]; // 计算 MinOut[i] = 顶点i的最小出边费用
for (i = 1; i <= n; i++)
{
MinOut[i] = NoEdge; // 所有的出边初始化为无连接
// 遍历找出 MinOut[i] = 顶点i的最小出边费用
for (j = 1; j <= n; j++)
if (adjMatrix[i][j] != NoEdge && (adjMatrix[i][j] < MinOut[i] || MinOut[i] == NoEdge))
MinOut[i] = adjMatrix[i][j];
// 不存在与这个顶点相连接的边
if (MinOut[i] == NoEdge)
return NoEdge;
MinSum += MinOut[i];
}
// 初始化最小堆
E.s = 0; // 根节点到当前节点的路径为x[0:s]
E.cc = 0; // 当前费用为0
E.rcost = MinSum; // x[s:n-1]中顶点最小出边费用和
E.x = new int[n]; // 需要进一步搜索的顶点是x[s+1:n-1]
// 初始化为顺序搜索
for (i = 0; i < n; i++)
E.x[i] = i + 1;
bestC = NoEdge; // 初始化最优值为 NoEdge
E.printNode(pq);
//搜索排列空间树
while (E.s < n - 1) //非叶节点
{
if (E.s == n - 2) // 当前扩展节点是叶节点的父节点,判断构成的回路是否最优
{
if (adjMatrix[E.x[n - 2]][E.x[n - 1]] != NoEdge && adjMatrix[E.x[n - 1]][1] != NoEdge &&
(E.cc + adjMatrix[E.x[n - 2]][E.x[n - 1]] + adjMatrix[E.x[n - 1]][1] < bestC || bestC == NoEdge))
{ // 如果更优,则更新费用更小的路
cout << "\n||||||||||||||||||||| 到达叶子节点的父节点 ———— 并更新最优解 |||||||||||||||||||||"
<< endl;
E.printNode(pq);
bestC = E.cc + adjMatrix[E.x[n - 2]][E.x[n - 1]] + adjMatrix[E.x[n - 1]][1];
E.cc = bestC;
E.lcost = bestC;
E.s++;
pq.push(E);
}
else
{
cout << "\n||||||||||||||||||||||| 到达叶子节点的父节点 ———— 不更新 |||||||||||||||||||||||"
<< endl;
E.printNode(pq);
delete[] E.x; // 舍弃需要进一步搜索的节点
}
}
else // 产生当前扩展节点儿子节点
{
cout << "\n*************** 开始一个新节点扩展 ***************\n"
<< endl;
for (i = E.s + 1; i < n; i++)
{ // 广度优先搜索,进行子节点的扩展
MinHeapNode N;
if (adjMatrix[E.x[E.s]][E.x[i]] != NoEdge) // E.x[E.s] 是当前要扩展的父节点,E.x[i] 是被遍历的子节点
{ // 可行儿子节点
cc = E.cc + adjMatrix[E.x[E.s]][E.x[i]]; // 当前费用 = 之前费用 + 新增费用
rcost = E.rcost - MinOut[E.x[E.s]]; // 更新最小出边费用和
b = cc + rcost; // 下界(限界函数)
if (b < bestC || bestC == NoEdge) // 子树可能含最优解 节点插入最小堆
{
N.s = E.s + 1; // 进入下一层
N.cc = cc;
N.lcost = b;
N.rcost = rcost;
N.x = new int[n];
for (j = 0; j < n; j++)
N.x[j] = E.x[j];
// 获得新的路径【换位】
N.x[E.s + 1] = E.x[i];
N.x[i] = E.x[E.s + 1];
pq.push(N); // 加入优先队列
N.printNode(pq);
}
}
}
delete[] E.x; //完成节点扩展
}
if (pq.empty()) // 堆已空
break;
E = pq.top(); // 取下一扩展节点
pq.pop();
}
if (bestC == NoEdge) // 无回路
return NoEdge;
for (i = 0; i < n; i++) // 将最优解复制到v[1:n]
v[i + 1] = E.x[i];
while (pq.size()) // 释放最小堆中所有节点
{
E = pq.top();
pq.pop();
delete[] E.x;
}
return bestC;
}
int main()
{
input();
int res = BBTSP();
printTravel(res);
}
-
利用优先队列式分支限界法解决0-1背包问题
2021-06-07 19:11:210-1背包问题用优先队列式分支限界法实现时, ①问题有2^n种可能解(物品放入/不放入背包); 解空间树为子集树:左子节点(当前物品放入)、右子节点(当前物品不放入) ②约束条件:背包剩余容量 lw ≥ 当前物品...问题描述:
给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包最大承载重量为C。物品是不可分割的,应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
要求:
随机生成物品和背包数据,利用分支限界法求解该问题并形成解题报告。一、问题分析:
0-1背包问题用优先队列式分支限界法实现时,
①问题有2^n种可能解(物品放入/不放入背包);
解空间树为子集树:左子节点(当前物品放入)、右子节点(当前物品不放入)
②约束条件:背包剩余容量 lw ≥ 当前物品重量 w (判断能否生成左孩子结点)
约束剪枝:问题不满足问题约束时停止该分支的搜索
限界条件:当前背包中物品的价值 + 剩余物品装满背包剩余容量的最大价值 (价值上界lv)≥ 之前计算得到的最大价值 bestv (判断能否生成右孩子结点)
限界剪枝:若价值上界<当前搜索的最优解,则从中间节点继续向子孙节点搜索不可能得到一个比当前更优的可行解,不必继续搜索
③优先队列是用最大堆来存储活节点表,活结点的优先级由当前价值+ 剩余物品至能把背包装满的最大价值(假设物品可分割时),装物品先捡着单位重量价值高的装。优先队列式分支限界法是利用存储解空间树的活结点,并且每次弹出一个作为扩展结点,是一种广度优先搜索遍历。二、问题的解决方案
①首先,对要输入的数据进行预处理,将各自物品依其单位重量价值进行从大到小排列。
②再进行广度优先搜索,由CalInf函数计算当前节点处的价值上界,在解空间树的当前扩展结点处,仅当进入右子树时才计算右子树的价值上界CalInf,以判断是否将右子树剪枝。(进入左子树不需要计算,因为其上界与其父节点上界相同)
③结点的优先级定义为:以结点的价值上界作为优先级(由CalInf函数计算出)三、问题求解中遇到的问题
优先队列式分支限界法如何求解价值上界
这里的背包问题,物品只能装或者不装,定义上界函数时,假设背包可以装一部分,即当背包装不下一整件物品时我们只装一部分,所以我们定义的上界函数是当前重量+剩余物品中单位重量价值最大的物品的平均价值*剩余容量。四、优先队列式分支限界法关键技术
运用广度优先搜索遍历找到最优解
优先队列式分支限界法每次在活结点表中选择一个最大价值的节点进行拓展。
从根结点(按单位价值降序排序后第一个物品)开始,以广度优先的方式进行搜索。根节点首先成为活结点,也是当前的扩展结点。一次性生成所有孩子结点,由于子集树中约定左分支上的值为“1”,因此沿着扩展结点的左分支扩展,则代表装入物品;由于子集树中约定右分支上的值为“0”,因此沿着扩展结点的右分支扩展,则代表不装入物品。此时,判断是否满足约束条件和限界条件,如果满足,则将其加入队列中;反之,舍弃。然后再从队列中取出一个元素,作为当前扩展结点,搜索过程队列为空时为止。
算法流程图:
五、伪代码
定义结点和物品结构体
定义排序优先级:
定义队列的优先级:
计算结点上界:
搜索函数:
效果截图
完整代码如下:
```cpp //加载头文件 #include<iostream>//cin cout #include<queue>//队列 #include<cstring>//字符串处理 #include<algorithm>//提供许多泛型算法和函数sort #include<stdlib.h> #include<time.h> //特殊定义 using namespace std;// 用到输入输出的时候就可以省略std::不用每次都写 const int maxn=10;//常变量maxn 最多物品数 //定义结构体 struct object//物品结构体 { double w;//物品重量 double v;//物品价值 double d;//物品单位重量的价值(价值重量比) int id;//物品序号 } a[maxn]; int n,W;//物品种数,背包容量 int bestx[maxn];//最优解 int bestv;//最优总价值 //预处理重排 bool tmp1(object b1,object b2)//物品优先级,以单位价值高的优先 { return b1.d>b2.d; } int init()//初始化 { memset(bestx,0,sizeof(bestx));//初始化最优解bestx数组,全为0 bestv=0;//最优总价值 sort(a+1,a+n+1,tmp1);//数组的降序排序 (按单位价值排序) +1:在数组中先从1位置开始存储 for(int i=1;i<=n;i++) printf("a[%d]=%f ",i,a[i].d); printf("\n"); return 0; } struct node//结点结构体 { double cv,lv;//当前价值,价值上界(注意类型) int lw;//剩余容量 int id;//物品排序后的序号 int x[maxn];//解向量 node() { memset(x,0,sizeof(x));//初始化解向量组x 全为0 lv=0;//价值上界定义为0 } node(int cvv,int lvv,int lww,int idd)//构造函数 { memset(x,0,sizeof(x)); cv=cvv;//当前价值 lv=lvv;//价值上界 lw=lww;//背包剩余容量 id=idd;//物品排序后的序号 } }; struct tmp2//结点优先级,价值上界高的优先级高 { bool operator() (node& n1,node& n2) { return n1.lv<n2.lv; } }; double CalInf(node t)//计算价值上界:当前背包中物品的价值 + 剩余物品装满背包剩余容量的最大价值 { int num=t.id;//获取此节点序号 double maxvalue=t.cv;//获取此节点当前价值 int left=t.lw;//获取背包剩余容量 while(num<=n&&left>=a[num].w)//循环每一个物品 满足条件:剩余容量大于等于此节点物品重量 { left-=a[num].w;//更新剩余容量 (-此节点物品重量) maxvalue+=a[num].v;//更新当前价值 ++num;//更新到下一节点 } if(num<=n&&left>0)//一定要加下标限制 背包剩余容量大于0 maxvalue+=1.0*a[num].v/a[num].w*left; //最大价值 = 当前重量+剩余物品中单位重量价值最大的物品的平均价值*剩余容量 return maxvalue; } void bfs() { priority_queue<node,vector<node>,tmp2> q;//结构体类型的优先队列 int sumv=0; int i; for(i=1; i<=n; ++i) sumv+=a[i].v;//价值上界sumv为所有物品价值之和 q.push(node(0,sumv,W,1));//堆内部放入根结点node(当前价值0,价值上界0,背包剩余容量W,物品排序后的序号1) while(!q.empty()) { node live,lchild,rchild; live=q.top();//将指针置于堆顶部 获取顶部元素 q.pop();//从堆中取出数据 弹出顶部元素 int t=live.id;//当前处理物品的序号 if(t>n||live.lw==0)//到达叶子结点或者没有剩余容量了 { if(live.cv>=bestv)//更新最优解,不加等号的话,第一次计算得到的值不会更新 {//当前价值大于等于最优总价值 for(int i=1; i<=n; ++i) bestx[i]=live.x[i];//最优解=解向量 bestv=live.cv; } continue; } if(live.lv<bestv)//不满足限界条件 价值上界小于当前价值(即最优总价值) ,不再拓展 continue;//限界剪枝:当问题已经搜索到一个可行解时,将其与当前求解状态进行比较,不满足限界条件进行剪枝 if(live.lw>=a[t].w)//满足约束条件,背包剩余容量大于等于物品重量,可以放入背包,可以生成左孩子 { lchild.cv=live.cv+a[t].v;//左孩子结点当前价值 = 当前价值+物品价值 lchild.lw=live.lw-a[t].w;//左孩子结点剩余容量 = 背包剩余容量-物品重量 lchild.id=t+1;//左孩子结点物品排序后的序号=下一物品序号 lchild.lv=CalInf(lchild);//左孩子价值上界 for(int i=1; i<=n; ++i) lchild.x[i]=live.x[i]; lchild.x[t]=1; if(lchild.cv>bestv)//注意要更新最优值 bestv=lchild.cv;//最优价值更新为左孩子当前价值 q.push(lchild); } rchild.cv=live.cv;//右孩子当前价值=当前处理物品价值 rchild.lw=live.lw;//右孩子剩余容量 rchild.id=t+1;//右孩子序号+1 rchild.lv=CalInf(rchild);//右孩子价值上界 if(rchild.lv>=bestv)//(判断价值上界)满足限界条件,不放入背包,可以生成右孩子 { for(int i=1; i<=n; ++i) rchild.x[i]=live.x[i]; rchild.x[t]=0; q.push(rchild);//加入右节点 } } } void output() { cout<<"可装载物品的最大价值为:"<<bestv<<endl; cout<<"装入的物品为:"; for(int i=1; i<=n; ++i) if(bestx[i]) cout<<a[i].id<<" "; cout<<endl; return ; } int main() { cout<<"请输入物品个数:"; cin>>n; cout<<"请输入背包容量:"; cin>>W; /*cout<<"请依次输入物品的重量和价值:";*/ srand((unsigned)time(NULL)); for(int i=1;i<=n;++i)//随机生成价值和重量 { a[i].v=rand()%n+1; a[i].w=rand()%n+1; cout<<"物品"; cout<<i; cout<<"重量"; cout<<a[i].w; cout<<"价值"; cout<<a[i].v<<endl; a[i].d=a[i].v/a[i].w;//物品单位价值 a[i].id=i;//物品序号 cout<<"单位价值"; cout<<a[i].d<<endl; } /*for(int i=1; i<=n; ++i) { cin>>a[i].w>>a[i].v; a[i].d=a[i].v/a[i].w; a[i].id=i; }*/ init(); bfs(); output(); return 0; }
-
装载问题-分支限界法(队列式分支限界法,优先队列式分支限界法)
2020-06-22 22:43:42} 样例测试 数据为上面那个样例 输入 4 12 8 6 2 3 输出 最优装载量为 11 装载的物品为 1 4 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。 活结点x在优先队列中的优先级定义...问题描述
有n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi,且
∑ i = 1 n w i ≤ c 1 + c 2 \sum^n_{i=1}w_i≤c_1+c_2 i=1∑nwi≤c1+c2
问题:
是否有一个合理的装载方案,可将这n个集装箱装上这2艘轮船?如果有,找出一种装载方案。
例如:当n=3, c1=c2=50
(1)若w=[10, 40, 40]
可将集装箱1和集装箱2装上第一艘轮船,而将集装箱3装上第二艘轮船;
(2)如果w=[20, 40, 40]
则无法将这3个集装箱都装上船;
基本思路
已证明,如果一个给定装载问题有解,则采用下面的策略可得到最优装载方案。
- 首先将第一艘轮船尽可能装满;
- 将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集,使该子集中集装箱重量之和最接近c1。由此可知,装载问题等价于以下特殊的0-1背包问题。
队列式分支限界法
- 解装载问题的队列式分支限界法
仅求出所要求的最优值
,稍后进一步构造最优解。 - 首先检测当前扩展结点的左儿子结点是否为可行结点。如果是,则将其加入到活结点队列Q中。
- 然后,将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后,当前扩展结点被舍弃。
- 活结点队列中,队首元素被取出作为当前扩展结点。
- 活结点队列已空,算法终止。
例子
例如 n=4, c1=12, w=[8, 6, 2, 3].
注:叶子结点不会被扩展,因此不用加入到活结点队列当中,此时,只需要检查该叶节点表示的最优解是否优于当前最优解,并实时更新当前最优解。
同层尾部标记:-1
活结点队列:
当取出的元素是-1时,判断当前队列是否为空,如果队列不空,则将尾部标记 -1加入到活节点队列中,代表算法开始处理下一层活节点,即:代表算法开始处理 下一个物品的装载问题(每一层i开始处理第i个物品的装载)。
代码(伪代码)
emplate<class Type> Type MaxLoading(Type w[], Type c, int n) { //初始化 Queue<Type>Q; // 活结点队列 Q.Add(-1); // 同层结点尾部标志 int i=1; //当前扩展结点所处的层 Type Ew=0; //扩展结点处相应的载重量 bestw=0; //搜索子集空间树 while (true) { // 检查左儿子结点 if (Ew + w[i] <= c1) // x[i] = 1,Ew存储当前扩展结点相应的载重量 EnQueue(Q, Ew + w[i], bestw, i, n); //将活结点加入到活结点队列Q中 // 右儿子结点总是可行的,将其加入到Q中 EnQueue(Q, Ew, bestw, i, n); // x[i] = 0 Q.Delete(Ew); // 取下一扩展结点 if (Ew == -1) { // 同层结点尾部 if (Q.IsEmpty( )) return bestw; Q.Add(-1); // 同层结点尾部标志 Q.Delete(Ew); // 取下一扩展结点 i++;} // 进入下一层 } }
算法的改进
算法MaxLoading初始时bestw=0,直到搜索到第一个叶结点才更新bestw。在搜索到第一个
叶结点前,总有Ew+r>bestw, 此时右子树测试不起作用。
为确保右子树成功剪枝,应该在算法每一次进入左子树的时候更新bestw的值。
样例
分析演示
代码改进(伪代码)
while (true) { // 检查左儿子结点 // wt=Ew + w[i]; // 左儿子结点的重量 if (wt<= c) { // 可行结点 if (wt > bestw) bestw = wt; //提前更新bestW,注意更新条件 // 加入活结点队列 if (i <= n) Q.Add(wt); } // 检查右儿子结点 if (Ew + r > bestw && i <= n) //右儿子剪枝 Q.Add(Ew); // 可能含最优解 Q.Delete(Ew); // 取下一扩展结点 if (Ew == -1) { // 同层结点尾部 if (Q.IsEmpty()) return bestw; Q.Add(-1); // 同层结点尾部标志 Q.Delete(Ew); // 取下一扩展结点 i++; r-=w[i];} // 进入下一层 } }
代码
#include <bits/stdc++.h> using namespace std; typedef struct QNode { QNode *parent; int lchild; int weight; }QNode; int n; int c; int bestw; int w[100]; int bestx[100]; void InPut() { scanf("%d %d", &n, &c); for(int i = 1; i <= n; ++i) scanf("%d", &w[i]); // for(int i = 1; i <= n; ++i) // printf("%d ", w[i]); // cout << endl; // printf("输入结束\n"); } //QNode *&bestE 的原因是 首先bestE是个地址, 其次引用为了赋值使用, 后边for循环中用到 void EnQueue(queue<QNode *> &q, int wt, int i, QNode *E, QNode *&bestE, int ch) { if(i == n) { if(wt == bestw) { bestE = E; bestx[n] = ch; return; } } QNode *b; b = new QNode; b->weight = wt; b->lchild = ch; b->parent = E; q.push(b); } int MaxLoading() { queue<QNode *>q; q.push(0); int i = 1; int Ew = 0, r = 0; bestw = 0; for(int j = 2; j <= n; ++j) r += w[j]; QNode *E, *bestE; //bestE的作用是:结束while循环后,bestE指向最优解的叶子节点,然后通过bestE->parent找到装入了哪些物品。 E = new QNode; //E这里作为一个中间量,连接parent和child E = 0; //赋0是因为树的根的值是0,while刚开始的时候其代表root while(true) { int wt = Ew + w[i]; if(wt <= c) { if(wt > bestw) //提前更新bestW,注意更新条件 bestw = wt; EnQueue(q, wt, i, E, bestE, 1); } if(Ew + r >= bestw) //右儿子剪枝 { EnQueue(q, Ew, i, E, bestE, 0); } E = q.front(); q.pop(); if(!E) //如果取得的数是0,代表该处理下一层 { if(q.empty()) //如果队列为空,表示该循环结束了 break; q.push(0); //如果队列中还有数据,表示循环还没结束。在该层的末尾加一个0标识符 E = q.front(); q.pop(); i++; //下一层走起 r -= w[i]; //计算剩余的重量 } Ew = E->weight; //不要忘记更新最新节点的值 } for(int j = n - 1; j > 0; --j) { bestx[j] = bestE->lchild; bestE = bestE->parent; } } void OutPut() { printf("最优装载量为 %d\n", bestw); printf("装载的物品为 \n"); for(int i = 1; i <= n; ++i) if(bestx[i] == 1) printf("%d ", i); } int main() { InPut(); MaxLoading(); OutPut(); }
样例测试
数据为上面那个样例
输入
4 12
8 6 2 3输出
最优装载量为 11
装载的物品为
1 4
优先队列式分支限界法
- 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。
- 活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量Ew(即:当前扩展结点船的载重量Ew)再加上剩余集装箱的重量r之和(即:将上界Ew+r定义为结点优先级)。
- 优先队列中优先级最大的活结点成为下一个扩展结点。
- 子集树中叶结点所相应的载重量与其优先级(上界值)相同,即:该叶子结点的上界值等于当前叶子结点处船的重量Ew。
- 在优先队列式分支限界法中,一旦有一个叶结点成为当前扩展结点,则可以断言该叶结点所相应的解即为最优解。此时可终止算法。
求最优解
- 在优先队列的每一个活结点中,保存从解空间树的根结点到该活结点的路径,在算法确定了达到最优值的叶结点时,就在该叶结点处同时得到相应的最优解。
- 在算法的搜索进程中,保存当前已构造出的部分解空间树,这样在算法确定了达到最优值的叶结点时,可以在解空间树中从该叶结点开始向根结点回溯,构造出相应的最优解。
样例
分析演示
代码
#include <bits/stdc++.h> using namespace std; class MaxHeapQNode { public: MaxHeapQNode *parent; //父节点 int lchild; //左节点:1; 右节点"0 int weight; //总重量 int lev; //层次 }; struct cmp { bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const { return a->weight < b->weight; } }; int n; int c; int bestw; int w[100]; int bestx[100]; void InPut() { scanf("%d %d", &n, &c); for(int i = 1; i <= n; ++i) scanf("%d", &w[i]); } void AddAliveNode(priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp> &q, MaxHeapQNode *E, int wt, int i, int ch) { MaxHeapQNode *p = new MaxHeapQNode; p->parent = E; p->lchild = ch; p->weight = wt; p->lev = i + 1; q.push(p); } void MaxLoading() { priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp > q; // 大顶堆 //定义剩余重量数组r int r[n + 1]; r[n] = 0; for(int j = n - 1; j > 0; --j) r[j] = r[j + 1] + w[j + 1]; int i = 1; MaxHeapQNode *E; int Ew = 0; while(i != n + 1) { if(Ew + w[i] <= c) { AddAliveNode(q, E, Ew + w[i] + r[i], i, 1); } AddAliveNode(q, E, Ew + r[i], i, 0); //取下一节点 E = q.top(); q.pop(); i = E->lev; Ew = E->weight - r[i - 1]; } bestw = Ew; for(int j = n; j > 0; --j) { bestx[j] = E->lchild; E = E->parent; } } void OutPut() { printf("最优装载量为 %d\n", bestw); printf("装载的物品为 \n"); for(int i = 1; i <= n; ++i) if(bestx[i] == 1) printf("%d ", i); } int main() { InPut(); MaxLoading(); OutPut(); }
样例测试
数据为上面那个样例
输入
4 12
8 6 2 3输出
最优装载量为 11
装载的物品为
1 4
-
优先队列式分支限界法解01背包
2019-05-18 19:17:42对于优先队列式分支限界法解01背包,实际上是广搜遍历生成树的过程。因为01背包。背包只有选和不选。所以该生成树是一个二叉树。假设规定左叉标1(代表选择该物品装入背包),右叉标0(代表不选择该物品装入背包)... -
算法设计中关于优先队列式分支限界法解装载问题的代码
2011-01-31 10:46:12分支限界法中的优先队列式分支限界法解装载问题 -
优先队列式_分支限界法_TSP旅行商问题问题
2020-05-28 23:54:55最近真的好久没有更了,会陆续更一些算法问题,有需要的朋友请...采用优先队列式分支限界算法解决该问题。 import java.util.Scanner; public class BBTSP { //排列树结点描述类 private static class HeapNode imple -
优先队列式分支限界法_0-1背包问题
2020-05-29 00:02:19需要的同学请自取哦~欢迎大家与我交流 问题: 0-1背包问题的问题提出是,有n个物品,其中物品i的重量是 ,价值是 ,有一容量为C的背包,要求选择若干物品装入背包,...设 ,使用优先队列式分支限界法求解此问题。 pack -
算法设计四(1)——用优先队列式分支限界法求解0-1背包问题(代码链接)
2021-04-27 21:53:50代码链接: 链接:pan.baidu.com/s/1GAFnDuj7-3x6BNa0uOL9Vg 码:pbfv 算法分析与设计第 4 次实验 ... 用优先队列式分支限界法求解0-1背包问题 ... 通过上机实验,要求掌握优先队列式分支限界... -
优先队列式分支限界法解0-1背包问题
2019-01-13 11:29:06现在采用优先队列式分支限界法来求解; 1. 优先队列中节点i的优先级由该节点的上界函数bound计算出的值upperprofit给出。该上界函数与回溯法中计算方法一致。 子集树中以i结点为跟的子树的任一节点的上界不会超过i... -
优先队列式分支限界法 解装载问题
2018-12-28 15:29:53上一篇我们学习了用队列式分支限界法求解,这一次采用优先队列式分支限界法来求解。 有一批共n个集装箱要装上2艘载重量分别为c1,c2的轮船,其中集装箱i的重量为wi,且要求确定是否有一个合理的装载方案可将这n个集... -
算法设计与分析: 6-18 一般解空间的优先队列式分支限界法
2018-07-24 21:11:516-18 一般解空间的优先队列式分支限界法 问题描述 试设计一个用优先队列式分支限界法搜索一般解空间的函数。该函数的参数包括结点可 行性判定函数和上界函数等必要的函数,并将此函数用于解布线问题。 印刷电路... -
算法实验-优先队列式分支限界法解01背包问题
2020-02-10 11:38:03分支限界法采用的是广度优先搜索,而优先队列采用的是队列里最优的出队,这里可以使用最大堆来实现活接垫优先队列,最大堆以活节点的界值作为优先级。 实验步骤 左子树的解的上界与父节点相同,不用计算。右子树的解... -
优先队列式分支限界法解决旅行售货商问题
2020-06-23 10:41:20优先队列式分支限界法解决旅行售货商问题 问题描述: 某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。 他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。... -
装载问题-分支限界法-优先队列式分支限界法
2018-05-26 15:28:58这里实现优先队列式分支限界法。如果你在用优先队列时用less关键字,发现生成的并不是优先队列 参考https://blog.csdn.net/m0_38015368/article/details/80461938#include <bits/stdc++.h> using ... -
单源最短路径-分支限界法-优先队列式分支限界法-Dijkstra
2018-05-25 11:18:42问题描述:给定一个带权有向图G = (V, E), 其中每...解法:用优先队列式分支限界法,代码核心跟贪心的Dijkstra算法差不多相同,要首先学会使用优先队列的使用。贪心的Dijkstra算法实现见Dijkstra算法实现代码:#incl... -
优先队列式分支限界法 轮船装载问题(集装箱问题)
2020-04-19 15:30:41上一次介绍了集装箱装载问题的队列式分支限界法,本次将分享优先队列式分支限界法解决这个问题的算法。 Problem: 装载问题的问题提出是,有一批共n个集装箱要装上2艘载重量分别为 c1和c2 的轮船,其中集装箱i的重量... -
采用优先队列式分枝限界法求解0/1背包问题-算法设计与分析报告C/C++版
2020-05-25 18:19:12//采用优先队列式分枝限界法求解0/1背包问题 #include <stdio.h> #include <queue> using namespace std; #define MAXN 20 //最多可能物品数 //问题表示 int n=3,W=30; int w[]={0,16,15,15}; /... -
批处理作业调度问题·优先队列式分支限界法·回溯法
2008-11-04 16:40:48c++实现的批处理作业调度问题·优先队列式分支限界法·回溯法包括了FlowShop和make类模板,有测试数据data -
采用优先队列式分支限界法解0-1背包问题
2018-06-26 18:06:58//把队列里value最大的赋值给liveNode prique.pop();//出栈 } while (!prique.empty());//空就停止循环 return 0; } void IO() { int w[20], v[20], c, n, bestValue = 0, i, k = 0, num[20]; FILE *ifp, *... -
优先队列式分支限界法,完成这n个任务在k个机器的最佳调度。
2020-06-05 12:13:07设计一个优先队列式分支限界法,计算完成这n个任务的最佳调度。 给出输入数据。第1行有2个正整数n和k。第2行的n个正整数是完成n个任务需要的时间。 样例输入 7 3 2 14 4 16 6 5 3 样例输出 17 思路 (仅做参考) ... -
用优先队列式分支限界法解决0-1背包问题
2016-04-26 20:28:23用优先队列式分支限界法解决0-1背包问题的算法思想: 1.分支限界法常以广度优先或最小耗费优先(最大效益优先)方式搜索问题的解空间树, 对于0-1背包问题的解空间树是一个颗子集树。 2.在分支限界法中有一个活结点... -
设计一个解n后问题的优先队列式分支限界法
2018-08-03 06:40:32using namespace std; struct HeapNode{ //定义一个结构体用来保存节点...struct cmp{ //自定义比较函数,在优先队列中将会用到,优先级的设定 bool operator()(HeapNode a,HeapNode b) { if(a.row==b.row)r... -
优先队列式分支限界法实现旅行商问题
2021-06-14 12:52:38; margin-right:0">主要问题:随机生成顶点数为n的图,随机指定顶点出发,利用优先队列式分支限界法完成旅行商问题求解。 ; margin-right:0">怎么实现随即指定顶点出发</p> -
队列式和优先队列式分支限界算法的异同点
2015-01-18 12:34:36相同点: 在这两种分支限界算法中每一个活结点都只有一次机会成为扩展节点,一旦活结点成为扩展节点,便一次性产生所有儿子节点,在...有限队列式:按照优先队列中的优先级进行选取子节点成为扩展节点。 -
夜深人静写算法——最大装载问题(优先队列式分支限界法)
2018-12-25 16:42:39(1)解决装载问题的优先队列,将扩展节点的当前装载的重量 (Ew) 加上剩余集装箱的总重量 (r[i]) 作为优先级,从优先级队列中出队列。 (2)为了方便找到最优的分配方法,在每一个节点设置指向父节点的... -
旅行售货员问题-分支限界法(优先队列式分支限界法)
2020-06-28 14:58:18解旅行售货员问题的优先队列式分支限界法用优先队列存储活结点表。 活结点m在优先队列中的优先级定义为:活结点m对应的子树费用下界lcost。 lcost=cc+rcost,其中,cc为当前结点费用,rcost为当前顶点最小出边费用...