lecutre_12回溯法1.ppt

第13章回溯法 一种组织有哪些信誉好的足球投注网站的一般技术，也有“问题的通用解法”之称。 著名的平面图的四色猜想：在一个平面或球面上的任何地图能够只用4种颜色来着色，使得相邻的国家在地图上有不同颜色。 这里假设每个国家在地图上必须是单连通的，两个国家相邻指的是这2个国家有一段长度不为0的边界，而不是只有一个公共点。 1976年借助计算机将四色猜想变成了四色定理 一个满足以上假设的地图可转化为一个平面图G=(V,E)。 平面图的区域着色问题就转变成了对一个无向连通图G=(V,E)的顶点着色问题: 给定无向连通图G=(V,E)和3种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。 寻求解的过程——回溯红：1 黄：2 兰：3 Backtrack( int L[N][N],int x[N], int t) {//前t-1个顶点已着色，给第t个以后的顶点着色 if (tn) { 得到一个解，flag=1;exit; } else for (int i=1;i=3;i++) {//尝试所有颜色i （1）对顶点t着颜色i； （2）若与前面的t-1个顶点颜色不冲突， 则对其余顶点着色（递归调用自身）； 否则，尝试下一种颜色； } } Backtrack( int L[N][N],int x[N], int t) {//前t-1个顶点已着色，给第t个以后的顶点着色 if (tn) { 得到一个解，flag=true; exit; } else for (int i=1;i=3;i++) { x[t]=i; //对顶点t着颜色i if (Ok(L，x，t)) Backtrack(t+1); } } 课堂作业：请写出着色合法性检验函数 Int Ok(int L[N][N],int x[N], int t) {// 检查颜色可用性 for (int j=1;jt;j++) if ((L[t][j]==1)(x[j]==x[t])) return false; return true; } Backtrack( int L[N][N],int x[N], int t) { if (tn) { //得到一个解，输出数组x;flag=true; } else for (int i=1;i=3;i++) { x[t]=i; if (Ok(L，x，t)) Backtrack(t+1); } } 3着色问题的非递归算法 void 3_Colorrec(int L[N][N],int x[N]) {1、x数组初始化为0 2、flag=0;t=1; 3、while(t=1) //当第一个顶点尝试完所有的颜色时，t会变为0 4、 {x[t]++; 5、 while(顶点t没有试遍所有颜色且目前颜色x[t]不合法） 顶点t取下一种颜色 （ x[t]+ +）； 6 、 if(顶点t有合法着色) 7、 if(t已是第n个顶点） 则得到一个合法着色方案输出方案，终止程序； 8、 else //只是的到部分解 t++; //为下一个顶点寻找合法着色 9、 else //顶点t试遍所有颜色，都不合法 {x[t]=0;t—;} //回上一行 } 3着色问题的非递归算法 void 3_Colorrec(int L[N][N],int x[N]) {1、x数组初始化为0 2、flag=0;t=1; 3、While(t=1) 4、 {x[t]++; 5、 while(x[t]=3 !ok(L,x,t)） x[t]+ +； 6 、 if(x[t]=3) 7、 if(t=n） 则得到一个合法着色方案输出方案，终止程序； 8、 else //只是的到部分解 t+