算法设计与分析——第6章 回溯算法
回溯法的基本思想
子集树与排列树
回溯算法搜索子集树的伪代码
//形参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);
}
}
//形参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]); //恢复状态
}
}
装载问题
0－1背包问题
图的m着色问题
//形参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
//搜索当前扩展结点的m个孩子
for(i=1; i<=m; i++ )
{
x[t] = i;
if( Same(t) ) BackTrack(t+1);
x[t] = 0;
}
}
n皇后问题
//形参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);
}
}
旅行商问题（TSP问题）
//形参t是回溯的深度，从2开始
void Backtrack(int t)
{
//到达叶子结点的父结点
if(t==n)
{
if(a[x[n-1]][x[n]]!= NoEdge && a[x[n]][1]!= NoEdge &&
(cc + a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc== NoEdge))
{
for(int i=1; i<=n; i++)
bestx[i] = x[i];
bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];
}
return;
}
else
{
for(int i=t; i<=n; i++)
{
if(a[x[t-1]][x[i]]!= NoEdge &&
(cc + a[x[t-1]][x[i]]< bestc||bestc == NoEdge))
{
swap(x[t],x[i]);
cc += a[x[t-1]][x[t]];
Backtrack(t+1);
cc -= a[x[t-1]][x[t]];
swap(x[t],x[i]);
}
}
}
}
流水作业调度问题
流水作业调度问题回溯算法的实现
//形参t是回溯的深度，从1开始
void Backtrack(int t)
{
//到达叶子结点，更新最优解
if (t>n)
{
bestf = f;
for (int i=1; i<=n; i++)
bestx[i]=x[i];
return;
}
for (int i=t; i<=n; i++)
{
f1 += job[x[i]][1];
f2[t] = ((f2[t-1]>f1) ? f2[t-1] : f1)+job[x[i]][2];
f += f2[t];
if (f<bestf) //剪枝
{
swap(x[t], x[i]);
Backtrack(t+1);
swap(x[t], x[i]);
}
f1 -= job[x[i]][1];
f -= f2[t];
}
}