回溯法

回溯法的思想是：能进则进，进不了换，换不了退。

隐约束指对能否得到问题的可行解和最优解做出的约束。隐约束包括约束函数和限界函数。

关键步骤是：

1. 定义解空间；
2. 确定解空间的组织结构（子集树、排列数、m叉树等）；
3. 搜索解空间。

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

大卖场购物（0-1背包问题）

问题举例

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

w[]	1	2	3	4
数值	2	5	4	2

w[]	1	2	3	4
数值	6	3	5	4

问题分析

1. 解空间={x₁,x₂,...,x_i,...,x_n}的所有子集（包括{0,0,0}这种子集），你像这里面就是{0,0,0,0},{0,0,0,1},{0,0,1,0},{0,0,1,1},…{1,1,1,1}。显约束为x_i=0或1。
2. 确定解空间的组织结构。由于显约束的缘故，可以看出解空间为子集树。

3. 搜索解空间

   • 约束条件为：w_ix_i≤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开始。并且以左子树为x_i=1，右子树x_i=0。

（2）开始搜索第一层（t=1）。cw=cw+w[1]=2cp=cp+v[1]=6，将2号结点加入左子树。(2号结点是第一个商品）

（3）拓展2号结点。考虑cw+w[2]=7左子树。（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左子树。（5号结点是第4个商品）

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

（7）回溯拓展4号。此时cp=9，若将5号结点加入右子树，cp+rp=9由于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左子树。（7号结点是第3件商品）。

（10）拓展7号结点（t=4）

cw+w[4]=8左子树。令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(12ⁿ+n 2ⁿ)=O(n * 2ⁿ)。

（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]

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

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. 定义问题的解空间。问题的解空间为 {x₁,x₂,...,x_i,...,x_n}的所有子集（包括{0,0,0}这种子集），你像这里面就是{0,0,0,0},{0,0,0,1},{0,0,1,0},{0,0,1,1},…{1,1,1,1}。显约束为x_i=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* 2ⁿ)，空间复杂度为O(n)。