广度优先

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

算法思想

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

算法步骤

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

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

1.相同点:

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

2.不同点

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

0-1背包问题

问题分析

前面有,不再重述,

w[]1234
2542
v[]1234
6354

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

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

  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. 队列为空,算法结束。

代码实现

算法分析

时间复杂度为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.代码实现