[设计郑宗汉郑晓明第7章+回溯.ppt

在4叉完全树中, 结点总数为 　　1+4+16+64+256=341 用回溯法处理时, c=27, 约为前者的8% 实际模拟表明: 当n=8时, 被访问的结点数与结点总数之比约为1.5%。 在最坏情况下的花费是O(nn)。 算法需用一个具有n个分量的向量存放解向量, 故所需工作空间为?(n)。 ? 用m种颜色为无向图G=(V,E)的每个顶点着色, 要求每个顶点着一种颜色、并使相邻两个顶点之间具有不同颜色, 该问题称为图的着色问题。 7.3 图的着色问题 1. 图着色问题的解空间 　V的顶点个数为n。m种颜色 　解向量为n元组(c1, c2,…, cn), 　　　　ci?{1,2,…,m}, ? 1?i?n 　例如, 5元组(1,3,2,3,1)表示对5顶点 　　　 图的一种着色 　用m种颜色给n顶点图着色, 　有mn种可能的着色组合。 7.3.1 图着色问题的求解过程 2. 图着色问题的状态空间树 　高度为n的完全m叉树。 　树的高度指从根结点到叶结点的 　　　最长通路的长度; 　每个分支结点都有m个儿子结点; 　最底层有mn个叶结点。 3顶点图的3着色问题的状态空间树: 3. 图着色问题的有哪些信誉好的足球投注网站过程 　约束方程: 　若顶点i与j邻接, 则 　x[i]?x[j] 例7.2 对图(a)三着色 数据结构:? int n; /*顶点个数*/ int m; /*最大颜色数*/ int k; /*顶点号,有哪些信誉好的足球投注网站深度*/ int x[n]; /*顶点的着色*/ Bool c[n][n]; /*布尔值的邻接矩阵*/ 函数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 (c[k][i] (x[k]==x[i]) 5. return False; 6. return Trur; 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; in; i++) {//初始化 x[i]=0; } k = 0; 5. while (k=0) { 6. x[k] = x[k]+1; 7. while((x[k]=m)(!ok(x,k,c,n))) 8. x[k] = x[k]+1; 9. if (x[k]=m) { 10. if (k==n-1) break; /*完成*/ 11. else k = k+1; } else {x[k]=0; k=k–1; } } }? 状态空间树的结点总数为: 每访问一个结点, 调用一次ok函数计算约束方程。ok函数循环体的执行次数最少1次, 最多n-1次。 在最坏情况下, 算法总花费为O(nmn) 被访问的结点数远低于状态空间树的总结点数。若不考虑输入所占空间, 需?(n)的空间存放解向量。? 第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,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!个叶