计算科学与数学系.ppt

计算科学与数学系 Algorithms Design and Analysis 计算科学与数学系 第七章 回溯法 理解回溯法的深度优先有哪些信誉好的足球投注网站策略。 掌握用回溯法解题的算法框架 （1）递归回溯最优子结构性质 （2）迭代回溯贪心选择性质 （3）子集树算法框架 （4）排列树算法框架 else k=k+1 //转下一行，即给下一个皇后找位置 x[k]=0 //初始化当前皇后列取值 else k=k-1 //回溯 return n后问题 PLACE(k) i=1 while (ik) do if (x[i]=x[k] or abs(x[i]-x[k])=abs(i-k) //同一列或同一斜线 then return(false) i=i+1 return(true) n后问题 4皇后问题解空间的树结构 n后问题 n后问题 n后问题 算法分析： 对于一般的n皇后问题，由于没有两个皇后能放在同一列上，则解向量必须是数1,2,…,n的一个排列，这样，回溯法可以改进为测试n!种布局而不是nn种。其实回溯法极大低减少了测试的次数。 图的m着色问题 问题描述： 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的两个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图至少需要m种颜色才能使图中每条边连接的两个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的可着色优化问题。 图的m着色问题 四色猜想（四色问题）：世界近代三大数学难题之一 四色问题的内容：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。用数学语言表示即：将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。 图的m着色问题 四色猜想（四色问题）： 提出来自于英国，1852年，毕业于伦敦大学的弗南西斯.格思 里提出了四色猜想的这一基本问题； 1852年11月23日，他的弟弟格里斯请教他的老师，著名数学 家德·摩尔根，德·摩尔根写信向自己的好友、著名数学家哈 密尔顿爵士请教，直到1865年哈密尔顿逝世，问题也没能解决。 1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提 出了这个问题，于是四色猜想成了世界数学界关注的问题。 1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分 别提交了证明四色猜想的论文，宣布证明了四色定理 图的m着色问题 1890年，在牛津大学就读的年仅29岁的赫伍德以自己的精确计算指出了肯普在证明上的漏洞。不久，泰勒的证明也被人们否定 1939年美国数学家富兰克林证明了22国以下的地图都可以用四色着色，1950年，有人从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。 从1936年就开始研究四色猜想的海克，公开宣称四色猜想可用寻找可约图形的不可避免组来证明。 美国伊利诺大学哈肯在1970年着手改进“放电过程”，后与阿佩尔合作编制一个很好的程序。就在1976年6月，他们在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明，轰动了世界 图的m着色问题 算法设计： 用图的邻接矩阵a表示无向连通图G=(V,E)，若(i,j)属于图G=(V,E)的边集E，则a[i][j]=1，否则a[i][j]=0。整数1,2,..,m用来表示m种不同颜色。顶点i所着颜色用x[i]表示。数组x[1:n]是问题的解空间。问题的解空间可以表示为一棵高度为n+1的完全m叉树。解空间树的第i(1≤i≤n)层中每一个结点都有m个儿子，每个儿子对应于x[i]的m个可能的着色之一。第n+1层结点均为叶结点。 图的m着色问题 图的m着色问题 算法： private void backtrack(int t) //t表示深度 { if(tn) { // n图的顶点数 sum++; //记录已找到的可m着色方案数 for(int i=1;i=n;i++) printf(x[i]+” ”); //记录当前解 } else for (int i=1;i=m;i++) { 图的m着色问题 x[t]=i;