《设计 郑宗汉郑晓明 第7章+回溯》由会员分享，可在线阅读，更多相关《设计 郑宗汉郑晓明 第7章+回溯（40页珍藏版）》请在金锄头文库上搜索。
1、第7章 回溯法,7.1 回溯法的思想方法 回溯法是一种通过有组织地检查和处理问题实例的解空间, 并对解空间进行归约的方法。对于解空间很大的一类问题, 这种方法特别有效。,实际生活中有很多问题没有有效算法, 如TSP。求解这类问题可采用: 回溯法(分支限界)、近似算法、随机算法。,7.1.1 问题的解空间和状态空间树 1. 解空间 问题的解向量: X=(x1,x2,xn), xi的所有可能取值的组合称为问题的解空间。例如, 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,
2、1) 输入规模为n时, 有2n种可能的解。,n=3时, 货郎问题的解空间为:(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) 输入规模为n时, 有n!种可能解。 2. 状态空间树问题的解空间可以用树的形式表示,这种树称为状态空间树。,n=4时, 货郎问题的状态空间树如下:,货郎问题的状态空间树为排列树:n!个叶结点, n!种可能的解 遍历排列树需(n!)的计算时间。,n=4时, 0/1背包问题的状态空间树如下:,0/1背包问题的状态空间树为子集树: 2n个叶结点, 2n种可能的解 遍历子集树需(2n)的计算时间。,7.1.2 状态空间树的
3、动态搜索 1. 可行解和最优解 可行解: 满足约束条件的解。解空间的一个子集最优解: 使目标函数取极值(极大或极小)的可行解。1个或少数几个,例如, 0/1背包问题有2n种可能解, 其中一些是可行解, 只有1个或几个是最优解。 再如, 货郎问题有nn种可能解,其中n!种可行解,只有1个或几个是最优解。 有些问题只要可行解, 不需最优解。 如八皇后问题、图着色问题。,2. 状态空间树的动态搜索 穷举法对整个状态空间树中的所有可能解进行搜索, 但只有满足约束条件的解才是可行解, 只有满足目标函数的解才是最优解。这就有可能使需要搜索的空间大为压缩。,从根结点出发沿子结点向下搜索。若它和子结点的边所记
4、的分量xi满足约束条件和目标函数的界, 则把xi加入到部分解中, 并继续向下搜索; 若它和子结点的边所记的分量xi不满足约束条件和目标函数的界, 则结束对以子结点为根的整棵子树的搜索, 选择另一子结点进行搜索。,搜索过程中的结点分为三类:l_结点(活结点): 所搜索到的结点不是叶结点, 且满足约束条件和目标函数的界, 其儿子结点还未全部搜索完毕;e_结点(扩展结点): 正在搜索其儿子结点的结点, 它也是一个l_结点.d_结点(死结点): 不满足约束条件或目标函数的结点; 其儿子结点已搜索完毕的结点; 叶结点。以d_结点为根的子树可在搜索过程中删除。,例7.1 有4个顶点的货郎问题（有向赋权图）
5、, 其费用矩阵如图所示, 求从顶点1出发最后回到顶点1的最短路线。,7.1.3 回溯法的一般性描述 问题的解向量: X=(x0, x1, xn-1)xi的取值范围为Si, Si=(ai,0, ai,1, , ai,mi) 故解空间为笛卡尔积A=S0S1Sn-1 状态空间树可看成为一棵高度为n的树: 第0层: |S0|=m0个分支结点,构成m0棵子树,每棵子树有|S1|=m1个分支结点; 第1层: m0m1个分支结点, m0m1棵子树; 第n-1层: m0m1 mn-1个叶结点,回溯法的一般步骤: 初始化, 令解向量X为空; 从根结点出发, 在第0层选择S0的第一个元素a0,0作为解向量X的第一
6、个元素, 即置x0=a0,0; 若X=(x0)是部分解, 则该结点是l_结点, 也是e_结点, 选择S1的第一个元素a1,0作为X的第二个元素, 即置x1=a1,0;,(4)若X=(x0,x1)是部分解, 则该结点是l_结点, 也是e_结点, 置x2=a2,0;若X=(x0,x1)不是部分解, 则该结点是d_结点, 舍弃以该结点为根的子树, 取S1的下一元素a1,1作为X的第二个元素, 即x1=a1,1。以此类推。,一般地, 若已检测到X=(x0,x1, , xi)是问题的部分解, 在把xi+1=ai+1,0扩展到X时, 有以下三种情况:,若X=(x0,x1, , xi+1)是最终解, 则把它
7、作为有效解保存。若只需一个解, 则结束, 否则继续搜索其它有效解; 若X=(x0,x1, , xi+1)是部分解, 则令xi+2=ai+2,0, 继续搜索其下层子树;,(3)若X=(x0,x1, , xi+1)既不是最终解, 也不是部分解, 则有下述两种情况: a.若xi+1=ai+1,k不是Si+1的最后元素, 则令xi+1=ai+1,k+1, 继续搜索其兄弟子树;b.若xi+1=ai+1,k是Si+1的最后元素, 则回溯到X=(x0,x1, , xi)的情况。若此时xi=ai,k不是Si的最后元素, 则令xi=ai,k+1, 搜索上一层兄弟子树; 若此时xi=ai,k是Si的最后元素, 则
8、继续回溯到X=(x0,x1, , xi-1)。,用mi表示集合Si的元素数, |Si|=mi; 用xi表示向量X的第i个分量; 用ki表示对Si中元素的取值位置。回溯法的一般性描述如下:,void backtrack_item() initial(x); i=0; ki=0; flag=False;while (i=0) while (kimi) /*不是最后元素*/xi = a(i, ki);if (constrain(x) /*无解*/ ,回溯法的求解步骤: 1. 对所给问题, 定义问题的解空间; 2. 确定状态空间树的结构; 子集树 或 排列树 3. 用深度优先搜索方法搜索解空间, 用约
9、束方程和目标函数的界对状态空间树进行修剪, 生成搜索树, 取得问题的解。,8-皇后问题: 在88的棋盘上放置8个皇后, 使其不在同一行、同一列或斜率为1的同一斜线上。n-皇后问题: 在nn的棋盘上放置n个皇后, 使其不在同一行、同一列或斜率为1的同一斜线上。,7.2 n后问题,7.2.1 4-皇后问题的求解过程 1. 4-皇后问题的解空间 向量X=(x1, x2, x3, x4), 其中xi表示第i行皇后的列位置,xi的取值范围Si = 1,2,3,4,有nn种可能解,例如, 向量(2,4,3,1)和(1,4,2,3)对应于图(a)、图(b)的皇后布局。这两种布局都不满足问题的要求。,2. 4
10、-皇后问题的状态空间树:4叉完全树4-皇后问题的约束方程:xi xj, 1i4, 1j4, ij|xi-xj| |i-j| , 1i4, 1j4, ij这就把44种可能解压缩成4!。4后问题状态空间树如下图所示:,3. 4-皇后问题的搜索过程,4-皇后问题的一个有效布局:,7.2.2 n后问题的算法实现 函数place判断皇后所处位置的正确性 Bool place(int x, int k) int i; /判断在其之前的for (i=1; i0) xk=xk+1; /从1开始while (xk=n) ,时间复杂性分析: 运行时间取决于所访问结点个数c。 每访问一个结点, 调用一次place函
11、数计算约束方程; place函数循环体的执行次数最少1次, 最多n-1次。因此, 总次数为O(cn)。 结点个数是动态生成的, 对不同实例具有不确定性。一般为n的多项式。,4后问题的搜索树:,在4叉完全树中, 结点总数为1+4+16+64+256=341 用回溯法处理时, c=27, 约为前者的8% 实际模拟表明: 当n=8时, 被访问的结点数与结点总数之比约为1.5%。 在最坏情况下的花费是O(nn)。 算法需用一个具有n个分量的向量存放解向量, 故所需工作空间为(n)。,用m种颜色为无向图G=(V,E)的每个顶点着色, 要求每个顶点着一种颜色、并使相邻两个顶点之间具有不同颜色, 该问题称为
12、图的着色问题。,7.3 图的着色问题,1. 图着色问题的解空间V的顶点个数为n。m种颜色 解向量为n元组(c1, c2, cn), ci1,2,m, 1in例如, 5元组(1,3,2,3,1)表示对5顶点图的一种着色用m种颜色给n顶点图着色, 有mn种可能的着色组合。,7.3.1 图着色问题的求解过程,2. 图着色问题的状态空间树 高度为n的完全m叉树。树的高度指从根结点到叶结点的最长通路的长度;每个分支结点都有m个儿子结点;最底层有mn个叶结点。,3顶点图的3着色问题的状态空间树:,3. 图着色问题的搜索过程 约束方程: 若顶点i与j邻接, 则xixj 例7.2 对图(a)三着色,数据结构:
13、 int n; /*顶点个数*/ int m; /*最大颜色数*/ int k; /*顶点号,搜索深度*/ int xn; /*顶点的着色*/ Bool cnn; /*布尔值的邻接矩阵*/函数ok: 判断顶点着色的有效性 有效返回true, 无效返回false,7.3.2 图的m着色问题的算法实现,1. Bool ok(int x, int k, Bool c, int n) 2. int i; 3. for (i=0; ik; i+) 4. if (cki 7. ,算法7.2 用m种颜色为图着色 输入: n, m, c; 输出: 着色x 1.void m_c(int n, int m, int x,Bool c) 2.int i,k;/k标记第几个点 3. for (i=0; i=0) 6. xk = xk+1; 7. while(xk=m) ,状态空间树的结点总数为:,每访问一个结点, 调用一次ok函数计算约束方程。ok函数循环体的执行次数最少1次, 最多n-1次。 在最坏情况下, 算法总花费为O(nmn) 被访问的结点数远低于状态空间树的总结点数。若不考虑输入所占空间, 需(n)的空间存放解向量。,
