广度优先

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

算法思想

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

算法步骤

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

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

1.相同点:

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

2.不同点

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

0-1背包问题

问题分析

前面有,不再重述,

w[]1234
2542
v[]1234
6354

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

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

算法设计

  1. 定义问题的解空间。问题解空间为{x1,x2,…,xi,…,xn},显约束为:xi=0或者1。
  2. 确定解空间的组织结构:子集树。
  3. 搜索解空间:
    • 约束条件为:wixi≤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 }};
  1. 扩展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表示为空
BXXX
BXXX
BCXX
BCXX
  1. 扩展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队列。如下表所示。
CDEX
CDEX
  1. 扩展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队列。如下表所示。
DEFG
DEFG
  1. 扩展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队列。如下表所示。
EFGH
EFGH
  1. 扩展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,所以不满足限界条件,舍弃。
  2. 扩展F结点。同理得到左分支,cp=8,rp=4,rw=1,t=4,x[3]=1,解向量为x[]=(0,1,1,0),生成左孩子J,加入q队列。扩展右分支,cp+rp<11,舍弃。
  3. 扩展G结点。该结点cp+rp<bestp=11,不满足限界条件,不再扩展。
  4. 扩展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。右分支不满足限界条件舍弃。
  5. 扩展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。右分支不满足限界条件舍弃。
  6. 队头元素J出队,该结点cp+rp=12<15,不满足限界条件,不再扩展。
  7. 队头元素K出队,扩展K结点:t=5,已经处理完毕,cp<bestp,不是最优解。
  8. 队头元素K出队,扩展K结点:t=5,已经处理完毕,cp=bestp,是最优解,输出该向量(1,0,1,1)。
  9. 队列为空,算法结束。

代码实现

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(2n+1),空间复杂度O(n*2n+1)。

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

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

weight2245
value6453

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;//返回最优值。}