计算机算法回溯法.ppt

计算机算法回溯法
*
第1页，共30页，2022年，5月20日，5点59分，星期三
通过应用范例学习回溯法的设计策略。
（1）装载问题；
（2）批处理作业调度；
（3）符号三角形问题
（4）n后问题；
（5）0-1背包问题； }
else t--;
}
}
*
第8页，共30页，2022年，5月20日，5点59分，星期三
子集树与排列树
遍历子集树需O(2n)计算时间
遍历排列树需要O(n!)计算时间
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);
}
}
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]);
}
}
*
第9页，共30页，2022年，5月20日，5点59分，星期三
装载问题
有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且
装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。
容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。
(1)首先将第一艘轮船尽可能装满；
(2)将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。由此可知，装载问题等价于以下特殊的0-1背包问题。
用回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法。
*
第10页，共30页，2022年，5月20日，5点59分，星期三
装载问题
解空间：子集树
可行性约束函数(选择当前元素)：
上界函数(不选择当前元素)：
当前载重量cw+剩余集装箱的重量r当前最优载重量bestw
void backtrack (int i)
{// 搜索第i层结点
if (i > n) // 到达叶结点
更新最优解bestx,bestw;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];
}
*
第11页，共30页，2022年，5月20日，5点59分，星期三
批处理作业调度
给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。
tji
机器1
机器2
作业1
2
1
作业2
3
1
作业3
2
3
这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。
*
第12页，共30页，2022年，5月20日，5点59分，星期三
批处理作业调度
解空间：排列树
void Flowshop::Backtrack(int i)
{
if (i > n) {
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestf = f;
}
else
for (int j = i; j <= n; j++) {
f1+