數(shù)據(jù)結構課程設計--最小生成樹

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：19 大?。?98.00KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩18頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　成績評定表　　課程設計任務書　　摘要　　“計算機算法設計與分析” 著重介紹了計算機算法設計領域的基本原則和根本原理。深入分析了一些計算機模型上的算法，介紹了一些和設計有

2、效算法有關的數(shù)據(jù)結構和編程技術，為讀者提供了有關遞歸方法、分治方法和動態(tài)規(guī)劃方面的詳細實例和實際應用，并致力于更有效算法的設計和開發(fā)。同時，對NP完全等問題能否有效求解進行了分析，并探索了應用啟發(fā)式算法解決問題的途徑。　　本文第一問，隨著信息技術的發(fā)展和嵌入式設備的廣泛使用．電路布線問題越來越受到人們的重視．要使電子電路獲得最佳性能．不僅元器件的布置占有著重要的地位．而且導線的布設也是非常重要的

3、．特別是在涉及到線路成本的布線方案中．一個好的布線算法就顯得尤為重要本文首先對一類電路板低成本布線問題進行了分析．進而給出了解決這一問題的分支限界解法．并對所提出算法的時間復雜度進行了分析和討論。　　本文第二問，掌握動態(tài)規(guī)劃法的原理，并能夠按其原理編程實現(xiàn)求兩個序列數(shù)據(jù)的最長公共子系列，以加深對其的理解。　　關鍵字：分支限界；布線問題；動態(tài)規(guī)劃<

4、/p>　　目錄　　1 分支限界解決布線問題1　　1.1問題重述1　　1.2問題分析1　　1.3算法分析與設計1</

5、p>　　1.4算法的實現(xiàn)與結果2　　2 動態(tài)規(guī)劃解決最長公共子序列問題9　　2.1問題重述9　　2.2問題分析9　　2.3算法分析與設計9

6、　　2.4算法實現(xiàn)與結果10　　參考文獻14　　1 分支限界解決布線問題　　1.1問題重述　　`布線問題：如圖1所示，印刷電路板將布線區(qū)域劃分成n*m個方格。精確的電路布

7、線問題要求確定連接方格a的中點到b的中點的最短布線方案。在布線時，電路只能沿直線或直角布線，如圖1所示。為了避免線路相交，已經布線的方格做了封鎖標記（如圖1中陰影部分），其他線路不允許穿過被封鎖的方格。　　1.2問題分析　　題目的要求是找到最短的布線方案，從圖1的情況看，可以用貪婪算法解決問題，也就是從a開始朝著b的

8、方向垂直布線即可。實際上，再看一下圖2，就知道貪婪算法策略是行不通的。因為已布線的放個沒有規(guī)律的所以直觀上說只能用搜索方法去找問題的解。　　根據(jù)布線方法的要求，除邊界或已布線處，每個E-結點分支擴充的方向有4個：上、下、左、右，也就是說，一個E-結點擴充后最多產生4個活結點。以圖2的情況為例，圖的搜索過程如圖3所示。　　搜索以a為第一個E-結點，以后不斷

9、擴充新的活結點，直到b結束（當然反之也可以）。反過來從b到a，按序號8-7-6-5-4-3-2-1就可以找到最短的布線方案。從圖3中也可以發(fā)現(xiàn)最短的布線方案是不唯一的。且由此可以看出，此問題適合用分支限界搜索。　　1.3 算法分析與設計　　算法分析：　　分支限界搜索法是一種在

10、問題解空間上進行搜索嘗試的算法。所謂“分支”是采用廣度優(yōu)先的策略，依次搜索E-結點的所有分支，也就是所有的相鄰結點。和回溯法一樣，在生成的結點中，拋棄那些不滿足約束條件（或者說不可能到處最優(yōu)可行解）的結點，其余結點加入活結點表。然后從表中選擇一個節(jié)點作為下一個E-結點，繼續(xù)搜索。選擇下一個E-結點的方式不同，會出現(xiàn)幾種不同的分值搜索方式。　　FIFO搜索&l

11、t;/p>　　先進先出（FIFO）搜索算法要依賴“隊”做基本的數(shù)據(jù)結構。一開始，根節(jié)點是唯一的活結點，根節(jié)點入隊。從活結點隊中取出根節(jié)點后，作為當前擴展結點。對當前擴展結點，先從左到右地產生它的所有兒子，用約束條件檢查，把所有滿足約束函數(shù)的兒子加入或節(jié)點隊列中。再從活結點表中取出隊首結點（對中最先進來的結點）為當前結點，……，直到找到一個解或活結點隊列為空為止。<

12、;b>　　LIFO搜索　　后進先出（LIFO）搜索算法要依賴“?！弊龌镜臄?shù)據(jù)結構。一開始，根結點入棧，從棧中彈出一個結點為當前擴展結點。對當前擴展結點，從左到右地產生它的所有兒子，用約束條件檢查，把所有滿足約束函數(shù)的兒子入棧，再從棧中彈出一個結點（棧中最后進來的結點）為當前擴展結點，……，直到找到一個解或棧為空為止。<b

13、>　　優(yōu)先隊列式搜索　　為了加速搜索的進程，應采用有效的方式選擇E-結點進行擴展。優(yōu)先隊列搜索，對每一個活結點計算一個優(yōu)先級（某些信息的函數(shù)值），并根據(jù)這些優(yōu)先級，從當前結點表中優(yōu)先選擇一個優(yōu)先級最高（最有利）的結點作為擴展結點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。　　算法設計：&

14、lt;/b>　　開辟m*n的二維數(shù)組模擬布線區(qū)域，初始值均為0，表示沒有被使用。已使用的位置，通過鍵盤輸入其下標，將對應值置為-1.輸入方格a、b的下標，存儲在變量中。　?、僖婚_始，唯一的活結點是a。　?、趶幕罱Y點表中取出后為當前擴展結點。　?、蹖Ξ斍皵U展結點，按上

15、、下、左、右的順序，找出可布線的位置，加入活結點隊列中，　?、茉購幕罱Y點隊列中取出后為當前擴展結點。　　⑤依此類推，直到搜索到達b結點，然后按序號8-7-6-5-4-3-2-1輸出最短布線方案，算法結束?；蚧罱Y點隊列已為空，表示無解，算法結束。　　1.4算法的實現(xiàn)與結果

16、　通過算法的分析與設計，計算如圖所示4所示的布線問題　　代碼：　　#include <stdio.h>　　#include <stdlib.h>　　typedef struct Position</p&g

17、t;　　{　　int row;　　int col;　　}Position;　　typedef struct team

18、　　{　　int x;　　int y;　　struct team *next;　　}team,*TEAM;<

19、;p>　　Position start,end,path[100];　　TEAM team_l=NULL;　　int a[100][100];　　int m,n,path_len;　　void output()<b&g

20、t;　　{　　int i,j;　　printf("\n|-------------------布線區(qū)域圖-------------------|\n");　　for(i=0;i<m+2;i++)<p&

21、gt;　　{　　for(j=0;j<n+2;j++)　　{　　printf("%5d",a[i][j]);　　}

22、　　printf("\n");　　}　　printf("|------------------------------------------------|\n");　　return;</b

23、>　　}　　void input_data()　　{　　char yes;　　int x,y

24、;　　printf("創(chuàng)建布線區(qū)域...\n\n");　　printf("請輸入區(qū)域大小(行列的個數(shù)): ");　　scanf("%d,%d",&m,&n);　　printf(

25、"請輸入開始點坐標(x,y): ");　　scanf("%d,%d",&start.row,&start.col);　　printf("請輸入結束點坐標(x,y): ");　　scanf("%d,%d",&en

26、d.row,&end.col);　　printf("區(qū)域內是否有被占用點? (y/n) ");　　fflush(stdin);　　scanf("%c",&yes);　　fflush(stdin);

27、　　while(yes=='y')　　{　　printf("請輸入占用點的坐標(x,y): ");　　scanf("%d,%d",&x,&y);<p&g

28、t;　　fflush(stdin);　　if(x<0 || x>m+1 || y<0 || y>n+1 || (x==start.row && y==start.col) || (x==end.row && y==end.col))　　{

29、　　printf("輸入錯誤,請重新輸入!!!\n");　　continue;　　}　　else　　{

30、　　a[x][y]=-1;　　}　　printf("是否還有被占用點? (y/n) ");　　scanf("%c",&yes);<p&g

31、t;　　fflush(stdin);　　}　　for(x=0;x<m+2;x++)　　{　　a[0][x]=-1;　　a[m+1][x]=-1;&l

32、t;/p>　　}　　for(x=0;x<n+2;x++)　　{　　a[x][0]=-1;　　a[x][n+1]=-1;&

33、lt;b>　　}　　return;　　}　　void inq(Position p)　　{

34、　　TEAM t,q;　　q=team_l;　　t=(TEAM)malloc(sizeof(TEAM));　　t->x=p.row;　　t->y=p.col;&

35、lt;p>　　t->next=NULL;　　if(team_l==NULL)　　{　　team_l=t;　　return ;

36、　　}　　while(q->next!=NULL)　　{　　q=q->next;　　}

37、;　　q->next=t;　　return;　　}　　Position outq()　　{　　Position

38、 out;　　out.row=team_l->x;　　out.col=team_l->y;　　team_l=team_l->next;　　return out;　　}<

39、/p>　　void find_path()　　{　　Position offset[4];　　Position here={start.row,start.col};　　Position nbr={0,0}

40、;　　int num_of_nbrs=4;　　int i,j;　　offset[0].row=0;offset[0].col=1; //右　　offset[1].row=1;offset[1].col=0; //下

41、　　offset[2].row=0;offset[2].col=-1;//左　　offset[3].row=-1;offset[3].col=0;//上　　printf("\n開始搜索路徑...\n");　　if((start.row == end.row)&&a

42、mp;(start.col == end.col)){　　path_len = 0;　　return;　　}　　while(1)<

43、;p>　　{　　for(i=0;i<num_of_nbrs;i++)　　{　　nbr.row=here.row+offset[i].row;　　nbr.col=here.col+off

44、set[i].col;　　if(a[nbr.row][nbr.col]==0)　　{　　a[nbr.row][nbr.col]=a[here.row][here.col] + 1;　　if((nbr.row == end.row) &

45、amp;& (nbr.col == end.col))　　break;　　inq(nbr); //nbr入隊　　}　　}<

46、;p>　　//是否到達目標位置finish　　if((nbr.row == end.row) && (nbr.col == end.col))　　break;　　//或節(jié)點隊列是否為空　　if(team_l==N

47、ULL)　　{ 　　printf("\n沒有結果!!!\n");　　return ;　　}　　h

48、ere=outq();　　}　　path_len=a[end.row][end.col];　　here=end;　　for(j=path_len-1;j>=0;j--)

49、　　{　　path[j] = here;　　for(i = 0;i < num_of_nbrs;i++)　　{　　nbr.row = here.row + offset[

50、i].row;　　nbr.col = here.col + offset[i].col;　　if(a[nbr.row][nbr.col] == j) //+ 2)　　break;　　}</p

51、>　　here=nbr;　　}　　return;　　}　　void out_path()&l

52、t;/p>　　{　　int i;　　printf("\n路徑為:\n");　　printf("(%d,%d) ",start.row,start.col);</p

53、>　　for(i=0;i<path_len;i++)　　{　　printf("(%d,%d) ",path[i].row,path[i].col);　　}&l

54、t;p>　　printf("\n");　　return;　　}　　void main()　　{<p&g

55、t;　　input_data();　　output();　　find_path();　　out_path();　　output();

56、}　　運行結果與分析：　　根據(jù)運行的結果我們看到，首先要給布線區(qū)域加一道“圍墻”，從開始點進行標記。直達到達結束點。并且可以看到a到b的路徑不是唯一的，及最優(yōu)解不是唯一的。　　2 動態(tài)規(guī)劃解決最長公共子序列問題&l

57、t;b>　　2.1 問題重述　　若給定序列={, ,…,}，則另一序列={,,…,}，是的子序列是指存在一個嚴格遞增下標序列{, ,…, }使得對于所有j=1,2,…,k有：=。例如，序列={B，C，D，B}是序列={A，B，C，B，D，A，B}的子序列，相應的遞增下標序列為{2，3，5，7}。給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X

58、和Y的公共子序列。請使用C語言編程，設計一個有效的算法解決下述問題：給定2個序列X={, ,…,}，和Y={ , ,…,}，找出X和Y的最長公共子序列。　　2.2問題分析　　設序列X={, ,…,}和Y={ , ,…,}的最長公共子序列為={,,…,}，則　　(1)若，則，且

59、是和的最長公共子序列。　　(2)若且，則Z是和Y的最長公共子序列。　　(3)若且，則Z是X和的最長公共子序列。　　由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。　　2.3算法分析與設計

60、　　算法分析：　　動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題

61、，則分解得到的子問題數(shù)目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中，這就是動態(tài)規(guī)劃法的基本思路。　　算法設計：

62、;　　由最長公共子序列問題的最優(yōu)子結構性質建立子問題最優(yōu)值的遞歸關系。用c[i][j]記錄序列和的最長公共子序列的長度。其中，={, ,…,} ={ , ,…, }。當i=0或j=0時，空序列是和的最長公共子序列。故此時C[i][j]=0。程序的設計思路是：調用函數(shù)void Initialize（），輸入兩個字符串，對兩個串的存儲數(shù)組b，c進行動態(tài)分配。調用函數(shù)void LCSLength（int m,int n,string x,st

63、ring y,int**c,int**b），將長度較小的字符串作為第一參數(shù)，將長度較大的字符串作為第二個參數(shù)。調用函數(shù)void LCS（inti，int j,string x,int**b）構造最長公共子序列調用函數(shù)。調用函數(shù)ReadCommand進行系統(tǒng)操作屏幕指示，然后利用函數(shù)void Interpret（char&cmd）對函數(shù)進行總體操作，最后得出最長公共子序列。　　2.4算法實

64、現(xiàn)與結果　　代碼如下：　　#include<iostream>　　#include<string>　　using namespace std;　　string x,y;

65、//x,y用來存放字符序列　　int **c,**b,m,n;　　/*m，n分別存儲字符串x,y的長度,數(shù)組c[i][j]存儲Xi和Yj得最長公共子序列的長度，　　b[i][j]記錄c[i][j]的值是有哪一個子問題的解得到的*/　　void LCSLength(int

66、m,int n,string x,string y,int **c,int**b);　　void LCS(int i,int j,string x,int **b);　　void Initialize();//對數(shù)組b,c動態(tài)分配空間以及對其進行初始化　　void ReadCommand(char &cm

67、d);　　void Interpret(char &cmd);　　void Realese();//釋放指針　　void Display();　　int main()　　{</p

68、>　　char cmd;　　do　　{　　ReadCommand(cmd);　　Interpret(cmd);　　}whil

69、e(cmd!='q'&&cmd!='Q');　　return 0;　　}　　void ReadCommand(char &cmd)<b

70、>　　{　　system("cls"); //清屏　　cout<<"\n--------------------------------------------------------------------------\n";

71、cout<<"\n\t\t\t\t操作提示";　　cout<<"\n--------------------------------------------------------------------------\n";　　cout<<"\tquit--

72、q/Q \t\t continue---c/C\n";　　do{　　cout<<"\n\n\t請選擇操作：";　　cin>>cmd;　　cou

73、t<<"\n--------------------------------------------------------------------------\n";　　}while(cmd!='c'&&cmd!='C'&&cmd!='q'&&cmd!='Q&

74、#39;);　　}　　void Initialize()　　{　　cout<<"分別輸入兩個字符串（每個字符串以回車結束）\n";<

75、p>　　cin>>x;　　cin>>y;　　m=x.length();　　n=y.length();　　c=new int*[m+1];<

76、;p>　　b=new int*[m+1];　　for(int i=0;i<=m;i++)　　{　　c[i]=new int[n+1];　　b[i]=new int[n+1];<

77、;b>　　}　　}　　void Realese()//釋放指針board　　{　　for(int i=0;i<=m;i++)

78、;　　{　　delete c[i];　　delete b[i];　　}　　delete[] c;　　delete[] b;<

79、p>　　}　　void Interpret(char &cmd)　　{　　switch(cmd)　　{

80、　　case 'c':　　case 'C': 　　Initialize();　　LCSLength(m,n,x,y,c,b);　　Display();　　Rea

81、lese();　　break;　　}　　}　　void LCSLength(int m,int n,string x,string y,int **c,int

82、**b)　　{　　int i,j;　　for(i=0;i<=m;i++)c[i][0]=0;　　for(i=1;i<=n;i++)c[0][i]=0;<p

83、>　　for(i=1;i<=m;i++)　　for(j=1;j<=n;j++)　　{　　if(x[i-1]==y[j-1])　　{　　c

84、[i][j]=c[i-1][j-1]+1;　　b[i][j]=1;　　}　　else if(c[i-1][j]>=c[i][j-1])　　{　　c[

85、i][j]=c[i-1][j];　　b[i][j]=2;　　}　　else　　{　　c[i][j]=c[i][j-1

86、];　　b[i][j]=3;　　}　　}　　}　　//構造最長公共子序列

87、　void LCS(int i,int j,string x,int **b)　　{　　if(i==0||j==0)return;　　if(b[i][j]==1)　　{&l

88、t;p>　　LCS(i-1,j-1,x,b);　　cout<<x[i-1];　　}　　else if(b[i][j]==2)LCS(i-1,j,x,b);　　else LCS(i,j-1,x,b);

89、;　　}　　void Display()　　{　　LCS(m,n,x,b);　　cout<<"\n請按回車鍵繼續(xù)！\n";

90、　　cin.get();　　cin.get();　　}　　結果分析：　　通過代碼和運行結果，我們能夠看到，首先對二個序列進行動態(tài)分配，將長度較小的字符串作為第一參數(shù)，將長度較

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結構課程設計--最小生成樹

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計--最小生成樹

文檔簡介

溫馨提示

最新文檔

評論

免費下載