图的m着色开题报告

PAGE毕业设计开题报告学生姓名：学号：学院、系：专业：计算机科学与技术设计题目：图的m着色问题研究及动态演示指导教师20

毕业设计开题报告1．结合毕业设计情况，根据所查阅的文献资料，撰写2000字左右的文献综述：文献综述课题研究的现状图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。1852年，毕业于伦敦大学的弗南西斯·格思里提出了任何地图都可以4中颜色来着色的4色猜想问题。过了100多年，电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程，在1976年6月，美国伊利诺大学哈肯与阿佩尔合作编制一个很好的程序在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明，轰动了世界[1]。目前解决该问题的算法很多，如回溯算法、分支界定法、Welsh-Powell算法、布尔代数法、蚁群算法、贪婪算法、禁忌搜索算法、神经网络、遗传算法以及模拟退火算法等。通常的解决着色问题的算法采用蛮力法、贪婪法、深度优先或广度优先等思想可以得到最优解，但时间复杂性太大，如回溯法，其计算时间复杂性为指数阶的；有的在多项式时间内能得到可行解，但不是最优解，如Welsh-Powell算法和贪婪算法。Welsh-Powell算法只能保证最多使用(为图中顶点的最大度)种颜色给一个图正常着色，而由Brooks定理，对于既不是完全图又不是奇圈的简单连通图，所需的颜色数。故通常的算法在解决图节点着色问题这样的NP完全问题时，存在很大的瓶颈，难以得到满意的结果。而对于像遗传算法和神经网络这样复杂的启发式算法，通常算法本身复杂性较大，并且算法效率难以分析，最终得到的是近似解，其是否最优解也不能保证。其中回溯法求解图着色的过程是：首先把所有顶点的颜色初始化为0，然后依次为每个顶点着色。如果其中i个顶点已经着色，并且相邻两个顶点的颜色都不一样，就称当前的着色是有效的局部着色；否则，就称为无效的着色。如果由根节点到当前节点路径上的着色，对应于一个有效着色，并且路径的长度小于n，那么相应的着色是有效的局部着色。这时，就从当前节点出发，继续探索它的儿子节点，并把儿子结点标记为当前结点。在另一方面，如果在相应路径上搜索不到有效的着色，就把当前结点标记为d_结点，并把控制转移去搜索对应于另一种颜色的兄弟结点。如果对所有m个兄弟结点，都搜索不到一种有效的着色，就回溯到它的父亲结点，并把父亲结点标记为d_结点，转移去搜索父亲结点的兄弟结点。这种搜索过程一直进行，直到根结点变为d_结点，或者搜索路径长度等于n，并找到了一个有效的着色为止[2]。课题研究的意义图的m着色只是各色算法中的一种，算法是一个全新的课题,已经成为计算机科学的核心,它在科学技术和社会发展中起着越来越重要的作用。算法的思想和初步知识,也正在成为普通公民的常识。算法(algorithm)一词源于算术(algorism)。精略地说,算术方法是一个由已知推求未知的运算过程。后来,人们把它推广到一般，把进行某一工作的方法和步骤称为算法。“计算机既是数学的创造物，又是数学的创造者”，而算法既是计算机理论和实践的核心，也是数学的最基本内容之一。甚至有人说，数学学习的主要作用是形成“算法思维”。算法有着悠久的发展历史，中国古代数学曾经以算法为特色，取得了举世瞩目的辉煌成就。在已经逐步进入信息化社会的今天，算法的基本知识、方法、思想日益融入人们社会生活的方方面面，已经也应该成为现代人所应具备的一种基本素质。算法学习有助于我们全面的理解运算能力，习能够培养学生的逻辑思维能力在算法学习中。研究一个问题的不同算法，并比较这些算法的优劣，并作出选择，从而提高效率，而这个过程才是一个真正的运算过程，因此算法学习使得我们更加全面的理解运算能力。我们常常说数学是思维的体操，能够训练学生的思维能力。算法作为数学的一个基本内容，在培养学生的逻辑思维能力上能够发挥重要的作用。算法是解题方法的精确描述。算法一方面具有具体化、程序化、机械化的特点，同时又有高度抽象性、概括性和精确性。因此，将解决具体问题的方法整理成算法的过程是一个条理化，精确化和逻辑化的过程，有助于培养学生的逻辑思维能力[3]。现而今算法已与我们的生活密不可分，复杂的数学问题和纷杂的生活问题中都有它的影子，大到卫星的发射小到日程的安排都有各种算法充斥其中，图的m着色算法只是我们更加了解它的一个钥匙。3.课题研究的目标使用C++语言以及VC++6.0编程工具完成图的m着色问题研究及动态演示，使之生动、易懂，加深对算法的理解，明白算法对于程序开发的意义。增加使用C++语言开发程序的经验，熟练VC++6.0编程工具的使用。C++是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。C++是有C语言演化而来的，当C语言发展到顶峰的时刻，出现了一个版本叫CwithClass，那就是C++最早的版本，在C语言中增加class关键字和类，那个时候有很多版本的C都希望在C语言中增加类的概念；后来C标准委员会决定为这个版本的C起个新的名字，那个时候征集了很多种名字，最后采纳了其中一个人的意见，以C语言中的++运算符来体现它是C语言的进步，故而叫C++，成立了C++标准委员会[15]。VC++6.0是Microsoft公司推出的一个基于Windows系统平台、可视化的集成开发环境，它的源程序按C++语言的要求编写，并加入了微软提供的功能强大的MFC(MicrosoftFoundationClass)类库。MFC中封装了大部分WindowsAPI函数和Windows控件，它包含的功能涉及到整个Windows操作系统。MFC不仅给用户提供了Windows图形环境下应用程序的框架，而且还提供了创建应用程序的组件，这样，开发人员不必从头设计创建和管理一个标准Windows应用程序所需的程序，而是从一个比较高的起点编程，故节省了大量的时间。另外，它提供了大量的代码，指导用户编程时实现某些技术和功能。因此，使用VC++提供的高度可视化的应用程序开发工具和MFC类库，可使应用程序开发变得简单[4]。参考文献：[1]黄睿·图的m着色·重庆职业技术学院学报，2006,15（1）：1～3[2]李文，王哲明，刘林·图顶点m着色的改进算法·天津理工学院学报，1998,14（3）：59～62[3]李亚玲·算法及其学习的意义·北京师范大学数学通报，2004,2：7～8[4]孙鑫，余安萍﹒VC++深入详解﹒北京：电子工业出版社，2006﹒10[5]李颂华，康会华﹒VisualC++2005入门经典﹒北京：清华大学出版社，2007﹒6[6]李言，李伟明，李贺﹒VisualC++项目开发全程实录﹒北京：清华大学出版社，2008﹒60[7]郑阿奇·VisualC++实用教程（第2版）·北京：电子工业出版社，2003·56[8]DavidJ.Kruglinski,潘爱民,王国印译·VisualC++技术内幕（第四版）·北京：清华大学出版社，1999·64[9]魏亮,李春葆编著·VisualC++程序设计例学与实践·清华大学出版社，2006·121[10]刘瑞，吴跃进，王宗越·VisualC++项目开发实用案例·北京：科学出版社，2006·154[11]荣钦科技·VISUALC++游戏设计·北京：北京科海电子出版社，2005·127[12]罗伟坚·VisualC++经典游戏程序设计·北京：人民邮电出版社，2006·97[13]严华峰等·VISUALC++课程设计案例精编(第二版)·北京：中国水利水电出版社，2004·176[14]李光明·VisualC++6.0经典实例大制作·北京：中国人事出版社，2001·193[15]钱能·C++程序设计教程·北京：清华大学出版社，1999·112

毕业设计开题报告２．本课题要研究或解决的问题和拟采用的研究手段（途径）：1.要研究或解决的问题：(1).研究回溯算法基本设计思想。(2).理解图的m着色问题的描述及实现方法。(3).动态演示算法的的实现过程。2.研究手段：(1).介绍溯算法以及图的m着色问题。(2).采用回溯法实现图的m着色的求解。(3).使用面向对象的程序设计方法，选取C++程序设计语言及VC++6.0编程工具实现可课题的设计。

毕业设计开题报告指导教师意见：1．对“文献综述”的评语：同学在文献综述中，对图的着色问题的历史、求解的思路和方法进行了研究与讨论，对采用回溯法求解图的着色问题进行了深入的分析，并对实现该课题采用的C++语言进行综述。总的来看，文献综述反应了采用回溯法求解图的着色问题的基本思想和方法，相关内容的阐述也较为详细准确。另外，文献数量和格式也符合规范要求。2．对本课题的深度、广度及工作量的意见和对设计结果的预测：课题深度及广度：图的着色问题是由地图的着色问题引申而来的，目前有许多的算法实现，其中回溯法是其中较为经典的算法，理解并实现该算法难度不大。本课题除了实现算法外，还要对算法过程进行生动形象的动态演示，以帮助理解问题求解的步骤和过程，因此该课题仍需对此部分进行详细的分析和设计。课题工作量：本课题首先需要对图的着色问题进行理解，并学习回溯算法解决问题的方法并最终实现问题的求解。此外还需对求解过程进行动态演示，采用VC++实现。其深度、广度能达到毕业设计的要求，并有一定的工作量。结果预测：从开题报告的论述中，可以看出该同学应该能实现图的着色问题的回溯算法的求