回溯法

回溯法的思想是:能进则进,进不了换,换不了退
隐约束指对能否得到问题的可行解和最优解做出的约束。隐约束包括约束函数限界函数
关键步骤是:
1. 定义解空间;
2. 确定解空间的组织结构(子集树、排列数、m叉树等);
3. 搜索解空间。

回溯法阶梯的关键是设计有效的显约束隐约束

大卖场购物(0-1背包问题)

问题举例

每个物品重量w和价值v如下表所示,购物车容量为W,求不超过购物车重量的最大价值。

w[]1234
2542
w[]1234
6354

问题分析

  1. 解空间={x1,x2,…,xi,…,xn}的所有子集(包括{0,0,0}这种子集),你像这里面就是{0,0,0,0},{0,0,0,1},{0,0,1,0},{0,0,1,1},…{1,1,1,1}。显约束为xi=0或1。
  2. 确定解空间的组织结构。由于显约束的缘故,可以看出解空间为子集树。
  3. 搜索解空间

– 约束条件为:wixi≤W(i=1~n)
– 限界条件:cp+rp>bestp(cp为当前已经装入购物车的物品的总价值,rp为第t+1~第n种物品的总价值,bestp为最大价值)
4. 搜索过程见问题求解。

问题求解

(1)首先初始化。w[]={2,5,4,2},v[]={6,3,5,4},sumw=2+5+4+2=13,sumv=6+3+5+4=18,因为sumw>W,所以不能装完,所以需要进行后续的操作。此时定义一个cp=rp=bestp=0,x[i]=0,cw=0。
注意:在这里w[]和v[]的下标都是从1开始。并且以左子树为xi=1,右子树xi=0。

(2)开始搜索第一层(t=1)。cw=cw+w[1]=2<W,所以令x[1]=1,
cp=cp+v[1]=6,将2号结点加入左子树。(2号结点是第一个商品)

(3)拓展2号结点。考虑cw+w[2]=7<W,所以令x[2]=1,cp=cp+v[2]=9,将3号结点加入左子树。(3号结点是第2个商品)

(4)拓展3号结点。考虑cw+w[3]=11>W,所以x[3]=0,然后计算cp+rp=9+4=13>bestp(此时bestp还是0),所以将4号结点加入右子树。(4号结点是第3个商品)

(5)拓展4号结点。考虑cw+w[4]=9<W,所以x[4]=1,然后计算cp=cp+v[4]=13,所以将5号结点加入左子树。(5号结点是第4个商品)

(6)拓展5号结点。由于此时t>n,故已经找到了一个当前的最优解,令bestp=cp(值为13),5号结点成为死结点。返回到上一结点。

(7)回溯拓展4号。此时cp=9,若将5号结点加入右子树,cp+rp=9<bestp,故该结点不满足限界条件,成为死结点,继续回溯到3号结点。由于3号结点已经研究过,左子树不可行,所以回溯到2号结点。

(8)扩展2号结点(t=2)。之前扩展了左子树,所以现在考虑右子树。此时cp=6,bound(t+1)=cp+rp=15>bestp,因此满足限界条件,扩展右子树,令x[2]=0,生成6号结点。(也就是第2个商品不要了)

(9)扩展6号结点(t=3)。cw+w[3]=6<W,满足约束条件,扩展左分支,令x[3]=1,cw=cw+w[3]=6,cp=cp+v[3]=11,生成7号结点加入左子树。(7号结点是第3件商品)。

(10)拓展7号结点(t=4)
cw+w[4]=8<W,满足约束条件,扩展到左子树。令x[4]=1,cw=cw+w[4]=8,cp=cp+v[4]=15。(8号结点是第4件商品)

(11)拓展8号结点(t=5)。由于此时t>n,故已经找到了一个当前的最优解,令bestp=cp(值为15),8号结点成为死结点。返回到上一结点。

(12)拓展7号结点(t=4)。考察bound(t+1)=cp+rp=11<15,成为死结点。

(13)拓展6号结点(t=3)。bound(t+1)=cp+rp=10<15,成为死结点。

(14)拓展1号结点(t=1),bound(t+1)=12<15,成为死结点。算法结束。

代码实现

double Bound(int i)//计算上界{ int rp=0;//剩余重量 while (i <= n) { rp += v[i]; i++; } return rp+cp;}void Backtrack(int t)//t当前在第t层{ if (t > n) { for (i = 1; i <= n; i++) { bestx[i] = x[i]; } bestp = cp; return; } if (cw + w[t] <= W)//还未到重量,可以搜索左子树 { x[t] = true; cw += w[t]; cp += v[t]; Backtrack(t + 1); cw -= w[t];//回溯 cp -= v[t];//回溯 } //若左子树不满足,然后看右子树,判断限界条件 if (Bound(t + 1) > bestp) { x[t] = false; Backtrack(t + 1); }}void initial_parameter(double W, int n){ cw = 0;//初始化当前重量为0 cp = 0;//初始化当前价值为0 bestp = 0;//初始化当前最好价值为0 int sumw = 0;//统计所有物品的总重量 int sumv = 0;//统计所有物品价值 //这里上面两个参数可以根据具体情况确定为int或者double等 for (i = 1; i <= n; i++) { sumw += w[i]; sumv += v[i]; } if (sumw <= W) { bestp = sumv; cout << "所有物品均放入购物车"; cout << "放入购物车的最大价值为" << bestp << "元。" << endl; return; } Backtrack(1); cout << "放入购物车的最大价值为" << bestp << "元。" << endl; cout << "放入购物车的物品序号为:"; for (i = 1; i <= n; i++) { if (bestx[i] == true) cout << i << " "; } cout << endl;}

算法复杂度和改进

1.算法复杂度
(1)时间复杂度:O(1*2n+n * 2n)=O(n * 2n)。
(2)空间复杂度:O(n)。
2.算法优化
实际上,经常我们在计算bound()函数的时候对于rp多算太多了,因为很有可能rp到某一步就超过了购物车的中梁,所以我们可以缩小上界,从而加快剪枝速度,提高搜索效率。
上界函数bound():当前价值cp+剩余容量可容纳的剩余物品的最大价值brp(为了能装最大价值,所以在计算上界函数的时候可以对商品分割,但实际的时候不允许),即修改为

double bound(int i){ //剩余物品为第i~n种物品 double cleft=W-cw;//剩余容量 while(i<=n && w[i]<cleft) { cleft-=w[i]; brp+=v[i]; i++ } //下面是采用切割的方式装满背包,这里是求上界, //所以可以这样做。实际是不允许的 if(i<=n) { brp+=v[i]/w[i]*cleft; } return cp+brp;}

为了更好地计算和运用上界函数剪枝,先将物品按照其单位重量价值(价值/重量)从大到小排序,然后按照排序后的顺序考察各个物品。即定义这样一个结构体:

struct Object{ int id;//物品序号 double ;//单位重量价值};bool cmp(Object a1, Object a2){ return a1.d>a2.d;}

然后将 initial_parameter(double W, int n)的if(sumw<=W)这个语段后面加入:

sort(Q,Q+n,cmp);for(i=1;i<=n;i++){ a[i]=w[Q[i-1].id];//把排序后的数据传递给辅助数组 b[i]=v[Q[i-1].id];}for(i=1;i<=n;i++){ w[i]=a[i]; v[i]=b[i];}

然后将

for (i = 1; i <= n; i++){ if (bestx[i] == true) cout << i << " ";}

修改为

 for (i = 1; i <= n; i++){ if (bestx[i] == true) cout << Q[i-1].id << " ";}

最大团

问题描述

部落酋长希望组织一支保卫部落的卫队,要在居民中选出最多的居民加入,并保证卫队中任何两个人都不是仇敌。编程计算构建部落护卫队的最佳方案。

问题分析

  • 完全子图:给定无向图G(V,E),其中V是结点集,E是边集。G’=(V’,E’)。如果结点集V’⊆V,E’⊆E,且G’***中的任意两个结点都有边相连,则成G’G**的完全子图。
  • 当且仅当G’不包含在G的更大的完全子图中时,G的完全子图G’G的团,就是说G’G的极大完全子图。
  • 最大团:G的最大团是指G所有团中,含结点数最多的团。

算法设计

  1. 定义问题的解空间。问题的解空间为 {x1,x2,…,xi,…,xn}的所有子集(包括{0,0,0}这种子集),你像这里面就是{0,0,0,0},{0,0,0,1},{0,0,1,0},{0,0,1,1},…{1,1,1,1}。显约束为xi=0或1。
  2. 解空间的组织结构:子集树,深度为n
  3. 搜索解空间:
    • 约束条件:假设当前扩展结点位于解空间树的第t层,那么从第1到第t-1层的结点情况都已经确定,接下来是按照扩展结点的左分支进行扩展,此时需要判断是否将第t个结点放到团里,只要第t和结点和前面t-1个结点中被选中的结点都有边连接,那么就能放到团里,即x[i]=1,否则不能放到团里,即x[i]=0。
    • 限界条件:根据前t个结点的状态确定当前已经放入团中的结点个数(用cn表示),假想t+1个结点到第n结点全部放入团内,放入的节点个数(fn表示),fn=n-t,则cn+fn是所有从根出发的路径中经过中间结点z的可行解所包含结点个数的上界。若cn+fn>bestn,则需要向子孙结点搜索,否则不需要。所以限界条件为cn+fn>bestn

代码实现

bool isPlace(int t){ bool status = true; for (int j = 1; j < t; j++) { if (x[j] && a[t][j] == 0) { status = false; break; } } return status;}//回溯法主体void backtrack(int t){ //到达叶结点 if (t > n) { for (int i = 1; i <= n; i++) bestx[i] = x[i]; bestn = cn; return; } if (isPlace(t)) { x[t] = 1; cn++; backtrack(t + 1); cn--; } if (cn + n - t > bestn)//这里可以进行优化 { x[t] = 0; backtrack(t + 1); }}

算法复杂度分析

1.时间复杂度:O(n* 2n),空间复杂度为O(n)。