圖的m著色開題報(bào)告

PAGE畢業(yè)設(shè)計(jì)開題報(bào)告學(xué)生姓名：學(xué)號(hào)：學(xué)院、系：專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)設(shè)計(jì)題目：圖的m著色問題研究及動(dòng)態(tài)演示指導(dǎo)教師20

畢業(yè)設(shè)計(jì)開題報(bào)告1．結(jié)合畢業(yè)設(shè)計(jì)情況，根據(jù)所查閱的文獻(xiàn)資料，撰寫2000字左右的文獻(xiàn)綜述：文獻(xiàn)綜述課題研究的現(xiàn)狀圖的著色問題是由地圖的著色問題引申而來的：用m種顏色為地圖著色，使得地圖上的每一個(gè)區(qū)域著一種顏色，且相鄰區(qū)域顏色不同。如果把每一個(gè)區(qū)域收縮為一個(gè)頂點(diǎn)，把相鄰兩個(gè)區(qū)域用一條邊相連接，就可以把一個(gè)區(qū)域圖抽象為一個(gè)平面圖。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯·格思里提出了任何地圖都可以4中顏色來著色的4色猜想問題。過了100多年，電子計(jì)算機(jī)問世以后，由于演算速度迅速提高，加之人機(jī)對話的出現(xiàn)，大大加快了對四色猜想證明的進(jìn)程，在1976年6月，美國伊利諾大學(xué)哈肯與阿佩爾合作編制一個(gè)很好的程序在美國伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上，用了1200個(gè)小時(shí)，作了100億判斷，終于完成了四色定理的證明，轟動(dòng)了世界[1]。目前解決該問題的算法很多，如回溯算法、分支界定法、Welsh-Powell算法、布爾代數(shù)法、蟻群算法、貪婪算法、禁忌搜索算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法以及模擬退火算法等。通常的解決著色問題的算法采用蠻力法、貪婪法、深度優(yōu)先或廣度優(yōu)先等思想可以得到最優(yōu)解，但時(shí)間復(fù)雜性太大，如回溯法，其計(jì)算時(shí)間復(fù)雜性為指數(shù)階的；有的在多項(xiàng)式時(shí)間內(nèi)能得到可行解，但不是最優(yōu)解，如Welsh-Powell算法和貪婪算法。Welsh-Powell算法只能保證最多使用(為圖中頂點(diǎn)的最大度)種顏色給一個(gè)圖正常著色，而由Brooks定理，對于既不是完全圖又不是奇圈的簡單連通圖，所需的顏色數(shù)。故通常的算法在解決圖節(jié)點(diǎn)著色問題這樣的NP完全問題時(shí)，存在很大的瓶頸，難以得到滿意的結(jié)果。而對于像遺傳算法和神經(jīng)網(wǎng)絡(luò)這樣復(fù)雜的啟發(fā)式算法，通常算法本身復(fù)雜性較大，并且算法效率難以分析，最終得到的是近似解，其是否最優(yōu)解也不能保證。其中回溯法求解圖著色的過程是：首先把所有頂點(diǎn)的顏色初始化為0，然后依次為每個(gè)頂點(diǎn)著色。如果其中i個(gè)頂點(diǎn)已經(jīng)著色，并且相鄰兩個(gè)頂點(diǎn)的顏色都不一樣，就稱當(dāng)前的著色是有效的局部著色；否則，就稱為無效的著色。如果由根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)路徑上的著色，對應(yīng)于一個(gè)有效著色，并且路徑的長度小于n，那么相應(yīng)的著色是有效的局部著色。這時(shí)，就從當(dāng)前節(jié)點(diǎn)出發(fā)，繼續(xù)探索它的兒子節(jié)點(diǎn)，并把兒子結(jié)點(diǎn)標(biāo)記為當(dāng)前結(jié)點(diǎn)。在另一方面，如果在相應(yīng)路徑上搜索不到有效的著色，就把當(dāng)前結(jié)點(diǎn)標(biāo)記為d_結(jié)點(diǎn)，并把控制轉(zhuǎn)移去搜索對應(yīng)于另一種顏色的兄弟結(jié)點(diǎn)。如果對所有m個(gè)兄弟結(jié)點(diǎn)，都搜索不到一種有效的著色，就回溯到它的父親結(jié)點(diǎn)，并把父親結(jié)點(diǎn)標(biāo)記為d_結(jié)點(diǎn)，轉(zhuǎn)移去搜索父親結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。這種搜索過程一直進(jìn)行，直到根結(jié)點(diǎn)變?yōu)閐_結(jié)點(diǎn)，或者搜索路徑長度等于n，并找到了一個(gè)有效的著色為止[2]。課題研究的意義圖的m著色只是各色算法中的一種，算法是一個(gè)全新的課題,已經(jīng)成為計(jì)算機(jī)科學(xué)的核心,它在科學(xué)技術(shù)和社會(huì)發(fā)展中起著越來越重要的作用。算法的思想和初步知識(shí),也正在成為普通公民的常識(shí)。算法(algorithm)一詞源于算術(shù)(algorism)。精略地說,算術(shù)方法是一個(gè)由已知推求未知的運(yùn)算過程。后來,人們把它推廣到一般，把進(jìn)行某一工作的方法和步驟稱為算法?！坝?jì)算機(jī)既是數(shù)學(xué)的創(chuàng)造物，又是數(shù)學(xué)的創(chuàng)造者”，而算法既是計(jì)算機(jī)理論和實(shí)踐的核心，也是數(shù)學(xué)的最基本內(nèi)容之一。甚至有人說，數(shù)學(xué)學(xué)習(xí)的主要作用是形成“算法思維”。算法有著悠久的發(fā)展歷史，中國古代數(shù)學(xué)曾經(jīng)以算法為特色，取得了舉世矚目的輝煌成就。在已經(jīng)逐步進(jìn)入信息化社會(huì)的今天，算法的基本知識(shí)、方法、思想日益融入人們社會(huì)生活的方方面面，已經(jīng)也應(yīng)該成為現(xiàn)代人所應(yīng)具備的一種基本素質(zhì)。算法學(xué)習(xí)有助于我們?nèi)娴睦斫膺\(yùn)算能力，習(xí)能夠培養(yǎng)學(xué)生的邏輯思維能力在算法學(xué)習(xí)中。研究一個(gè)問題的不同算法，并比較這些算法的優(yōu)劣，并作出選擇，從而提高效率，而這個(gè)過程才是一個(gè)真正的運(yùn)算過程，因此算法學(xué)習(xí)使得我們更加全面的理解運(yùn)算能力。我們常常說數(shù)學(xué)是思維的體操，能夠訓(xùn)練學(xué)生的思維能力。算法作為數(shù)學(xué)的一個(gè)基本內(nèi)容，在培養(yǎng)學(xué)生的邏輯思維能力上能夠發(fā)揮重要的作用。算法是解題方法的精確描述。算法一方面具有具體化、程序化、機(jī)械化的特點(diǎn)，同時(shí)又有高度抽象性、概括性和精確性。因此，將解決具體問題的方法整理成算法的過程是一個(gè)條理化，精確化和邏輯化的過程，有助于培養(yǎng)學(xué)生的邏輯思維能力[3]?，F(xiàn)而今算法已與我們的生活密不可分，復(fù)雜的數(shù)學(xué)問題和紛雜的生活問題中都有它的影子，大到衛(wèi)星的發(fā)射小到日程的安排都有各種算法充斥其中，圖的m著色算法只是我們更加了解它的一個(gè)鑰匙。3.課題研究的目標(biāo)使用C++語言以及VC++6.0編程工具完成圖的m著色問題研究及動(dòng)態(tài)演示，使之生動(dòng)、易懂，加深對算法的理解，明白算法對于程序開發(fā)的意義。增加使用C++語言開發(fā)程序的經(jīng)驗(yàn)，熟練VC++6.0編程工具的使用。C++是一種靜態(tài)數(shù)據(jù)類型檢查的，支持多重編程范式的通用程序設(shè)計(jì)語言。它支持過程化程序設(shè)計(jì)、數(shù)據(jù)抽象、面向?qū)ο蟪绦蛟O(shè)計(jì)、制作圖標(biāo)等等泛型程序設(shè)計(jì)等多種程序設(shè)計(jì)風(fēng)格。C++是有C語言演化而來的，當(dāng)C語言發(fā)展到頂峰的時(shí)刻，出現(xiàn)了一個(gè)版本叫CwithClass，那就是C++最早的版本，在C語言中增加class關(guān)鍵字和類，那個(gè)時(shí)候有很多版本的C都希望在C語言中增加類的概念；后來C標(biāo)準(zhǔn)委員會(huì)決定為這個(gè)版本的C起個(gè)新的名字，那個(gè)時(shí)候征集了很多種名字，最后采納了其中一個(gè)人的意見，以C語言中的++運(yùn)算符來體現(xiàn)它是C語言的進(jìn)步，故而叫C++，成立了C++標(biāo)準(zhǔn)委員會(huì)[15]。VC++6.0是Microsoft公司推出的一個(gè)基于Windows系統(tǒng)平臺(tái)、可視化的集成開發(fā)環(huán)境，它的源程序按C++語言的要求編寫，并加入了微軟提供的功能強(qiáng)大的MFC(MicrosoftFoundationClass)類庫。MFC中封裝了大部分WindowsAPI函數(shù)和Windows控件，它包含的功能涉及到整個(gè)Windows操作系統(tǒng)。MFC不僅給用戶提供了Windows圖形環(huán)境下應(yīng)用程序的框架，而且還提供了創(chuàng)建應(yīng)用程序的組件，這樣，開發(fā)人員不必從頭設(shè)計(jì)創(chuàng)建和管理一個(gè)標(biāo)準(zhǔn)Windows應(yīng)用程序所需的程序，而是從一個(gè)比較高的起點(diǎn)編程，故節(jié)省了大量的時(shí)間。另外，它提供了大量的代碼，指導(dǎo)用戶編程時(shí)實(shí)現(xiàn)某些技術(shù)和功能。因此，使用VC++提供的高度可視化的應(yīng)用程序開發(fā)工具和MFC類庫，可使應(yīng)用程序開發(fā)變得簡單[4]。參考文獻(xiàn)：[1]黃?！D的m著色·重慶職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2006,15（1）：1～3[2]李文，王哲明，劉林·圖頂點(diǎn)m著色的改進(jìn)算法·天津理工學(xué)院學(xué)報(bào)，1998,14（3）：59～62[3]李亞玲·算法及其學(xué)習(xí)的意義·北京師范大學(xué)數(shù)學(xué)通報(bào)，2004,2：7～8[4]孫鑫，余安萍﹒VC++深入詳解﹒北京：電子工業(yè)出版社，2006﹒10[5]李頌華，康會(huì)華﹒VisualC++2005入門經(jīng)典﹒北京：清華大學(xué)出版社，2007﹒6[6]李言，李偉明，李賀﹒VisualC++項(xiàng)目開發(fā)全程實(shí)錄﹒北京：清華大學(xué)出版社，2008﹒60[7]鄭阿奇·VisualC++實(shí)用教程（第2版）·北京：電子工業(yè)出版社，2003·56[8]DavidJ.Kruglinski,潘愛民,王國印譯·VisualC++技術(shù)內(nèi)幕（第四版）·北京：清華大學(xué)出版社，1999·64[9]魏亮,李春葆編著·VisualC++程序設(shè)計(jì)例學(xué)與實(shí)踐·清華大學(xué)出版社，2006·121[10]劉瑞，吳躍進(jìn)，王宗越·VisualC++項(xiàng)目開發(fā)實(shí)用案例·北京：科學(xué)出版社，2006·154[11]榮欽科技·VISUALC++游戲設(shè)計(jì)·北京：北京科海電子出版社，2005·127[12]羅偉堅(jiān)·VisualC++經(jīng)典游戲程序設(shè)計(jì)·北京：人民郵電出版社，2006·97[13]嚴(yán)華峰等·VISUALC++課程設(shè)計(jì)案例精編(第二版)·北京：中國水利水電出版社，2004·176[14]李光明·VisualC++6.0經(jīng)典實(shí)例大制作·北京：中國人事出版社，2001·193[15]錢能·C++程序設(shè)計(jì)教程·北京：清華大學(xué)出版社，1999·112

畢業(yè)設(shè)計(jì)開題報(bào)告２．本課題要研究或解決的問題和擬采用的研究手段（途徑）：1.要研究或解決的問題：(1).研究回溯算法基本設(shè)計(jì)思想。(2).理解圖的m著色問題的描述及實(shí)現(xiàn)方法。(3).動(dòng)態(tài)演示算法的的實(shí)現(xiàn)過程。2.研究手段：(1).介紹溯算法以及圖的m著色問題。(2).采用回溯法實(shí)現(xiàn)圖的m著色的求解。(3).使用面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，選取C++程序設(shè)計(jì)語言及VC++6.0編程工具實(shí)現(xiàn)可課題的設(shè)計(jì)。

畢業(yè)設(shè)計(jì)開題報(bào)告指導(dǎo)教師意見：1．對“文獻(xiàn)綜述”的評語：同學(xué)在文獻(xiàn)綜述中，對圖的著色問題的歷史、求解的思路和方法進(jìn)行了研究與討論，對采用回溯法求解圖的著色問題進(jìn)行了深入的分析，并對實(shí)現(xiàn)該課題采用的C++語言進(jìn)行綜述?？偟膩砜?，文獻(xiàn)綜述反應(yīng)了采用回溯法求解圖的著色問題的基本思想和方法，相關(guān)內(nèi)容的闡述也較為詳細(xì)準(zhǔn)確。另外，文獻(xiàn)數(shù)量和格式也符合規(guī)范要求。2．對本課題的深度、廣度及工作量的意見和對設(shè)計(jì)結(jié)果的預(yù)測：課題深度及廣度：圖的著色問題是由地圖的著色問題引申而來的，目前有許多的算法實(shí)現(xiàn)，其中回溯法是其中較為經(jīng)典的算法，理解并實(shí)現(xiàn)該算法難度不大。本課題除了實(shí)現(xiàn)算法外，還要對算法過程進(jìn)行生動(dòng)形象的動(dòng)態(tài)演示，以幫助理解問題求解的步驟和過程，因此該課題仍需對此部分進(jìn)行詳細(xì)的分析和設(shè)計(jì)。課題工作量：本課題首先需要對圖的著色問題進(jìn)行理解，并學(xué)習(xí)回溯算法解決問題的方法并最終實(shí)現(xiàn)問題的求解。此外還需對求解過程進(jìn)行動(dòng)態(tài)演示，采用VC++實(shí)現(xiàn)。其深度、廣度能達(dá)到畢業(yè)設(shè)計(jì)的要求，并有一定的工作量。結(jié)果預(yù)測：從開題報(bào)告的論述中，可以看出該同學(xué)應(yīng)該能實(shí)現(xiàn)圖的著色問題的回溯算法的求