算法設(shè)計與分析課程設(shè)計任務(wù)書

1、課程設(shè)計算法設(shè)計與分析課程設(shè)計任務(wù)書年級： 2007學(xué)院名稱： 數(shù)學(xué)與計算機學(xué)院 專業(yè)： 信息與計算科學(xué)專業(yè)一、設(shè)計題目用回溯法求解一般哈密爾頓回路問題、主要內(nèi)容給出內(nèi)存分類法的多種應(yīng)用，給出這些應(yīng)用對應(yīng)的算法并編程實現(xiàn)。三、具體要求(1) 給出各種分類法的求解算法 ;(2) 編程實現(xiàn)各種分類法的算法 ;(3) 對所寫的每個算法給出時空復(fù)雜性分析。四、主要技術(shù)路線提示1、回溯法的主要思想是每次只構(gòu)造解的一個分量，然后按照下面的方法來評估這個部分構(gòu)造解。 如果一個部分構(gòu)造解可以進一步構(gòu)造而不會違反問題的約束， 我們就接受對解的下一個分量所 做的第一個合法選擇。 如果無法對下一個分量進行合法選擇，

2、 就不必對剩下的任何分量再做任 何選擇了。在這種情況下，該算法進行回溯，把部分構(gòu)造解的最后一個分量替換為他的下一個 選擇。2、設(shè)計回溯法的步驟(1) 對所做的選擇構(gòu)造一棵所謂的狀態(tài)空間數(shù)。(2) 如果一個部分構(gòu)造解仍然有可能導(dǎo)致一個完整解，我們說這個部分解在樹中的相應(yīng)結(jié)點是有希望的；否則，我們說他是沒希望的。(3) 一個回溯法的狀態(tài)空間樹是按照深度優(yōu)先的方式來構(gòu)造的。(4) 最后，如果該算法找到了問題的一個完整解， 它要么就停止了， 要么繼續(xù)查找其他可能的解。3、哈密頓路徑問題在上世紀(jì)七十年代初，終于被證明是“ NP 完備”的。據(jù)說具有這樣性課程設(shè)計100 的網(wǎng)絡(luò)，利用質(zhì)的問題，難于找到一個有

3、效的算法。實際上對于某些頂點數(shù)不到 現(xiàn)有最好的算法和計算機也需要比較荒唐的時間（比如幾百年）才能確定其是否存在 一條這樣的路徑。從圖中的任意一點出發(fā)， 路途中經(jīng)過圖中每一個結(jié)點當(dāng)且僅當(dāng)一次， 則成為哈密頓回路。 要滿足兩個條件：1. 封閉的環(huán)2. 是一個連通圖，且圖中任意兩點可達 經(jīng)過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為哈密頓通路。 經(jīng)過圖中所有頂點一次且僅一次的回路稱為哈密頓回路。具有哈密頓回路的圖稱為 哈密頓圖 ，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈 密頓圖。平凡圖是哈密頓圖。4、針對算法實現(xiàn)，要求掌握算法的思想和原理，通過編程語言（VC 、 VB 、Java 等均

4、可）實現(xiàn)算法。5、具體算法和方案可參考任務(wù)書后相關(guān)參考文獻。五、進度安排1、第一周 :分析題目的需求，設(shè)計抽象數(shù)據(jù)類型、構(gòu)思算法、通過類的設(shè)計實現(xiàn)抽象數(shù)據(jù)類型并編 寫上機程序2、第二周 完成程序開發(fā)，進行測試并分析結(jié)果，最后撰寫課程設(shè)計報告六、完成后應(yīng)上交的材料上交的成果的內(nèi)容必須由以下四個部分組成，缺一不可。 1上交源程序：學(xué)生按照課程設(shè)計的具體要求所開發(fā)的所有源程序（應(yīng)該放到一個文件夾中）。2上交程序的說明文件： （保存在 .txt 中），在說明文檔中應(yīng)該寫明上交程序所在的目錄，上交程序 的主程序文件名，如果需要安裝，要有程序的安裝使用說明。3 課程設(shè)計報告電子文檔： （保存在 word

5、文檔中，文件名要求 按照“學(xué)號姓名算法分析課設(shè)報 告 .doc”起名，如文件名為“ 200300109 張三算法分析課設(shè)報告 .doc” ），按照課程設(shè)計的具體要求建立 的功能模塊，每個模塊要求按照如下幾個內(nèi)容認(rèn)真完成：其中包括：（ 1）需求分析：在該部分中敘述每個模塊的功能要求等。（ 2）概要設(shè)計在此說明每個部分的算法設(shè)計說明（可以是描述算法的流程圖） ，每個程序中使用的存儲結(jié)構(gòu)設(shè)計 說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義。（ 3）詳細(xì)設(shè)計 各個算法實現(xiàn)的源程序，對每個題目要有相應(yīng)的源程序（可以是一組源程序，每個功能模塊采用不 同的函數(shù)實現(xiàn)） 。源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰課程設(shè)計的程序注釋。（ 4）調(diào)試分析 包括測試數(shù)據(jù)，測試輸出的結(jié)果，時間復(fù)雜度分析，和每個模塊設(shè)計和調(diào)試時存在問題的思考（問 題是哪些？問題如何解決？） ，算法的改進設(shè)想。（ 5）課設(shè)總結(jié)總結(jié)可以包括 ：課程設(shè)計過程的收獲、遇到問題、遇到問題解決問題過程的思考、程序調(diào)試能力 的思考、對算法設(shè)計與分析這門課程的思考、在課程設(shè)計過程中對算法設(shè)計與分析課程的認(rèn)識等內(nèi) 容。4課程設(shè)計報告打印稿。七、推薦參考資料教 材：算法設(shè)計與分析