1、本科實驗報告課程名稱： 算法設(shè)計與分析 實驗項目： 遞歸與分治算法 實驗地點： 計算機系實驗樓110 專業(yè)班級： 物聯(lián)網(wǎng)1601 學號： 2021002105 學生姓名： 俞夢真 指導教師： 郝曉麗 2021年 05月 04 日實驗一 遞歸與分治算法1.1 實驗目的與要求1進一步熟悉C/C+語言的集成開發(fā)環(huán)境；2通過本實驗加深對遞歸與分治策略的理解和運用。1.2 實驗課時2學時1.3 實驗原理分治（Divide-and-Conquer）的思想：一個規(guī)模為n的復雜問題的求解，可以劃分成若干個規(guī)模小于n的子問題，再將子問題的解合并成原問題的解。需要注意的是，分治法使用遞歸的思想。劃分后的每一個子問

2、題與原問題的性質(zhì)相同，可用相同的求解方法。最后，當子問題規(guī)模足夠小時，可以直接求解，然后逆求原問題的解。1.4 實驗題目1上機題目：格雷碼構(gòu)造問題Gray碼是一個長度為2n的序列。序列無相同元素，每個元素都是長度為n的串，相鄰元素恰好只有一位不同。試設(shè)計一個算法對任意n構(gòu)造相應的Gray碼（分治、減治、變治皆可）。對于給定的正整數(shù)n，格雷碼為滿足如下條件的一個編碼序列。（1）序列由2n個編碼組成，每個編碼都是長度為n的二進制位串。（2）序列中無相同的編碼。（3）序列中位置相鄰的兩個編碼恰有一位不同。 2設(shè)計思想：根據(jù)格雷碼的性質(zhì)，找到他的規(guī)律，可發(fā)現(xiàn)，1位是0 1。兩位是00 01 11 10

3、。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍個。N-1個位前面加0，N-2為倒轉(zhuǎn)再前面再加1。3代碼設(shè)計：#include#include#include #includeusing namespace std;/求格雷碼 遞推式子：G(n-1)=B(n-1) G(i)=B(i+1)異或B(i) (0in-2)/輸出n位GRad碼-普通方法vector My_grad;void get_grad(int n)/cout11)/cout1endl;for(int i=2;i=n;i+)vector tmp;for(int j=0;j=0;j-)s

4、tring s=1;s+=tmpj;My_grad.push_back(s);int main()int n;while(cinn)get_grad(n);for(int i=0;iMy_grad.size();i+)coutMy_gradi0，T=(t1,t2,tn)，客戶i希望的服務完成時刻為di0，D=(d1,d2,dn)；一個調(diào)度f:AN，f(i)為客戶i的開始時刻。如果對客戶i的服務在di之前結(jié)束，那么對客戶i的服務沒有延遲，即如果在di之后結(jié)束，那么這個服務就被延遲了，延遲的時間等于該服務的實際完成時刻f(i)+ti減去預期結(jié)束時刻di。一個調(diào)度f的最大延遲是所有客戶延遲時長的最大

5、值maxiAf(i)+ti-di。附圖2所示是不同調(diào)度下的最大延遲。使用貪心策略找出一個調(diào)度使得最大延遲達到最小。2設(shè)計思想：貪心思想，按照他們的截止時間從小到大排序，如果截止時間相同按照花費時間從小到大排序。然后按照f_min（所有客戶延遲時長的最大值）=max(worksi.cost+time-worksi.deadline,f_min);尋找最所有客戶延遲時長的最大值。3代碼設(shè)計：/最小延遲調(diào)度問題/輸入包含：任務，任務完成需要的時間，完成改任務的截止時間#include#include#include#includeusing namespace std;const int maxn=

6、1000+10;int n;struct nodeint id;int cost;int deadline;worksmaxn;bool cmp(node a,node b)if(a.deadline!=b.deadline)return a.deadlineb.deadline; else return a.costb.cost;int dpmaxnmaxn;int main()while(scanf(%d,&n)!=EOF)for(int i=0;in;i+)scanf(%d,&worksi.cost);for(int i=0;in;i+)scanf(%d,&worksi.deadline

7、),worksi.id=i+1;sort(works,works+n,cmp);int f_min=0;int time=0;for(int i=0;iworksi.deadline)f_min=max(worksi.cost+time-worksi.deadline,f_min);/coutf_minendl;time+=worksi.cost;printf(Maximum delay:n);printf(%dn,f_min);printf(Complete the order of tasks:n);for(int i=0;in;i+)coutworksi.id ;coutendl;ret

8、urn 0;/*樣例輸入：55 8 4 10 310 12 15 11 20*/運行結(jié)果：2.5 思考題（1）哈夫曼編碼問題的編程如何實現(xiàn)？答：哈夫曼樹，又名最優(yōu)樹，給定n個權(quán)值作為n的葉子結(jié)點，構(gòu)造一顆二叉樹，若帶權(quán)路徑長度達到最小，成這樣的二叉樹為最優(yōu)二叉樹，也稱哈夫曼樹。實現(xiàn)步驟：1、初始化: 根據(jù)給定的n個權(quán)值w1，w2,.wn.構(gòu)成n棵二叉樹的集合F=T1,T2.Tn,其中每棵二叉樹中只有一個帶權(quán)Wi的根結(jié)點，左右子樹均空。2、 找最小樹:在F中選擇兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一-棵新的二叉樹，且至新的二叉樹的根結(jié)點的權(quán)值為其左右子樹，上根結(jié)點的權(quán)值之和。 3、刪除與加入:

9、 在F中刪除這兩棵樹，并將新的二叉樹加入F中。 4、判斷:重復前兩步(2和3)，直到F中只含有一棵樹為止。該樹即為哈夫曼樹。（2）使用貪心策略求解背包問題。答：首先計算每種物品單位重量的價值viwi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未達到w，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去直到背包滿重為止。算法的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O(nlogn)。（3）分析普里姆算法和克魯斯卡爾算法中的貪心策略。答：1、普里姆算法貪心策略：要

10、記錄到S中的下一條邊（u，v）是一條不在S中，且使得SUu,v的權(quán)值之和也是最小的邊 時間復雜度：O(n2) 空間復雜度：O(n2)2、克魯斯卡爾算法中的貪心策略：選取屬于不同聯(lián)通分量且構(gòu)成權(quán)值最小且不形成回路的兩個頂點組成的邊、本科實驗報告課程名稱： 算法設(shè)計與分析 實驗項目： 動態(tài)規(guī)劃 實驗地點： 計算機系實驗樓110 專業(yè)班級： 物聯(lián)網(wǎng)1601 學號： 2021002105 學生姓名： 俞夢真 指導教師： 郝曉麗 2021年 05月 07日實驗三 動態(tài)規(guī)劃算法3.1 實驗目的與要求1理解動態(tài)規(guī)劃算法的基本思想；2運用動態(tài)規(guī)劃算法解決實際問題，加深對貪心算法的理解和運用。3.2 實驗課時4

11、學時（課內(nèi)2學時+課外2學時）3.3 實驗原理動態(tài)規(guī)劃（Dynamic Programming）算法思想：把待求解問題分解成若干個子問題，先求解子問題，然后由這些子問題的解得到原問題的解。動態(tài)規(guī)劃求解過的子問題的結(jié)果會被保留下來，不像遞歸那樣每個子問題的求解都要從頭開始反復求解。動態(tài)規(guī)劃求解問題的關(guān)鍵在于獲得各個階段子問題的遞推關(guān)系式：（1）分析原問題的最優(yōu)解性質(zhì)，刻畫其結(jié)構(gòu)特征；（2）遞歸定義最優(yōu)值；（3）自底向上（由后向前）的方式計算最優(yōu)值；（4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。3.4 實驗題目1上機題目：最大子段和問題給定n個整數(shù)（可以為負數(shù)）組成的序列(a1,a2,an)，

12、使用動態(tài)規(guī)劃思想求該序列的子段和的最大值。注：當所有整數(shù)均為負整數(shù)時，其最大子段和為0。例如，對于六元組(-2, 11, -4, 13, -5, -2)，其最大字段和為：a2 + a3 + a4 = 20。除了動態(tài)規(guī)劃，該問題可以使用順序求和+比較（蠻力法）和分治法求解，思考其求解過程。2設(shè)計思想動態(tài)規(guī)劃思想：dpi,表示到當前i的最大字段和為多少，而他的字段和時要不就是前面的最大字段和加上本身的數(shù)值要不就是自身的數(shù)值。狀態(tài)轉(zhuǎn)移方程：dpi=max(dpi,dpi-1+ai);3代碼設(shè)計#include#include#include#includeusing namespace std;co

13、nst int maxn=1000+10;int dpmaxn;int amaxn;/動態(tài)規(guī)劃思想：dpi,表示到當前i的最大字段和為多少，而他的字段和時要不就是前面的最大字段和加上本身的數(shù)值要不就是自身的數(shù)值/dpi=max(dpi,dpi-1+ai);int main()int n;while(cinn)memset(dp,0,sizeof(dp);for(int i=0;iai,dpi=ai;int ans=0;for(int i=1;ians)ans=dpi;coutansendl;return 0;3.5 思考題（1）深刻理解動態(tài)規(guī)劃與遞歸求解問題的區(qū)別是什么？、答：動態(tài)規(guī)劃其實和分

14、治策略是類似的，也是將一個原問題分解為若干個規(guī)模較小的子問題，遞歸的求解這些子問題，然后合并子問題的解得到原問題的解。區(qū)別在于這些子問題會有重疊，一個子問題在求解后，可能會再次求解，于是我們想到將這些子問題的解存儲起來，當下次再次求解這個子問題時，直接拿過來就是。（2）動態(tài)規(guī)劃思想解題的步驟是什么？答：第一步：確定子問題。 在這一步重點是分析那些變量是隨著問題規(guī)模的變小而變小的， 那些變量與問題的規(guī)模無關(guān)。 第二步：確定狀態(tài)：根據(jù)上面找到的子問題來給你分割的子問題限定狀態(tài) 第三步：推到出狀態(tài)轉(zhuǎn)移方程：這里要注意你的狀態(tài)轉(zhuǎn)移方程是不是滿足所有的條件， 注意不要遺漏。 第四步：確定邊界條件：先根據(jù)

15、題目的限制條件來確定題目中給出的邊界條件是否能直接推導出， 如果不行也可以嘗試從邊界條件反推（舉個例子：a(n)a(2)有遞推關(guān)系， 但是a(2)a(1)不符合上述遞推關(guān)系， 我們就可以考慮用a(1)來倒推出a(2)， 然后將遞推的終點設(shè)置為a(2)）; 第五步：確定實現(xiàn)方式：這個依照個人習慣 就像是01背包的兩層for循環(huán)的順序 第六步：確定優(yōu)化方法：很多時候你會發(fā)現(xiàn)走到這里步的時候你需要返回第1步重來。首先考慮降維問題（優(yōu)化內(nèi)存）， 優(yōu)先隊列、四邊形不等式（優(yōu)化時間）等等。（3）動態(tài)規(guī)劃思想和貪心算法在求解問題時的區(qū)別是什么？答：共同點: 求解的問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)區(qū)別點:動態(tài)規(guī)劃算法

16、通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。（4）使用動態(tài)規(guī)劃算法求解最長公共子序列（LCS）問題。答：LCS問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，得其狀態(tài)轉(zhuǎn)移方程或者說遞歸式： dpij 表示記錄ai bj的LSC的長度 時間復雜度： O(m+n);ai=bj dpi-1j-1+1;ai!=bj max(dpi-1j,dpij-1);（5）使用動態(tài)規(guī)劃算法求解最長最大字段和問題。答：動態(tài)規(guī)劃思想：dpi,表示到當前i的最大字段和為多少，而他的字段和時要不就是前面的最大字段和加上本身的數(shù)值要不就是自身

17、的數(shù)值。dpi=max(dpi,dpi-1+ai)本科實驗報告課程名稱： 算法設(shè)計與分析 實驗項目： 回溯算法 實驗地點： 計算機系實驗樓110 專業(yè)班級： 物聯(lián)網(wǎng)1601 學號： 2021002105 學生姓名： 俞夢真 指導教師： 郝曉麗 2021年 05 月 07 日實驗四 回溯算法4.1 實驗目的與要求1通過回溯算法的示例程序理解回溯算法的基本思想；2運用回溯算法解決實際問題，進一步加深對回溯算法的理解和運用。4.2 實驗課時4學時（課內(nèi)2學時+課外2學時）。4.3 實驗原理回溯算法（Backtrack）的基本做法是搜索，或是一種組織得井井有條的、能避免不必要搜索的窮舉式搜索法。這種方

18、法適用于解一些組合數(shù)相當大的問題。回溯算法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解：如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索?；厮菟惴ǖ幕静襟E：（1）針對所給問題，定義問題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：（1）用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹；（2）用限界函數(shù)剪去得不到最優(yōu)解的子樹。4.4 實驗題目1上機題目：排兵布陣問題某游戲中，不同的兵

19、種處于不同的地形上時，其攻擊能力也一樣，現(xiàn)有n個不同兵種的角色(1, 2, ., n)，需安排在某戰(zhàn)區(qū)n個點上，角色i在j點上的攻擊力為Aij，使用回溯法設(shè)計一個布陣方案，使總的攻擊力最大。注：個人決定A矩陣的初始化工作。該問題求解算法的輸入數(shù)據(jù)形如附圖4所示。2設(shè)計思想：利用回溯法搜索尋找解空間樹。深度優(yōu)先搜索，設(shè)立訪問標記進行剪枝，并將總共的攻擊力作為參數(shù)不斷傳入。尋找最大的攻擊力。數(shù)值的存儲用的是二位數(shù)組，用ans_pos記錄過程。3代碼設(shè)計/角色i在j點上的攻擊力為Aij#include#include#includeusing namespace std;const int maxn

20、=100+10;int n,ans=0;int mapmaxnmaxn;bool vismaxn;int posmaxn,ans_posmaxn;void dfs(int cnt,int u)if(cnt=n)if(uans)ans=u;memcpy(ans_pos,pos,sizeof(pos);return;for(int i=0;in;i+)if(!visi)visi=1;poscnt=i+1;dfs(cnt+1,u+mapcnti);visi=0;int main()while(scanf(%d,&n)!=EOF&n)ans=0;for(int i=0;in;i+)for(int j=

21、0;jn;j+)scanf(%d,&mapij);memset(vis,0,sizeof(vis);dfs(0,0);printf(Max ATC:%dn,ans);printf(Postion: );for(int i=0;in;i+)printf(%d ,ans_posi);printf(n);return 0;/*560 40 80 50 6090 60 80 70 2030 50 40 50 8090 40 30 70 9060 80 90 60 50*/運行結(jié)果：4.5 思考題（1）什么是啟發(fā)式搜索問題？啟發(fā)式搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從

22、這個位置進行搜索直到目標。這樣可以省略大量無謂的搜索路徑，提高了效率。在啟發(fā)式搜索中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。（2）搜索算法的解空間樹的如何定義？答：解決一個問題的所有可能的決策序列就構(gòu)成了該問題的解空間。通常將解空間畫成樹的形狀，稱為解空間樹。（3）0-1背包問題的動態(tài)規(guī)劃算法如何求解？答：聲明一個 大小為 mnc 的二維數(shù)組，m i j 表示 在面對第 i 件物品，且背包容量為 j 時所能獲得的最大價值 ，那么我們可以很容易分析得出 mij 的計算方法，（1） j =wi 的情況，這時背包容量可以放下第 i 件物品，我們就要考慮拿這件物品是否能獲取更大的

23、價值。狀態(tài)轉(zhuǎn)移方程：if(j=wi) mij=max(mi-1j,mi-1j-wi+vi);else mij=mi-1j;（4）n皇后問題使用回溯法如何求解？答：首先找出解空間：給棋盤的行和列都編上1到N的號碼，皇后也給編上1到N的號碼。由于一個皇后應在不同的行上，為不失一般性，可以假定第i個皇后將放在第i行上的某列。因此N皇后問題的解空間可以用一個N元組（X1，X2，.Xn）來表示，其中Xi是放置皇后i所在的列號。這意味著所有的解都是N元組（1，2，3，.，N）的置換。解空間大小為N！。其次我們看約束條件：因為解空間已經(jīng)給我們排除了不在同一行（因為每個皇后分別已經(jīng)對應不同的行號）的約束條件。

24、我們要判斷的是不在同一列和不在同一斜線的約束。因為Xi表示皇后所在的列號，所以第k個皇后和第i個皇后同列的判斷條件是X（k）=X（i）。所以不同列的判段條件是X（k）！=X（i），1ki 。又因為同一斜線的特征是要么行號和列號之和不變（右高左低）要么是行號和列號只差相等（左高右低），所以第k個皇后和第i個皇后在同斜線的判斷條件是 i+X（i）= k+X（k) 或 i-X(i) =k-X(k),兩式合并得 |X(i)-X(k)|=|i-k| 。（5）使用回溯法求解裝載問題。答：基本思路： 容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(

25、2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近C1。由此可知，裝載問題等價于以下特殊的0-1背包問題。本科實驗報告課程名稱： 算法設(shè)計與分析 實驗項目： 分支限界算法 實驗地點： 計算機系實驗樓110 專業(yè)班級： 物聯(lián)網(wǎng)1601 學號： 2021002105 學生姓名： 俞夢真 指導教師： 郝曉麗 2021年 05 月 14 日實驗五 分支限界算法5.1 實驗目的與要求1通過分支限界算法的示例程序進一步理解分支限界算法的基本思想；2運用分支限界算法解決實際問題，進一步加深對分支限界算法的理解和運用。5.2 實驗課時4學時（

26、課內(nèi)2學時+課外2學時）。5.3 實驗原理分枝限界（Branch-and-Bound）算法是另一種系統(tǒng)地搜索解空間的方法，它與回溯算法的主要區(qū)別在于對E-結(jié)點的擴充方式。每個活結(jié)點有且僅有一次機會變成E-結(jié)點。當一個結(jié)點變?yōu)镋-結(jié)點時，則生成從該結(jié)點移動一步即可到達的所有新結(jié)點。在生成的結(jié)點中，拋棄那些不可能導出（最優(yōu)）可行解的結(jié)點，其余結(jié)點加入活結(jié)點表，然后從表中選擇一個結(jié)點作為下一個E-結(jié)點。從活結(jié)點表中取出所選擇的結(jié)點并進行擴充，直到找到解或活動表為空，擴充過程才結(jié)束。有兩種常用的方法可用來選擇下一個E-結(jié)點（雖然也可能存在其他的方法）：（1）先進先出（F I F O）即從活結(jié)點表中取出

27、結(jié)點的順序與加入結(jié)點的順序相同，因此活結(jié)點表的性質(zhì)與隊列相同。（2）（優(yōu)先隊列）最小耗費（LC）或最大收益法在這種模式中，每個結(jié)點都有一個對應的耗費或收益。如果查找一個具有最小耗費的解，則活結(jié)點表可用最小堆來建立，下一個E-結(jié)點就是具有最小耗費的活結(jié)點；如果希望搜索一個具有最大收益的解，則可用最大堆來構(gòu)造活結(jié)點表，下一個 E-結(jié)點是具有最大收益的活結(jié)點。5.4 實驗題目1上機題目：運動員最佳配對問題羽毛球隊有男女運動員各n人。給定兩個nn矩陣P和Q；Pij表示男運動員i和女運動員j配對組成混合雙打的男運動員競賽優(yōu)勢，Qij表示女運動員i和男運動員j配對組成混合雙打的女運動員競賽優(yōu)勢（注意：由于

28、多種原因，Pij 未必等于Qji），男運動員i和女運動員j配對組成混合雙打的男女運動員雙方總體競賽優(yōu)勢為Pij* Qji。用分支限界法設(shè)計一個算法，計算男女運動員的最佳配對，即各組男女運動員雙方總體競賽優(yōu)勢的總和達到最大。2設(shè)計思想對于n個男運動員，從第1個開始搭配女運動員：第1個有n種搭配方法，第2個有n-1種搭配方法第n個有n-(n-1)種搭配方法；根據(jù)問題給出的示例：輸入n的值為3，表示男女運動員各有3名；男運動員 1 2 3按順序搭配女運動員，他們分別對應的女運動員可以是：女運動員 1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1所以其解空間是(1,2,3),(1

29、,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)，整個問題可看成是1,2,3的全排列問題，將解空間組織成一棵排列樹。解空間樹的第i層到第i+1層邊上的標號給出了變量的值。從樹根到葉的任一路徑表示解空間中的一個元素。用LC分支界限法的搜索策略搜索整個解空間3代碼設(shè)計/運動員最佳配對-效益最大/分支限界法#include#include#include#include#includeusing namespace std;const int maxn=100+10;int n;int pmaxnmaxn,qmaxnmaxn;int ans_xmaxn;int vismaxn;struct nodeint dep;int win;int *x;node(int d,int w)x=new intn+1;dep=d;win=w;int get_win(