搜索技术【广度优先搜索】 - 优先队列式广度优先搜索

搜索技术【广度优先搜索】 - 优先队列式广度优先搜索

优先队列优化以当前节点的上界为优先值，把普通队列改成优先队列，这样就得到了优先队列式分支限界法。

【算法设计】

优先级的定义为活节点代表的部分解所描述的已装入物品的价值上界，上界越大，优先级越高。活节点的价值上界up=活节点的cp+剩余物品装满背包剩余容量的最大价值rp’。

• 约束条件：cw+w [i ]≤W 。
• 限界条件：up=cp+rp’≥bestp。

【举个栗子】

有一个背包和4个物品，每个物品的重量和价值如下图所示，背包的容量W =10。求在不超过背包容量的前提下，把哪些物品放入背包才能获得最大价值。

① 初始化。sumw和sumv分别用来统计所有物品的总重量和总价值。sumw=13，sumv=18，sumw>W ，因此不能全部装完，需要搜索求解。

② 按价值重量比非递增排序。排序后的结果如下图所示。为了程序处理方便，把排序后的数据存储在w []和v []数组中。后面的程序在该数组上操作即可，如下图所示。

③ 创建根节点A。初始化当前放入背包的物品重量cp=0，当前价值上界up=sumv，当前剩余容量rw=W ，当前处理物品序号为1，当前最优值bestp=0。最优解初始化为x []=(0,0,0,0)，创建一个根节点Node(cp,up,rw,id)，标记为A，加入优先队列q 中，如下图所示。

④ 扩展节点A。队头元素A出队，该节点的up≥bestp，满足限界条件，可以扩展。rw=10>w [1]=2，剩余容量大于1号物品的重量，满足约束条件，可以放入背包，生成左孩子，令cp=0+6=6，rw=10-2=8。那么上界怎么算呢？up=cp+rp’=cp+剩余物品装满背包剩余容量的最大价值rp’。剩余容量还有8，可以装入2、3号物品，装入后还有剩余容量2，只能装入4号物品的一部分，装入的价值为剩余容量×单位重量价值，即2×3/5=1.2，rp’=4+5+1.2=10.2，up=cp+rp’= 16.2。

在此需要注意，背包问题属于01背包问题，物品要么装入，要么不装入，是不可以分割的，这里为什么还会有部分装入的问题呢？很多读者看到这里都有这样的疑问，在此不是真的部分装入了，只是算上界而已。令t=2，x [1]=1，解向量更新为x []=(1,0,0,0)，创建新节点B并将其加入q 队列中，更新bestp=6，如下图所示。

再扩展右分支，cp=0，rw=10，剩余容量可以装入2、3号物品，装入后还有剩余容量4，只能装入4号物品的一部分，装入的价值为剩余容量单位重量价值，即4×3/5=2.4，rp’=4+5+2.4= 11.4，up=cp+rp’=11.4，up>bestp，满足限界条件，令t =2，x [1]=0，解向量更新为x []=（0,0,0,0），生成右孩子C并将其加入q 队列中，如下图所示。

⑤ 扩展节点B。队头元素B出队，该节点的up≥bestp，满足限界条件，可以扩展。剩余容量rw=8>w [2]=2，大于2号物品的重量，满足约束条件，令cp=6+4=10，rw=8−2=6，up=cp+rp’=10+5+2×3/5=16.2，t=3，x [2]=1，解向量更新为x []=(1,1,0,0)，生成左孩子D并将其加入q 队列中，更新bestp=10。再扩展右分支，cp=6，rw=8，剩余容量可以装入3号物品，4号物品部分装入，up=cp+rp’=6+5+3×4/5=13.4，up>bestp，满足限界条件，令t =3，x [2]=0，解向量为x []=(1,0,0,0)，生成右孩子E并将其加入q 队列中。

注意：q 为优先队列，其实是用堆实现的，如果不想搞清楚，则只需知道每次up值最大的节点出队即可，如下图所示。

⑥ 扩展节点D。队头元素D出队，该节点的up≥bestp，满足限界条件，可以扩展。剩余容量rw=6>w [3]=4，大于3号物品的重量，满足约束条件，令cp=10+5=15，rw=6−4=2，up=cp+rp’=10+5+2×3/5=16.2，t =4，x [3]=1，解向量更新为x []=(1,1,1,0)，生成左孩子F并将其加入q 队列中，更新bestp=15。再扩展右分支，cp=10，rw=8，剩余容量可以装入4号物品，up=cp+rp’=10+3=13，up

⑦ 扩展节点F。队头元素F出队，该节点的up≥bestp，满足限界条件，可以扩展。剩余容量rw=2

⑧ 扩展节点G。队头元素G出队，该节点的up≥bestp，满足限界条件，可以扩展。t =5，已经处理完毕，bestp=cp=15，是最优解，解向量为x []=(1,1,1,0)。注意：虽然解是(1,1,1,0)，但对应的物品原来的序号是1、4、3。节点G出队。

⑨ 队头元素E出队，该节点的up

⑩ 队头元素C出队，该节点的up

⑪ 队列为空，算法结束。

【算法实现】

① 定义节点和物品结构体。

struct Node{ // 定义节点，记录当前节点的解信息
	int cp; //已装入背包的物品价值
	double up; //价值上界
	
	int rw; //背包剩余容量
	int id; //物品号
	bool x[N];
	Node(){}
	Node(int _cp , double _up , int _rw , int _id){
		cp = _cp;
		up = _up;
		rw = _rw;
		id = _id;
		memset(x , 0 , sizeof(x));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

struct Goods{ //物品结构体
	int weight; // 重量
	int value; //价值
}goods[N];
1
2
3
4

② 定义辅助结构体和排序优先级（从大到小排序）。

struct Object{ // 辅助物品结构体，用于按单位重量价值【价值/重量比】 排序
	int id; //序号
	double d; //单位重量价值
}S[N];

bool cmp(Object a1 , Object a2){ //排序优先级，按照物品的单位重量价值由大到小排序
	return a1.d > a2.d;
}
1
2
3
4
5
6
7
8

③ 定义队列的优先级。

bool operator<(const Node &a , const Node &b){ //队列优先级，up越大越优先
	return a.up < b.up;
}
1
2
3

④ 计算节点的上界

double Bound(Node tnode){
	double maxvalue = tnode.cp; //已装入背包的物品价值
	int t = tnode.id; //排序后序号
	
	double left = tnode.rw; //剩余容量
	while(t <= n && w[t] <= left){
		maxvalue += v[t];
		left -= w[t++];
	}
	if(t <= n){
		maxvalue += double(v[t]) / w[t] * left;
	}
	return maxvalue;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

⑤ 优先队列分支限界法

int priorbfs(){
	
	int t , tcp , trw; //当前处理的物品序号t、当前装入背包的物品价值tcp、当前剩余容量 trw
	double tup; //当前价值上界 tup
	priority_queue<Node> q; //创建第一个优先队列
	q.push(Node(0 , sumv , W, 1)); //初始化，将根节点加入优先队列中
	
	while(!q.empty()){
		Node livenode , lchild , rchild; //定义三个节点型变量
		livenode = q.top(); //取出队头元素作为 当前扩展节点 livenode
		q.pop(); //队头元素出队
		t = livenode.id; //当前处理的物品序号
	
		if(t > n || livenode.rw == 0){
			if(livenode.cp >= bestp){ //更新最优解 和最优值
				for(int i = 1 ; i <= n ; i++){
					bestx[i] = livenode.x[i];
				}
				bestp = livenode.cp;
			}
			continue;
		}
	
		if(livenode.up < bestp){ //如果不满足，则不再扩展
			continue;
		}
		tcp = livenode.cp; //当前背包的 价值
		trw = livenode.rw; //背包的剩余容量
	
		if(trw >= w[t]){
			lchild.cp = tcp + v[t];
			lchild.rw = trw - w[t];
			lchild.id = t + 1;
			tup = Bound(lchild); //计算左孩子的上界
			lchild = Node(lchild.cp , tup , lchild.rw , lchild.id);
			
			for(int i = 1; i <= n ; i++){ //复制以前的解向量
				lchild.x[i] = livenode.x[i];
			}
			lchild.x[t] = true;
			if(lchild.cp > bestp){ //比最优值大 才更新
				bestp = lchild.cp;
			}
			q.push(lchild); //左孩子入队
		}
	
		rchild.cp = tcp;
		rchild.rw = trw;
		rchild.id =  t + 1;
		tup = Bound(rchild); //计算右孩子的上界
		if(tup >= bestp){ //扩展右孩子，满足限界条件，不放入
			rchild = Node(tcp , tup , trw, t + 1);
			for(int i = 1; i <= n ; i++){ //复制以前的解向量
				rchild.x[i] = livenode.x[i];
			}
			rchild.x[t] = false;
			q.push(rchild); //右孩子入队
		}
	}
	return bestp; //返回最优值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

【算法分析】

虽然在算法复杂度数量级上，优先队列的分支限界法算法和普通队列的算法相同，但从图解可以看出，采用优先队列式的分支限界法算法生成的节点数更少，找到最优解的速度更快。