樹最大連通分支問題 說明書

1、數(shù)學(xué)與計算機學(xué)院課程設(shè)計說明書課 程 名 稱: 算法設(shè)計與分析-課程設(shè)計 課 程 代 碼: 7106620 題 目: 樹的最大連通分支問題 年級/專業(yè)/班: 2008/信息與計算科學(xué) /2 班 學(xué) 生 姓 名: 何德宏 學(xué) 號: 312008070102221 開 始 時 間: 2011 年 12 月 5 日完 成 時 間: 2011 年 12 月 18 日課程設(shè)計成績：學(xué)習(xí)態(tài)度及平時成績（30）技術(shù)水平與實際能力（20）創(chuàng)新（5）說明書撰寫質(zhì)量（45）總 分（100）指導(dǎo)教師簽名： 年 月 日樹的最大連通分支問題目 錄 1 1 引引 言言 .1 11.1 問題的提出 .11.2 任務(wù)與分析.

2、12 2 程序的主要功能程序的主要功能 .3 32.1 樹的存儲功能.32.2 連通分支的計算功能.33 3 程序運行平臺程序運行平臺 .3 34 4 總體設(shè)計總體設(shè)計 .3 34.1 算法設(shè)計.34.2 流程設(shè)計.65 5 模塊分析模塊分析 .7 75.1 樹的存儲模塊 .75.2 計算樹的最大連通分支模塊 .96 6 系統(tǒng)測試系統(tǒng)測試 .10107 7 結(jié)論結(jié)論 .14148 8 致謝致謝 .15159 9 參考文獻參考文獻 .1616附錄附錄 .1717 樹的最大連通分支問題摘摘 要要隨著計算機的普及，人們解決問題的方法也變得多樣化，同一個問題總想用簡單實用的方法去解決，其中樹的最大連通

3、分支問題就是一個很典型的例子，我們可以用蠻力法和動態(tài)規(guī)劃法去實現(xiàn)，但用動態(tài)規(guī)劃的方法效率更高。因此該系統(tǒng)利用動態(tài)規(guī)劃的方法編程實現(xiàn)了求解樹的最大連通分支問題，該程序能夠快速輸入樹的結(jié)構(gòu)，并能計算出樹的最大連通分支。此外，代碼簡潔易懂，界面友好，能一目了然的看出最終的結(jié)果，便于操作。關(guān)鍵詞：樹的最大連通分支;動態(tài)規(guī)劃; -1-樹的最大連通分支問題1 1 引引 言言 1.11.1 問題的提出問題的提出 連通分支定義： 設(shè) X 是一個拓撲空間對于 X 中的點的連通關(guān)系而言的每一個等價類稱為拓撲空間 X 的一個連通分支如果 Y 是拓撲空間 X 的一個子集Y 作為 X 的子空間的每一個連通分支稱為 X

4、的子集 Y 的一個連通分支 拓撲空間 X 的每一個連通分支都不是空集；X 的不同的連通分支無交；以及 X 的所有連通分支之并便是 X 本身此外，x，yX 屬于 X 的同一個連通分支當(dāng)且僅當(dāng) x 和 y 連通樹作為一種特殊的圖，它本身就是連通的，里面還有許多的連通子圖，當(dāng)每個頂點加入權(quán)值后，可以計算出權(quán)值最大的連通子圖。使用的方法可以有很多，其中蠻力法和動態(tài)規(guī)劃是兩種比較典型的方法，相對于蠻力法而言，動態(tài)規(guī)劃的方法效率更高，所以最后選擇了動態(tài)規(guī)劃方法來計算樹的最大連通分支問題。1.21.2 任務(wù)與分析任務(wù)與分析給定一棵樹T，樹中每個頂點u都有一個權(quán)值w(u)，而且權(quán)值可以是正數(shù)或者負數(shù)?，F(xiàn)在要找

5、到樹T的一個連通子圖使該子圖的權(quán)之和最大，要求編程實現(xiàn)計算出樹的最大連通分支傳統(tǒng)的方法為蠻力法，即依次以每一個頂點為根節(jié)點，然后找出以該節(jié)點為根節(jié)點的所有連通子圖，分別計算出連通子圖的權(quán)值之和，最后找出權(quán)值之和最大的連通子圖，便可得出最后的結(jié)果，但該方法效率不高，如果給定是一棵有很多節(jié)點的樹，那么這效率將會非常低下。為此，我們將使用動態(tài)規(guī)劃的方法來求解此問題：對于以X為根的子樹分兩種情況考慮：（1）、包含根（fx,1）：fx,1等于所有大于0的fsonx,1的和加wx。（2）、不包含根（fx,0）:fx,0=maxmax(fsonx,1,fsonx,0)。記憶話搜索遞歸求解。算法分析:最大連通

6、分支在子樹或樹中，因此對樹進行遍歷，依次求出以每個結(jié)點為樹根的最大連通分支權(quán)值-2-樹的最大連通分支問題樹根rootT1T2W0Wr=Wr+Wt1rootT1T2W0 該問題具有兩個子性質(zhì)：最有子結(jié)構(gòu)性質(zhì)子問題重疊性質(zhì)算法實現(xiàn)：1、對于葉子結(jié)點或兒子個數(shù)為0的結(jié)點，其最大連通分支權(quán)值為該 結(jié)點的權(quán)值2、某一結(jié)點的最大連通權(quán)值0，則將其值加到它的父親結(jié)點的最大連通權(quán)值，反之舍棄該值3、最后求出根結(jié)點的最大連通權(quán)值，結(jié)束遍歷4、所求最大連通分支權(quán)值即結(jié)點 的最大連通權(quán)值最后采用動態(tài)規(guī)劃求解，類似于圖的后續(xù)遍歷，這方法避免了很多蠻力法的缺點，因此效率也得到了很大的提高。樹根rootT1T2W0W0-

7、3-樹的最大連通分支問題2 2 程序的主要功能程序的主要功能2.12.1 樹的存儲功能樹的存儲功能要想計算樹的最大連通分支，首先需要給定一棵樹，因此需要存儲樹的基本信息，其中最重要的就是節(jié)點信息，用結(jié)構(gòu)體來表示：包括結(jié)點的權(quán)值（weight） ，結(jié)點的父親結(jié)點（father） ，結(jié)點的兒子結(jié)點（child） ，結(jié)點的最大連通分支權(quán)值（wmax）和結(jié)點是否被訪問過（visited） ，最后需要用數(shù)組（動態(tài)創(chuàng)建）表示樹。2.22.2 連通分支的計算功能連通分支的計算功能樹創(chuàng)建完后，首先要對樹結(jié)構(gòu)進行初始化，并需要輸入數(shù)據(jù)建立樹結(jié)構(gòu)，然后確定一個樹根，對每一個結(jié)點用動態(tài)規(guī)劃的方法進行遍歷，找出最大連

8、通分支并計算出權(quán)值，最后輸出最大的連通分支和其權(quán)值。3 3 程序運行平臺程序運行平臺WINDOWS XP/WIN 7 VC+6.0。具體操作如下：進入 Visual C+6.0 開發(fā)環(huán)境,在開發(fā)環(huán)境的主窗口中選擇File|New 菜單項，在彈出的對話框中單擊 Project 選項卡，選擇 C+ Source File，命名為“樹的最大連通分支問題” ，再制定保存路徑，單擊 OK 鍵完成新建。再在編輯窗口中編輯代碼，編譯，鏈接， ，進行調(diào)試，執(zhí)行，然后輸出結(jié)果。 4 4 總體設(shè)計總體設(shè)計4.14.1 算法設(shè)計算法設(shè)計1、數(shù)據(jù)結(jié)構(gòu)struct Cnode /用結(jié)構(gòu)體來表示結(jié)點 long weigh

9、t; /結(jié)點的權(quán)值 int father; /結(jié)點的父親結(jié)點 int childnum; /結(jié)點的兒子個數(shù) long wMax; /結(jié)點的最大連通分支權(quán)值 -4-樹的最大連通分支問題bool visited; /該結(jié)點是否被訪問過int save100;/最大連通分支權(quán)值來源;2、動態(tài)創(chuàng)建數(shù)組表示樹Cnode *tree=new Cnoden+1;3、樹的初始化for (i=1;i(treei.weight); treei.wMax=treei.weight;treei.save0=0;treei.save1=0;treei.save2=0;treei.save3=0;treei.save4=

10、0;treei.save5=0;4、樹結(jié)構(gòu)的建立：cout請輸入各結(jié)點的關(guān)系：endl;for (i=1;iuv; treev.father=u; -5-樹的最大連通分支問題treeu.childnum+; coutendl;5、動態(tài)規(guī)劃算法實現(xiàn)計算樹的最大連通分支：int root; int m=1;for (i=1;i0)/遍歷樹 for (i=1;i0) treetreei.father.wMax=treetreei.father.wMax+treei.wMax; treetreei.father.savei=i;for(int m=0;m=5;m+) if(treei.savem!=0

11、) treetreei.father.savem=treei.savem;-6-樹的最大連通分支問題 6、結(jié)果的輸出long max=tree1.wMax; int h=1;for (i=2;imax) max=treei.wMax; h=i;cout 最大權(quán)值為 ：maxendl;coutendl;cout 最大連通分支包含的結(jié)點為 ：endl;for (int j=1;j=n;j+)if(treeh.savej!=0)couttreeh.savejendl;if(j=h)couthendl;4 4.2.2 流程設(shè)計流程設(shè)計總體設(shè)計的流程圖如圖 4.1 所示：-7-樹的最大連通分支問題圖 4

12、.1 總體流程圖5 5 模塊分析模塊分析5.15.1 樹的存儲模塊樹的存儲模塊代碼分析：struct Cnode /用結(jié)構(gòu)體來表示結(jié)點 long weight; /結(jié)點的權(quán)值 int father; /結(jié)點的父親結(jié)點 int childnum; /結(jié)點的兒子個數(shù) 開始初始化樹動態(tài)規(guī)劃求最大連通分支計算最大權(quán)值輸出結(jié)果完成未完成建立樹結(jié)構(gòu)-8-樹的最大連通分支問題long wMax; /結(jié)點的最大連通分支權(quán)值 bool visited; /該結(jié)點是否被訪問過int save100;/最大連通分支權(quán)值來源; 樹的初始化及建立：cout請輸入樹結(jié)點的個數(shù) endln; coutendl;Cnode

13、*tree=new Cnoden+1;/動態(tài)創(chuàng)建數(shù)組表示樹 cout請依次輸入各結(jié)點的權(quán)值：endl;for (i=1;i(treei.weight); treei.wMax=treei.weight;treei.save0=0;treei.save1=0;treei.save2=0;treei.save3=0;treei.save4=0;treei.save5=0;coutendl; cout請輸入各結(jié)點的關(guān)系：endl;for (i=1;iuv; treev.father=u; treeu.childnum+; 5.25.2 計算樹的最大連通分支模塊計算樹的最大連通分支模塊代碼分析：int

14、 root; int m=1;for (i=1;i0)/遍歷樹 for (i=1;i0) treetreei.father.wMax=treetreei.father.wMax+treei.wMax; treetreei.father.savei=i;for(int m=0;m=5;m+) if(treei.savem!=0)-10-樹的最大連通分支問題 treetreei.father.savem=treei.savem; long max=tree1.wMax; int h=1;for (i=2;imax) max=treei.wMax; h=i;cout 最大權(quán)值為 ：maxendl;c

15、outendl;cout 最大連通分支包含的結(jié)點為 ：endl;for (int j=1;j=n;j+)if(treeh.savej!=0)couttreeh.savejendl;if(j=h)couthendl;6 系統(tǒng)測試系統(tǒng)測試程序完成后需要對程序進行測試，在本程序中需要輸入樹結(jié)點的個數(shù)，各結(jié)點的權(quán)值，各節(jié)點之間的對應(yīng)關(guān)系，最后即可輸出相應(yīng)的結(jié)果。輸入樹的實例如圖 6-1 所示，輸入過程和輸入結(jié)果如 6-2 到 6-5 所示： -11-樹的最大連通分支問題-1-13 31 1-1-11 112345圖 6-1 輸入實例圖 6-2 輸入樹結(jié)點的個數(shù)圖 6-3 輸入各結(jié)點的權(quán)值圖 6-4 各

16、結(jié)點的對應(yīng)關(guān)系每行有表示樹 T 的一條 邊的 2 個整數(shù) u,v，表示頂點 u 與頂點 v 相連-12-樹的最大連通分支問題圖 6-5 樹的結(jié)構(gòu)圖圖 6-6 計算出得最大權(quán)值及包含的結(jié)點圖 6-7 最大連通分支-13-樹的最大連通分支問題從上述結(jié)果可知，此程序能夠很好地解決樹的最大連通分支問題，從最終的結(jié)果來看此次設(shè)計還是比較成功的。上面顯示的就是計算樹的最大連通分支的問題從例子可以看出，我們輸入相應(yīng)的數(shù)據(jù)后可以一目了然的看到最終的結(jié)果，不用看太多的復(fù)雜關(guān)系，能給我們一種簡潔明了的感覺，但從用戶體驗上來看，界面不夠友好，只是大體的顯示了結(jié)構(gòu)，從另外一方面講顯得很抽象，因此這點需要改進。-14-

17、樹的最大連通分支問題7 7 結(jié)論結(jié)論本次課程設(shè)計用 C+進行開發(fā)，采用了動態(tài)規(guī)劃算法。動態(tài)規(guī)劃算法和遞歸算法是在解決很多問題中比較通用的算法，此次課程設(shè)計通過動態(tài)規(guī)劃算法和遞歸能成功地解決樹的最大連通分支問題。經(jīng)過此次對次問題的解決，再次加深了我對動態(tài)規(guī)劃這種思想的理解。剛開始選題的時候覺得很簡單，能夠很容易的去實現(xiàn)，但是仔細想后，發(fā)現(xiàn)并不是想象中的那樣子，甚至無從下手。雖然樹的最大連通分支問題是用動態(tài)規(guī)劃實現(xiàn)的一個很好的例子，但是真正去實現(xiàn)的人并不多，因此可供參考的資料很少。通過查閱資料，知道了幾種解決此問題的方法，其中比較有名的為蠻力算法和動態(tài)規(guī)劃算法，但綜合其時間效率和實現(xiàn)過程，最后選擇

18、了動態(tài)規(guī)劃。在程序設(shè)計時，使用了結(jié)構(gòu)體來存儲樹的各節(jié)點的信息，也使用了數(shù)組來表示數(shù)。此程序有以下幾大優(yōu)點：1、代碼簡練易懂；2、方便用戶使用；3、能成功地解決樹的最大連通分支問題。當(dāng)然由于時間比較緊，再加上有些基礎(chǔ)知識的原因，只是大體實現(xiàn)了功能，界面之類的不夠友好，需要在下來的時間不斷鉆研，刻苦學(xué)習(xí)，爭取能夠?qū)W到更多的東西，讓自己變得更好。-15-樹的最大連通分支問題8 8 致謝致謝首先需要感謝的是指導(dǎo)老師王曉明老師，在他的督促下才能按時完成這個課程設(shè)計，感謝他這學(xué)期對我們的細心教導(dǎo)與幫助，在他的幫助下我雖不能說學(xué)到了全部的知識，但收獲卻不少，讓我很好的理解了算法設(shè)計與分析這門課程的重要性，給

19、我以后在遇到問題的時候提供了很多的思路。王老師總是很對我們提出各種問題很熱情耐心的解答。沒有他的幫助與輔導(dǎo)我們是不可能完成學(xué)習(xí)和課程設(shè)計的。再者需要感謝的是與我們相關(guān)的各門課的老師，沒有他們，我們就不會有很好的基礎(chǔ)做課程設(shè)計了。當(dāng)然整個完成的過程中周圍的同學(xué)也給了不少幫助，總之在此真的非常感激每個人！有進步是因為有幫助！-16-樹的最大連通分支問題9 9 參考文獻參考文獻1宋文. 算法設(shè)計與分析. 重慶：重慶大學(xué)出版社，20012Anany Levitin. 算法設(shè)計與分析基礎(chǔ). 北京：清華大學(xué)出版社，20063王曉東. 算法設(shè)計與實驗題解M.北京：電子工業(yè)出版社，20064王紅梅. 算法設(shè)計

20、與分析M.北京：清華大學(xué)出版社，20065鄭曉明. 算法設(shè)計與分析M.北京：清華大學(xué)出版社，2005-17-樹的最大連通分支問題附錄#include iostream.h #include using namespace std; struct Cnode /用結(jié)構(gòu)體來表示結(jié)點 long weight; /結(jié)點的權(quán)值 int father; /結(jié)點的父親結(jié)點 int childnum; /結(jié)點的兒子個數(shù) long wMax; /結(jié)點的最大連通分支權(quán)值 bool visited; /該結(jié)點是否被訪問過int save100;/最大連通分支權(quán)值來源; int main() int i; long

21、n,u,v;cout請輸入樹結(jié)點的個數(shù) endln; coutendl;Cnode *tree=new Cnoden+1;/動態(tài)創(chuàng)建數(shù)組表示樹 cout請依次輸入各結(jié)點的權(quán)值：endl;for (i=1;i(treei.weight); treei.wMax=treei.weight;treei.save0=0;treei.save1=0;treei.save2=0;treei.save3=0;treei.save4=0;treei.save5=0;coutendl; cout請輸入各結(jié)點的關(guān)系：endl;for (i=1;iuv; treev.father=u; treeu.childnum+; coutendl;coutendl; cout樹的結(jié)構(gòu)如下圖所示 ：endl;cout*endl;cout.4(1).endl; cout.*.*.endl; cout.*.*.endl;-19-樹的最大連通分支問題 cout.*.*.endl;cout.*.*.endl; cout.1(-1).5(-1).endl; cout.*.*.endl; cout.*.*.endl;cout.*.*.endl;cout.*.*.endl;cout.2(1).3(3).endl;cout.