图的着色问题实验报告.doc

算法设计与分析基础实验报告院 系： 计算机科学与技术学院 专 业： 计算机科学与技术 班 级： 学 号： 姓 名： 指导教师： 重庆邮电大学目录1 题目简介1 1.题目名称1 2.题目背景1 3.题目理论描述1 4.书中题目22 算法的基本思想2 1.回溯法基本思想2 2.贪心法基本思想2 3.其他算法简介33 算法具体设计分析3 1.回溯法分析与设计3 2.贪心法分析与设计4 3.复杂度分析44 实验分析5 1.实验环境5 2.程序的执行及结果55 总结与心得116 代码11 1.C+代码11 2.JS核心代码13参考文献161 题目简介1. 题目名称 图的着色问题。2. 题目背景 早在19世纪中期，英国数学家就提出了地图着色问题：给地图的各地域着色，要使相邻的地域具有不同的颜色，至少需要多少种颜色。显然，3种颜色是不够的，例如图9.15中的4个地域至少要四种颜色才能作出满足上述要求的着色。另一方面，人们很快证明了，5种颜色是足够的。当时英国青年盖思里（Guthrie）提出，用4种颜色即可给地图着色，使相邻区域具有不同的颜色，但他未能加以证明。于是，这给后人留下了一个著名的难题四色问题，它至今未得到证实或否定。直到1976年这个问题才由爱普尔(kiapple)，黑肯(whaken)和考西(jkoch)利用电子计算机的帮助得以解决。他们证明了4种颜色足以对任何地图着色。 如图13. 题目理论描述已知一个图g和m0种颜色，在只准使用这m种颜色对g的结点着色的情况下，是否能使图中任何相邻的两个结点都具有不同的颜色呢?这个问题称为m-着色判定问题。在m-着色最优化问题则是求可对图g着色的最小整数m。这个整数称为图g的色数。这是求图的最少着色问题，求出m的值。4. 书中题目根据题目要求，此题数据来自算法设计与分析基础223页习题7的数据。但因为图着色问题是无向图，所以我们把它改写成无向矩阵（如图2）。 图22 算法的基本思想1. 回溯法基本思想回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。它是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。回溯法解题思路为：儿子结点标记为当前结点。在另一方面，如果在相应路径上搜索不到有效的着色，就把当前结点标记为d_结点，并把控制转移去搜索对应于另一种颜色的兄弟结点。如果对所有m个兄弟结点，都搜索不到一种有效的着色，就回溯到它的父亲结点，并把父亲结点标记为d_结点，转移去搜索父亲结点的兄弟结点。这种搜索过程一直进行，直到根结点变为d_结点，或者搜索路径长度等于n，并找到了一个有效的着色为止。2. 贪心法基本思想所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。贪心法解决问题的思路：选择一种颜色，以任意顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，则用颜色1为该顶点着色，当没有顶点能以这种颜色着色时，选择颜色2和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则选取颜色3并为尽可能多的顶点着色，依此类推。3. 其他算法简介求极小覆盖法布尔代数法，穷举法Welch Powell着色法，蚁群算法等。3 算法具体设计分析1. 回溯法分析与设计 设数组colorn表示顶点的着色情况，回溯法求解m着色问题的算法如下：图着色回溯法： （1）将数组colorn初始化为0；（2）k=1;（3）while (k=1) 依次考察每一种颜色，若顶点k的着色与其他顶点的着色不 发生冲突，则转步骤3.2；否则，搜索下一个颜色； 若顶点已全部着色，则输出数组colorn，返回； 否则， 若顶点k是一个合法着色，则k=k+1，转步骤3处理下一个顶点； 否则， 重置顶点k的着色情况，k=k-1，转步骤3。2. 贪心法分析与设计图着色贪心法：设数组colorn表示顶点的着色情况，贪心法求解图着色问题的算法如下： （1）color1=1; /顶点1着颜色1（2）for (i=2; i=n; i+) /其他所有顶点置未着色状态 colori=0;（3）k=0; （4）循环直到所有顶点均着色 k+; /取下一个颜色 for (i=2; i=n; i+) /用颜色k为尽量多的顶点着色 若顶点i已着色，则转上步骤，考虑下一个顶 点； 若图中与顶点i邻接的顶点着色与顶点i着颜色 k不冲突，则colori=k;3.复杂度分析图m可着色问题的解空间树中内结点个数是O(mn)，对于每一个内结点，在最坏情况下， 用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O( )。因此，回溯法总的时间耗费是 4 实验分析1. 实验环境（）软件平台操作系统：windows 7旗舰版编译软件：Microsoft Visual Studio 2012（） 硬件平台电脑型号：X86 兼容 笔记本处理器：Intel(R) Core(TM) i3-2330M内存：GB2. 程序的执行及结果根据书中邻接矩阵做出的如下（图）及运行结果：图图 图图因为输入三种颜色有六种解，最终如上图最终结果如图，输出在文件里。图附加：我们组还用和做了一程序，规定了四种颜色，但无向图自己确定（如图），以下是运行结果（如图）：图图 图5 总结与心得本次题目是我们选择的是图着色的问题，这是一个NP问题。设计到图的邻接顶点的访问和图的遍历。图的存储结构选择的是邻接矩阵的形式，在遍历图时是从第一个顶点开始，一次在定点数组中完成所有顶点的遍历，保证了全部的顶点都是可以访问到的。因为要对地图着色，所以着色是一个动态的过程，可以在遍历的过程中完成对地图的着色，每次访问一个结点，先赋值第一种颜色，如果和它的的邻接点的颜色不重复，则对下个顶点开始着色，否则本顶点的颜色转换到下一种，直到能够完成赋值。程序编写本身并不难，思路很清晰，就是赋值和比较之间的来回循环。写程序的时候查阅了着色问题，直到了这个问题是用计算机进行证明的，地图到目前为止还没有出现这个证明的反例；而且也明白了计算机在现代数学中的重要作用，因为如果没办法归纳证明，那就可以使用计算机进行穷举，只要穷举出来没有反例出现，则可以说明他没有问题。 在题目要求中说是中国地图，但是我们觉得为了程序的灵活性，应该能够对任意图进行着色，所以增加了建图的功能，使他可以对不同的图进行操作。 本次实验中巩固了我对图这种算法中回溯法和贪心法的认识，掌握了图的建立，图的数据的存取，在这块知识上的认识更加巩固了。6 代码 1.C+代码#include#includeusing namespace std;map node;int group66 = 0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,1,1,0,0,0,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0;int count = 0;void print()for(int i = 1; i 6; i+)cout nodei;count+;cout endl;void GCP(int i, int m)if(i = 6)print();return;for(int j = 1; j = m; j+)nodei = j;for(int k = 1; k = i; k+)if(groupik)if(nodek = nodei)nodei = 0;if(nodei = j)GCP(i+1, m);elsecontinue;int main()for(int i = 0; i = 5; i+)/初始化节点nodei = 0;cout *图的着色问题* endl;int m = 0;cout m;while(m 5 | m = 0)cout m;cout 着色的方案有: endl;GCP(1,m);cout 着色的方案共有 count 种。 endl;return 0;2. JS核心代码function ininEvent()var goButt = document.getElementById(go);var circleButton = document.getElementById(circle);var lineButton = document.getElementById(line);goButt.addEventListener(click,graphcolor);circleButton.addEventListener(click,function()/*resetButton();this.setAttribute(class,toolSelect);*/resetButton.call(this);controlTag = 1;);lineButton.addEventListener(click,function()resetButton.call(this);controlTag = 2;);var i=0;var container = document.getElementById(container);container.addEventListener(click,function()var mySvg = document.getElementById(mySvg);var svgLeft = mySvg.offsetLeft;var svgTop = mySvg.offsetTop;if(svgLeftevent.clientX&svgTopevent.clientY&event.clientX(svgLeft+800)&event.clientY=1)colorsk+;while(colorsk=m)if(ok(k)var obj = circleElesk-1;obj.setAttribute(fill,colorcolorsk);changeColor();break;elsecolorsk+;if(colorsk=m&k=DataArr.length)/ok/alert(colors.join();/alert(1);/sleep(2000);/alert();var mySvg = document.getElementById(mySvg);var svgTmp = mySvg.cloneNode(true);svgTmp.id=undefined;/svgTmp.setAttribute();/svgTmp.appendChild(mySvg.children);/var result = document.getElementById(result);result.appendChild(svgTmp);else if(colorsk=m&kDataArr.length)k = k+1;elsecolorsk = 0;var obj = circleElesk-1;obj.setAttribute