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]?，F而今算法已與我們的生活密不可分，復雜的數學問題和紛雜的生活問題中都有它的影子，大到衛星的發射小到日程的安排都有各種算法充斥其中，圖的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]黃?！D的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++實現。其深度、廣度能達到畢業設計的要求，并有一定的工作量。結果預測：從開題報告的論述中，可以看出該同學應該能實現圖的著色問題的回溯算法的求