《算法设计与分析》-第五章 回溯法

n后问题算法的描述如下:
1. void n_queens(int n,int x[]) 2. { 3. int k = 1; /* k:搜索深度 */ : 4. x[1] = 0; 5. while (k>0) { 6. x[k] = x[k] + 1; /* 在当前列加 的位置开始搜索 */ 在当前列加1的位置开始搜索 7. while ((x[k]<=n)&&(!place(x,k))) /* 当前列位置是否满足条件 */ 8. x[k] = x[k] + 1; /* 不满足条件 继续搜索下一列位置 */ 不满足条件,继续搜索下一列位置 9. if (x[k]<=n) { /* 存在满足条件的列 */ 存在满足条件的列? 10. if (k==n) break; /* 是最后一个皇后 完成搜索 */ 是最后一个皇后,完成搜索 11. else { 12. k = k + 1; x[k] = 0; /* 不是 则处理下一个行皇后 */ 不是,则处理下一个行皇后 13. } 14. } 15. else { /* 已判断完 列,均没有满足条件 */ 已判断完n列 均没有满足条件 16. x[k] = 0; k = k – 1; /* 第k行复位为 回溯到前一行 */ 行复位为0,回溯到前一行 行复位为 17. } 18. } 19. }
–
}
5.2 回溯法的算法框架
用回溯法搜索排列树的一般解法:
– –
Void traceback(int t) {
If(t>n) output(x); Else for(i=t;i<=n;i++){ swap(x[t],x[i]); if(constraint(t)&&bound(t)) backtrack(t+1); swap(x[i],x[t]); }
5.1 回溯法的基本思想
(2)状态空间树:问题解空间的树形式表示 例:n=3, 0/1背包问题的状态空间树.
1 1 D 1 H 0 I 1 J B 0 E 0 K 1 L 1 F M 1 N A 0 C 0 G 0 O
----子集树 解空间大小: 2n
5.1 回溯法的基本思想
(2)状态空间树:问题解空间的树形式表示 例:n=4, 旅行商问题的状态空间树.
void backtrack(int i){ if(i>n){ if(cw>bestw) bestw=cw; return; } if(cw+w[i]<=c){ cw+=w[i]; backtrack(i+1); cw-=w[i]; } backtrack(i+1); }
5.5 回溯法的应用 回溯法的应用—0/1背包问题 背包问题
回溯法(backtracking) 第五章 回溯法
5.1 回溯法的基本思想 5.2 回溯法的算法框架 5.3 回溯法的应用—n后问题 5.4 回溯法的应用—装载问题
回溯法(Backtracking) 第五章 回溯法
回溯法和分支限界法都是通过系统地搜索解空 间树而求得问题解的搜索算法. 在系统地检查解空间的过程中,抛弃那些不可 能导致合法解的候选解,从而使求解时间大大 缩短.(与蛮干算法相区别) 回溯法以深度优先的方式搜索解空间,而分支 限界法以广度优先或最小耗费(最大收益)的 方式搜索解空间.
}
–
}
5.2 回溯法的算法框架
用回溯法搜索子集树的一般解法:
– –
Void backtrack(int t) {
If(t>n) output(x); Else for(i=0;i<=1;i++){ x[t]=i; if(constraint(t)&&bound(t)) backtrack(t+1); }
A 2 C 3 F 4 L 4 2 G H 3 4 M N 1 B 3 D
4 4 I 2 O E 2 J 3 P 3 K 2 Q
----排列树 解空间大小: n!
5.1 回溯法的基本思想
(3)状态空间树的动态搜索
可行解和最优解: 可行解:满足约束条件的解,解空间中的一个子集 最优解:使目标函数取极值(极大或极小)的可行解,一 个或少数几个 例:货郎担问题,有nn种可能解. n!种可行解,只有一个或 几个解是最优解. 例:背包问题,有2n种可能解,有些是可行解,只有一个或 几个是最优解. 有些问题,只要可行解,不需要最优解,例如八后问题.
}
5.4 回溯法的应用 装载问题 回溯法的应用—装载问题
有一批集装箱要装上一艘载重量为c的轮船. 其中集装箱i的重量为Wi.最优装载问题要求 确定在装载体积不受限制的情况下,将尽可能 多的集装箱装上轮船.
int n,w[],c,cw,bestw; int maxloading(){ cw=0;bestw=0; backtrack(1); return bestw; }
5.1 回溯法的基本思想
回溯法(backtracking)是一种系统地搜索问 题解的方法.为实现回溯,首先需要定义一个 解空间(solution space),然后以易于搜索 的方式组织解空间,最后用深度优先的方法搜 索解空间,获得问题的解.
5.1 回溯法的基本思想
回溯法求解的三个步骤: (1)定义一个解空间,它包含问题的解 (2)用易于搜索的方式组织解空间 (3)深度优先搜索解空间,获得问题的解.
5.1 回溯法的基本思想
(1)解空间 设问题的解向量为X=(x1,x2,…,xn) ,xi的取值范 围为有穷集Si .把xi的所有可能取值组合,称 为问题的解空间.每一个组合是问题的一个可 能解.
5.1 回溯法的基本思想
(1)解空间 例:0/1背包问题,S={0,1},当n=3时,0/1背 包问题的解空间是: {(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1, 1,0),(1,1,1)} 当输入规模为n时,有2n种可能的解.
5.1 回溯法的基本思想
(3)状态空间树的动态搜索
状态空间树的动态搜索 l_结点(活结点):所搜索到的结点不是叶结点,且满足 约束条件和目标函数的界,其儿子结点还未全部搜索完毕, e_结点(扩展结点):正在搜索其儿子结点的结点,它也 是一个l_结点; d_结点(死结点):不满足约束条件,目标函数,或其儿 子结点已全部搜索完毕的结点,或者叶结点.以d_结点作 为根的子树,可以在搜索过程中删除.
皇问题) (8-皇问题) 皇问题
8皇后问题可以表示成8-元组(x1,…,x8),其中xi是放在第 i行的皇后所在的列号.于是,解空间由88个8-元组组 成. 约束条件:xi≠xj for all i, j |xi-xj|≠| j-i | 约束条件之一为没有两个xi相同(即任意两个皇后不在 同一列上).将其加入到元组的定义中,这时解空间的 大小由88个元组减少到8!个元组.
n后问题算法的描述如下:
int n, sum,x[]; void n_queens(){
sum=0; x[ ]=0; backtrack(1); }
void backtrack(int t) {
if (t>n){sum++;output(x)} else for(i=1;i<=n;i++){ x[t]=i; if place(x,t) backtrack(t+1); }
5.2 回溯法的算法框架
递归回溯的一般解法:
– –
VoБайду номын сангаасd traceback(int t) {
If(t>n) output(x); Else for(i=f(n,t);i<=g(n,t);i++){ x[t]=h[i]; if(constraint(t)&&bound(t)) backtrack(t+1); }
�
–
}
5.3 回溯法的应用 回溯法的应用—n后问题 后问题
例1(8-皇问题)
皇问题) 例1(8-皇问题) ( 皇问题
在8×8的棋盘上放置8个皇后,使得这8个皇 后不在同一行,同一列及同一斜角线上.如下 1 2 3 4 5 6 7 8 图6.1: Q
1 2 3 4 5 6 7 8
Q Q Q Q Q Q Q
int c,n,w[],p[],cw,cp,bestp; void backtrack(int i){ if(i>n){bestp=cp; return;} if(cw+w[i]<=c){ cw+=w[i]; cp+=p[i]; backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(bound(i+1)>bestp) backtrack(i+1); } int bound( int i){ int cleft=c-cw; int bound=cp; while(i<=n&&w[i]<=cleft){ cleft-=w[i]; bound+=p[i]; i++; } if(i<=n) bound+=pi]/w[i]*cleft; return bound; }
5.1 回溯法的基本思想
(1)解空间 例:货郎担(旅行商)问题, S={1,2,…,n},当 n=3时, S={1,2,3} ,货郎担问题的解空间是: {(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),┅ ,(3,3,1),(3,3,2),(3,3,3)} 当输入规模为n时,它有nn种可能的解. 考虑到约束方程xi≠xj.因此,货郎担问题的解 空间压缩为: {(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)} 当输入规模为n时,它有n!种可能的解.