回溯法
回溯法的思想是：能进则进，进不了换，换不了退。
隐约束指对能否得到问题的可行解和最优解做出的约束。隐约束包括约束函数和限界函数。
关键步骤是：
- 定义解空间；
- 确定解空间的组织结构（子集树、排列数、m叉树等）；
- 搜索解空间。
回溯法阶梯的关键是设计有效的显约束和隐约束。
大卖场购物（0-1背包问题）
问题举例
每个物品重量w和价值v如下表所示，购物车容量为W，求不超过购物车重量的最大价值。
| w[] | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 数值 | 2 | 5 | 4 | 2 |
| w[] | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 数值 | 6 | 3 | 5 | 4 |
问题分析
- 解空间={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。
- 确定解空间的组织结构。由于显约束的缘故，可以看出解空间为子集树。
-
搜索解空间
- 约束条件为：wixi≤W（i=1~n）
- 限界条件：cp+rp>bestp（cp为当前已经装入购物车的物品的总价值，rp为第t+1~第n种物品的总价值，bestp为最大价值）
- 搜索过程见问题求解。
问题求解
（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]=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(12n+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所有团中，含结点数最多的团。
算法设计
- 定义问题的解空间。问题的解空间为 {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。
- 解空间的组织结构：子集树，深度为n。
-
搜索解空间：
- 约束条件：假设当前扩展结点位于解空间树的第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)。
