以深度优先方式搜索问题解的算法【回溯法是优化的暴力遍历,即一棵树在特定条件作为剪枝函数,树可以提前截掉,省去一些子节点。完全暴力遍历则是需要全部叶子节点都考虑】
回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点,以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法
(1)针对所给问题,定义问题的解空间; (2)确定易于搜索的解空间结构; (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索
常用剪枝函数: 用约束函数在扩展结点处剪去不满足约束的子树; 用限界函数剪去得不到最优解的子树。
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻,算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n),则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。
有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi,且
装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。如果有,找出一种装载方案。 容易证明,如果一个给定装载问题有解,则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满; (2)将剩余的集装箱装上第二艘轮船。 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集,使该子集中集装箱重量之和最接近。由此可知,装载问题等价于以下特殊的0-1背包问题
void backtrack (int i){// 搜索第i层结点
if (i > n){//到达叶结点更新最优解bestx;return;}
r -= w[i];
if (cw + w[i] <= c) {// 搜索左子树
x[i] = 1;
cw += w[i];
backtrack(i + 1);
cw -= w[i];
}
if (cw + r > bestw) {// 搜索右子树
x[i] = 0;
backtrack(i + 1);
}
r += w[i];
}
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。
2)不处于同一正、反对角线:
boolean place (int k) {
for (int j=1;j<k;j++)
if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;
return true;
}
void backtrack (int t) {
if (t>n) output(x);
else
for (int i=1;i<=n;i++) {
x[t]=i;
if (place(t)) backtrack(t+1);
}
}
解向量:(x1, x2, … , xn)是1,2, … ,n的排列 约束: 不处于同一正、反对角线
boolean place (int k) {
for (int j=1;j<k;j++)
if ((abs(k-j)==abs(x[j]-x[k]))) return false;
return true;
}
void backtrack (int t) {
if (t>n) output(x);
else
for (int i=t;i<=n;i++) {
swap(x[t],x[i]);
if (place(t)) backtrack(t+1);
swap(x[t],x[i]);
}
}
#define n 7
char s[n] = {a,b,c,d,e,f,g};
int x[n];
void output(int x[]);
void all_subset ( ){
backtrack(0);
}
void backtrack (int t){
if (t>=n) output(x);
else
for (int i=0;i<=1;i++) {
x[t]=i;
backtrack(t+1);
}
}
void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=0;i<=1;i++) {
x[t]=i;
if (legal(t)) backtrack(t+1);
}
}
#define n 7
int s[n] = {1,2,3,4,5,6,7};
int x[n];
void output(int x[]);
void all_ permutation( ){
backtrack(0);
}
void backtrack (int t){
if (t>=n) output(x);
else
for (int i=t; i<n; i++) {
swap(x[t],x[i]);
backtrack(t+1);
swap(x[t],x[i]);
}
}
#define n 7
int s[n] = {1,2,3,4,5,6,7};
int x[n];
void output(int x[]);
void all_subset ( ){
backtrack(0);
}
void backtrack (int t){
if (t>=n) output(x);
else
for (int i=t;i<n;i++) {
swap(x[t],x[i]);
if(legal(t)) backtrack(t+1);
swap(x[t],x[i]);
}
bool legal(int t){
bool bRet = true;
for (int i=0;i<t;i++) {
bRet &&= ((x[i]-x[i+1])%2==1);
}
return bRet;
}
剪枝剪剪【legal函数】
#define n 7
int x[n], s[n] = {1,2,3,4,5,6,7};
void main ( ){
backtrack1(0);
backtrack2(0);
}
void backtrack1 (int t){
if (t>=n) output(x);
else
for (int i=0;i<=1;i++) {
x[t]=i;
if(legal(t)) backtrack1(t+1);
}
}
void backtrack2 (int t){
if (t>=n) output(x);
else
for (int i=t;i<n;i++) {
swap(x[t],x[i]);
if(legal(t)) backtrack2(t+1);
swap(x[t],x[i]);
}
}
5-1, 5-2, 5-3,5-4, 5-5