算法笔记之回溯法（1）

回溯法

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

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

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

问题举例

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

问题分析

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]=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*2ⁿ+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]<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. 定义问题的解空间。问题的解空间为 {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)。