算法分析与设计学习笔记--7

回溯算法
回溯法是一种组织搜索的一般技术，有“通用的解题法”之称，用它可以系统的搜索一个问题的所有解或任一解。
有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。
可以系统地搜索一个问题的所有解或任意解，既有系统性又有跳跃性。
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。
这种以深度优先的方式系统地搜索问题的解的方法称为回溯法。

6.1.1 问题的解空间
应用回溯法求解时，需要明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。
例如，对于有n种可选择物品的0—1背包问题，其解空间由长度为n的0—1向量组成，该解空间包含了对变量的所有可能的0—1赋值。

在生成解空间树时，定义以下几个相关概念：
活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。
扩展结点：当前正在生成其儿子结点的活结点叫扩展结点（正扩展的结点）。
死结点：不再进一步扩展或者其儿子结点已全部生成的结点就是死结点。

在确定了解空间的组织结构后，回溯从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。
这个开始结点成为一个活结点，同时成为当前的扩展结点。在当前的扩展结点，搜索向深度方向进入一个新的结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。
若在当前扩展结点处不能再向深度方向移动，则当前的扩展结点成为死结点，即该活结点成为死结点。此时回溯到最近的一个活结点处，并使得这个活结点成为当前的扩展结点。
回溯法以这样的方式递归搜索整个解空间（树），直至满足中止条件。

例6.1 0—1背包问题
　假设背包容量C＝30，w＝{16，15，15}，v＝{45，25，25}

例6.2 旅行商问题
TSP问题(Traveling Salesman Problem)通常称为旅行商问题，也称为旅行售货员问题、货担郎问题等，是组合优化中的著名难题，也是计算复杂性理论、图论、运筹学、最优化理论等领域中的一个经典问题，具有广泛的应用背景。TSP问题最早在20世纪20年代由数学家兼经济学家Karl Menger提出来的。
问题的一般描述为：旅行商从n个城市中的某一城市出发，经过每个城市仅有一次，最后回到原出发点，在所有可能的路径中求出路径长度最短的一条。
设G=(V, E)是一个带权图，其每一条边(u, v)∈E的费用（权）为正数w(u, v)。目的是要找出G的一条经过每个顶点一次且仅经过一次的回路，即汉密尔顿（Hamilton）回路v1，v2 ，…，vn ，使回路的总权值最小：

（1，3，2，4，1）的总权值为25，为最优回路。

回溯法的基本思想

在回溯法搜索解空间树时，通常采用两种策略（剪枝函数）避免无效搜索以提高回溯法的搜索效率：
用约束函数在扩展结点处减去不满足约束条件的子树；
用限界函数减去不能得到最优解的子树。
解0—1背包问题的回溯法用剪枝函数剪去导致不可行解的子树。
解旅行商问题的回溯算法中，如果从根结点到当前扩展结点的部分周游路线的费用已超过当前找到的最好周游路线费用，则以该结点为根的子树中不包括最优解，就可以剪枝。

子集树与排列树

有时问题是要从一个集合的所有子集中搜索一个集合，作为问题的解。或者从一个集合的排列中搜索一个排列，作为问题的解。
回溯算法可以很方便地遍历一个集合的所有子集或者所有排列。
当问题是要计算n个元素的子集，以便达到某种优化目标时，可以把这个解空间组织成一棵子集树。
例如，n个物品的0-1背包问题相应的解空间树就是一棵子集树。
这类子集树通常有2n个叶结点，结点总数为2n +1-1。
遍历子集树的任何算法，其计算时间复杂度都是Ω(2n)。

//形参t为树的深度，根为1
void backtrack (int t)
{
　　if (t>n) update(x);
　　else
　　　　for (int i=0; i<=1; i++)　　//每个结点只有两个子树
　　　　{
　　　　　　x[t]=i;　　　　　　　 //即0/1
　　　　　　if (constraint(t) && bound(t)) backtrack(t+1);
　　　　}
}

约束函数constraint(t)和限界函数bound(t)，称为剪枝函数。
函数update(x)是更新解向量x的。
约束函数constraint(t)，一般可以从问题描述中找到。

当所给的问题是确定n个元素满足某种性质的排列时，可以把这个解空间组织成一棵排列树。
排列树通常有n!个叶子结点。因此遍历排列树时，其计算时间复杂度是Ω(n!) 。
例如，旅行商问题就是一棵排列树。

//形参t为树的深度，根为1
void backtrack (int t)
{
　　if (t>n) update(x);
　　else
　　　　for (int i=t; i<=n; i++)
　　　　{
　　　　　　//为了保证排列中每个元素不同，通过交换 来实现
　　　　　　swap(x[t], x[i]);
　　　　　　if (constraint(t) && bound(t)) backtrack(t+1);
　　　　　　swap(x[t], x[i]);　　　　//恢复状态
　　　　}
}

给定一个物品集合s＝｛1，2，3，…，n｝，物品i的重量是wi，其价值是vi，背包的容量为W，即最大载重量不超过W。在限定的总重量W内，我们如何选择物品，才能使得物品的总价值最大。
输入
第一个数据是背包的容量为c（1≤c≤1500），第二个数据是物品的数量为n（1≤n≤50）。接下来n行是物品i的重量是wi，其价值为vi。所有的数据全部为整数，且保证输入数据中物品的总重量大于背包的容量。
当c＝0时，表示输入数据结束。
输出
对每组测试数据，输出装入背包中物品的最大价值。

令cw(i)表示目前搜索到第i层已经装入背包的物品总重量，即部分解(x1, x2 , …, xi)的重量：
对于左子树， xi =1 ，其约束函数为：
若constraint(i)＞W，则停止搜索左子树，否则继续搜索。

假设当前最优值为bestv，若Bound(i)＜bestv，则停止搜索第i层结点及其子树，否则继续搜索。显然r(i)越小， Bound(i)越小，剪掉的分支就越多。
为了构造更小的r(i) ，将物品以单位重量价值比di=vi/wi递减的顺序进行排列：
d1≥d2≥… ≥dn
对于第i层，背包的剩余容量为W-cw(i)，采用贪心算法把剩余的物品放进背包，根据贪心算法理论，此时剩余物品的价值已经是最优的，因为对剩余物品不存在比上述贪心装载方案更优的方案。
#define NUM 100
int c; //背包的容量
int n; //物品的数量
int cw; //当前重量
int cv; //当前价值
int bestv; //当前最优价值
//描述每个物品的数据结构
struct Object{
int w; //物品的重量
int v; //物品的价值
double d; //物品的单位重量价值比
}Q[NUM]; //物品的数组
对物品以单位重量价值比递减排序的因子是：
bool cmp(Object a, Object b)
{
if(a.d>=b.d) return true;
else return false;
}
物品的单位重量价值比是在输入数据时计算的：
for(int i=0; i<n; i++)
{
scanf("%d%d",&Q[i].w,&Q[i].v);
Q[i].d = 1.0*Q[i].v/Q[i].w;
}
使用C++标准模板库的排序函数sort()排序：
sort(Q, Q+n, cmp);

//形参i是回溯的深度，从0开始
void backtrack(int i)
{
　　//到达叶子结点时，更新最优值
　　if (i+1>n) {bestv = cv; return;}
　　//进入左子树搜索
　　if (cw+Q[i].w<=c)
　　{
　　　　cw += Q[i].w;
　　　　cv += Q[i].v;
　　　　backtrack(i+1);
　　　　cw -= Q[i].w;
　　　　cv -= Q[i].v;
　　}
　　//进入右子树搜索
　　if (Bound(i+1)>bestv) backtrack(i+1);
}
//形参i是回溯的深度
int Bound(int i)
{
　　int cleft = c-cw;　　　//背包剩余的容量
　　int b = cv;　　　　　　//上界
　　//尽量装满背包
　　while (i<n && Q[i].w<=cleft)
　　{
　　　　cleft -= Q[i].w;
　　　　b += Q[i].v;
　　　　i++;
　　}
　　//剩余的部分空间也装满
　　if (i<n) b += 1.0cleftQ[i].v/Q[i].w;
　　return b;
}

n皇后问题
由于棋盘的每列只有一个皇后，所以可以用一维向量X( x1, x2, …, xn)，其中xi∈{1, 2, …, n}，表示第i列皇后所在的行x[i]，即解空间的每个结点都有n个儿子，因此解空间的大小为nn，这是一棵子集树。

算法6.6（1） n皇后问题回溯算法的数据结构
#define NUM 20
int n; //棋盘的大小
int x[NUM]; //解向量
int sum; //当前已经找到的可行方案数

//形参t是回溯的深度，从1开始
void Backtrack(int t)
{
　　int i;
　　//到达叶子结点，获得一个可行方案。累计总数，并输出该方案
　　if (t>n)
　　{
　　　　sum++; //是全局变量
　　　　for (i=1; i<=n; i++)
　　　　　　printf(" %d", x[i]);
　　　　printf("\n");
　　}
　　else
　　　　for (i=1; i<=n; i++)
　　　　{
　　　　　　x[t] = i;
　　　　　　if (Place(t)) Backtrack(t+1);
　　　　}
}
//形参t是回溯的深度
inline bool Place(int t)
{
　　int i;
　　for (i=1; i<t; i++)
　　　　if ((abs(t-i) == abs(x[i]-x[t])) || (x[i] == x[t]))
　　　　　　return false;
　　return true;
}

由于每一列只放置一个皇后，所以不用判断合法性。
对于每一行，假设已经放置到t列，只要判断 ，i＝1, 2, …, t-1互不相同即可。
对于对角线的判断，可以看成是斜率为±1的两条直线，经过两点（i，x[i]）和（t，x[t]）: