广度优先

广度优先搜索，其实就是层次遍历，程序采用队列来实现。

算法思想

从根开始，常以BF或以最小耗费（即最大收益）优先的方式搜索问题的解空间树。首先将根结点加入活结点表，接着从活结点表中取出根结点，使其成为当前扩展结点，一次性生成其所有孩子结点，判断孩子结点是舍弃还是保留，舍弃哪些导致不可行解或导致非最优解的孩子结点，其余的被保留在活结点表中。再从活结点表中取出一个活结点作为当前扩展结点，重复上述扩展过程，直到找到所需的解或活结点表为空时为止。每一个活结点最多只有一次机会成为扩展结点。

算法步骤

算法解题步骤为：
1. 定义问题的解空间。
2. 确定问题的解空间组织结构。
3. 搜索解空间。搜索前要定义判断标准（约束函数或限界函数），如果选优优先队列式分支限界法，则必须确定优先级。

回溯法与分支限界法的异同

1.相同点：

• 均需要先定义问题的解空间，确定的解空间组织结构一般都是树和图；
• 在问题的解空间树上搜索问题解。
• 搜索前均需要确定判断条件，该判断条件用于判断扩展生成的结点是否为可行结点。
• 搜索过程中必须判断扩展生成的结点是否满足判断条件，如果满足则保留该扩展结点，否则舍弃。

2.不同点

• 搜索目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支界限法的求解目标则是找出满足约束条件的一个解，或者是在满足约束条件的解中找出在某种意义下的最优解。
• 搜索的方式不同：回溯法以深度优先搜索方法搜索空间树，分支限界法采用广度优先法或者最小消耗优先搜索解空间树。
• 扩展方式不同：回溯法搜索，扩展结点一次只生成一个孩子结点，而分支限界法则一次生成所有孩子结点。

0-1背包问题

问题分析

前面有，不再重述，

购物车重量W=10。
商品的结构体定义为：

struct Goods{ int weight; int value;} goods[N];

算法设计

1. 定义问题的解空间。问题解空间为{x₁,x₂,…,x_i,…,x_n}，显约束为：x_i=0或者1。
2. 确定解空间的组织结构：子集树。
3. 搜索解空间：
   • 约束条件为：w_ix_i≤W（i=1~n）
   • 限界条件：cp+rp>bestp（cp为当前已经装入购物车的物品的总价值，rp为第t+1~第n种物品的总价值，bestp为最大价值）
4. 搜索过程：从根节点开始，以BFS方式进行搜索。根节点首先成为活结点，也是当前的扩展结点。一次性生成所有孩子结点，由于子集树中约定左分支上的值为“1”，因此沿着扩展结点的左分支扩展，则代表装入物品；右分支的值为“0”，代表不装入物品。此时判断是否满足约束条件和限界条件，如果满足，则将其加入队列中；反之舍弃。然后再从队列中取出一个元素，作为当前扩展结点，搜索过程队列为空时结束。

步骤解释

1. 初始化。sumw=2+5+4+2=13，sumv=6+3+5+4=18，因为sumw>W，所以不能装完，所以需要进行后续的操作。初始化cp=0,rp=sumv，当前剩余重量rw=W；当前处理物品序号为1；当前最优值bestp=0.解向量为x[]=(0,0,0,0)，创建一个根结点Node(cp,rp,rw,id)，标记为A，加入先进先出队列q中。cp为装入购物车的物品价值，rp为剩余物品的总价值，rw为剩余容量，id为物品号，x[]为当前解向量。

//定义结点。每个节点来记录当前的解。
struct Node

{ int cp, rp; //cp背包的物品总价值，rp剩余物品的总价值 int rw; //剩余容量 int id; //物品号 bool x[N];//解向量 Node() {} Node(int _cp, int _rp, int _rw, int _id){ cp = _cp; rp = _rp; rw = _rw; id = _id; memset(x, 0, sizeof(x));//解向量初始化为0 }};

2. 扩展A结点。队头元素A出队，该结点的cp+rp≥bestp，满足限界条件，可以扩展。rw=10>goods[1].weight=2，剩余容量大于1号物品，满足约束条件，可以放入购物车，cp=0+6=6。rp=18-6=12，rw=10-2=8，t=2，x[1]=1，解向量更新为x[]=(1,0,0,0)，生成左孩子B，加入q队列，更新bestp=6。再扩展右分支，cp=0,rp=18-6=12,cp+rp>=bestp=6，满足限界条件，不放入1号物品，cp=0,rp=12,rw=10,t=2,x[1]=0，解向量为x[]=(0,0,0,0)，创建新结点C，加入q队列。如下表所示，X表示为空。

3. 扩展B结点。队头元素B出队，该结点cp+rp>=bestp，满足限界条件，可以扩展。rw=8>goods[2].weight=5，剩余容量大于2号物品重量，满足约束条件，可以放入购物车，cp=6+3=9。rp=12-3=9，rw=8-5=3，t=3，x[2]=1，解向量更新为x[]=(1,1,0,0)，生成左孩子D，加入q队列，更新bestp=9。再扩展右分支，cp=6,rp=12-3=9,cp+rp>=bestp=9，满足限界条件，不放入2号物品，cp=6,rp=9,rw=8,t=3,x[2]=0，解向量为x[]=(1,0,0,0)，创建新结点E，加入q队列。如下表所示。

4. 扩展C结点。队头元素C出队，该结点cp+rp>=bestp，满足限界条件，可以扩展。rw=10>goods[2].weight=5，剩余容量大于2号物品重量，满足约束条件，可以放入购物车，cp=0+3=3。rp=12-3=9，rw=10-5=5，t=3，x[2]=1，解向量更新为x[]=(0,1,0,0)，生成左孩子F，加入q队列。再扩展右分支，cp=0,rp=12-3=9,cp+rp>=bestp=9，满足限界条件，不放入2号物品，cp=6,rp=9,rw=10,t=3,x[2]=0，解向量为x[]=(0,0,0,0)，创建新结点G，加入q队列。如下表所示。

5. 扩展D结点。队头元素D出队，该结点cp+rp>=bestp，满足限界条件，可以扩展。但是rw=3>goods[3].weight=4，所以不满足约束条件，舍弃左分支。扩展右分支，cp=9,rp=9-5=4,cp+rp>=bestp=9，满足限界条件，不放入3号物品，cp=9,rp=4,rw=3,t=4,x[3]=0，解向量为x[]=(1,1,0,0)，创建新结点H，加入q队列。如下表所示。

6. 扩展E结点。同理可得cp=11,rp=4,rw=4,t=4,x[3]=1，更新解向量为x[]=(1,0,1,0)，生成左孩子I，加入q队列，更新bestp=11。扩展右分支，cp=6,rp=9-5=4,cp+rp=10<bestp=11，所以不满足限界条件，舍弃。
7. 扩展F结点。同理得到左分支，cp=8,rp=4,rw=1,t=4,x[3]=1，解向量为x[]=(0,1,1,0)，生成左孩子J，加入q队列。扩展右分支，cp+rp<11，舍弃。
8. 扩展G结点。该结点cp+rp<bestp=11，不满足限界条件，不再扩展。
9. 扩展H结点。队头H结点出队，该结点cp+rp>=bestp，满足限界条件，rw=3>goods[4].weight=2，满足约束条件，令cp=9+4=13,rp=4-4=0,rw=3-2=1,t=5,x[4]=1，解向量更新为x[]=(1,1,0,1)，生成孩子K，加入q队列，更新bestp=13。右分支不满足限界条件舍弃。
10. 扩展I结点。 队头I结点出队，该结点cp+rp>=bestp，满足限界条件，rw=4>goods[4].weight=2，满足约束条件，令cp=11+4=15,rp=4-4=0,rw=4-2=2,t=5,x[4]=1，解向量更新为x[]=(1,0,1,1)，生成孩子L，加入q队列，更新bestp=15。右分支不满足限界条件舍弃。
11. 队头元素J出队，该结点cp+rp=12<15，不满足限界条件，不再扩展。
12. 队头元素K出队，扩展K结点：t=5，已经处理完毕，cp<bestp，不是最优解。
13. 队头元素K出队，扩展K结点：t=5，已经处理完毕，cp=bestp，是最优解，输出该向量(1,0,1,1)。
14. 队列为空，算法结束。

代码实现

int bestp, W, n, sumw, sumv;/*bestp 用来记录最优解。W为购物车最大容量。n为物品的个数。sumw 为所有物品的总重量。sumv 为所有物品的总价值。*///bfs 来进行子集树的搜索。int bfs(){ int t, tcp, trp, trw; queue<Node> q; //创建一个普通队列(先进先出) q.push(Node(0, sumv, W, 1)); //压入一个初始结点 while (!q.empty()) //如果队列不空 { Node livenode, lchild, rchild;//定义三个结点型变量 livenode = q.front();//取出队头元素作为当前扩展结点livenode q.pop(); //队头元素出队 //cp+rp>bestp当前装入的价值+剩余物品价值小于当前最优值时，不再扩展。 cout << "当前结点的id值:" << livenode.id << "当前结点的cp值:" << livenode.cp << endl; cout << "当前结点的解向量:"; for (int i = 1; i <= n; i++) { cout << livenode.x[i]; } cout << endl; 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.cp + livenode.rp<bestp)//判断当前结点是否满足限界条件，如果不满足不再扩展 continue; //扩展左孩子 tcp = livenode.cp; //当前购物车中的价值 trp = livenode.rp - goods[t].value; //不管当前物品装入与否，剩余价值都会减少。 trw = livenode.rw; //购物车剩余容量 if (trw >= goods[t].weight) //满足约束条件，可以放入购物车 { lchild.rw = trw - goods[t].weight; lchild.cp = tcp + goods[t].value; lchild = Node(lchild.cp, trp, lchild.rw, t + 1);//传递参数 for (int i = 1; i<t; i++) { lchild.x[i] = livenode.x[i];//复制以前的解向量 } lchild.x[t] = true; if (lchild.cp>bestp)//比最优值大才更新 bestp = lchild.cp; q.push(lchild);//左孩子入队 } //扩展右孩子 if (tcp + trp >= bestp)//满足限界条件，不放入购物车 { rchild = Node(tcp, trp, trw, t + 1);//传递参数 for (int i = 1; i<t; i++) { rchild.x[i] = livenode.x[i];//复制以前的解向量 } rchild.x[t] = false; q.push(rchild);//右孩子入队 } } return bestp;//返回最优值。}

算法分析

时间复杂度为O(2ⁿ⁺¹)，空间复杂度O(n*2ⁿ⁺¹)。

算法优化拓展——优先队列式分支限界法

优先队列优化，简单来说就是以当前结点的上界为优先值，把普通队列改成优先队列。
1. 算法设计。约束条件没有改变。优先级定义为活结点代表的部分解锁描述的装入物品价值的上界，该价值上界越大，优先级越高。活结点的价值上界up=活结点的cp+剩余物品装满购物车剩余容量的最大价值rp’。限界条件变为up=cp+rp’>=bestp。
2. 解题步骤（简略版）
– 初始化。sumw和sumv分别用来统计所有物品的总重量和总价值。sumw=13,sumv=18,sumw>W，所以不能全部装完，需要搜索求解。
– 按价值重量比非递增排序。排序结果如下表所示。
– 后续不再详细叙述。

3.代码实现

//定义辅助物品结构体，包含物品序号和单位重量价值,用于按单位重量价值(价值/重量比)排序、struct Object { int id; //物品序号 double d;//单位重量价值 }S[N];//定义排序优先级按照物品单位重量价值由大到小排序bool cmp(Object a1,Object a2){ return a1.d>a2.d;}//定义队列的优先级。 以up为优先，up值越大，也就越优先bool operator <(const Node &a, const Node &b){ return a.up<b.up;}int bestp,W,n,sumw,sumv;/* bestv 用来记录最优解。 W为背包的最大容量。 n为物品的个数。 sumw 为所有物品的总重量。 sumv 为所有物品的总价值。*/double Bound(Node tnode){ double maxvalue=tnode.cp;//已装入购物车物品价值 int t=tnode.id;//排序后序号 //cout<<"t="<<t<<endl; double left=tnode.rw;//剩余容量 while(t<=n&&w[t]<=left) { maxvalue+=v[t]; // cout<<"malvalue="<<maxvalue<<endl; left-=w[t]; t++; } if(t<=n) maxvalue+=double(v[t])/w[t]*left; //cout<<"malvalue="<<maxvalue<<endl; return maxvalue;}//priorbfs 为优先队列式分支限界法搜索。int priorbfs(){ int t,tcp,trw; double tup; //当前处理的物品序号t，当前装入购物车物品价值tcp， //当前装入购物车物品价值上界tup，当前剩余容量trw priority_queue<Node> q; //创建一个优先队列,优先级为装入购物车的物品价值上界up q.push(Node(0, sumv, W, 1));//初始化,根结点加入优先队列 while(!q.empty()) { Node livenode, lchild, rchild;//定义三个结点型变量 livenode=q.top();//取出队头元素作为当前扩展结点livenode q.pop(); //队头元素出队 cout<<"当前结点的id值:"<<livenode.id<<"当前结点的up值:"<<livenode.up<<endl; cout<<"当前结点的解向量:"; for(int i=1; i<=n; i++) { cout<<livenode.x[i]; } cout<<endl; t=livenode.id;//当前处理的物品序号 // 搜到最后一个物品的时候不需要往下搜索。 // 如果当前的购物车没有剩余容量(已经装满)了，不再扩展。 if(t>n||livenode.rw==0) { if(livenode.cp>=bestp)//更新最优解和最优值 { cout<<"更新最优解向量:"; for(int i=1; i<=n; i++) { bestx[i]=livenode.x[i]; cout<<bestx[i]; } cout<<endl; 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;//返回最优值。}