最新算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告

1、可以修改5TAIYUAN UNIVERSITY OF TECHNOLOGY本科實(shí)驗(yàn)報(bào)告課程名稱(chēng)：算法設(shè)計(jì)與分析實(shí)驗(yàn)項(xiàng)目：遞歸與分治算法實(shí)驗(yàn)地點(diǎn)：計(jì)算機(jī)系實(shí)驗(yàn)樓110專(zhuān)業(yè)班級(jí)：物聯(lián)網(wǎng)1601 學(xué)號(hào)：2016002105俞夢(mèng)真郝曉麗學(xué)生姓名:指導(dǎo)教師：實(shí)驗(yàn)一遞歸與分治算法1.1 實(shí)驗(yàn)?zāi)康呐c要求1 .進(jìn)一步熟悉 OC+語(yǔ)言的集成開(kāi)發(fā)環(huán)境；2 .通過(guò)本實(shí)驗(yàn)加深對(duì)遞歸與分治策略的理解和運(yùn)用。1.2 實(shí)驗(yàn)課時(shí)2學(xué)時(shí)1.3 實(shí)驗(yàn)原理分治(Divide-and-Conquer )的思想：一個(gè)規(guī)模為 n的復(fù)雜問(wèn)題的求解，可以劃分成若干個(gè)規(guī)模小于n的子問(wèn)題，再將子問(wèn)題的解合并成原問(wèn)題的解。需要注意的是，分治法使用

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

3、，1位是0 1。兩位是00 01 11 10。三位是000 001 011010 110 111 101 100。n位是前n-1位的2倍個(gè)。N-1個(gè)位前面加 0, N-2為倒轉(zhuǎn)再前面再加 13 .代碼設(shè)計(jì)：#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 t

4、mp;for(int j=0;j=0;j-) string s=1;s+=tmpj;My_grad.push_back(s);IIint main()int n;while(cinn) get_grad(n);for(int i=0;iMy_grad.size();i+) coutMy_gradi0, T=(t1,t2,tn),客戶(hù)i希望的服務(wù)完成時(shí)刻為di0, D=(d1,d2,dn)； 一個(gè)調(diào)度f(wàn):A-N, f(i)為客戶(hù)i的開(kāi)始時(shí)刻。如果對(duì)客戶(hù)i的服務(wù)在di之前結(jié)束，那么對(duì)客戶(hù)i的服務(wù)沒(méi)有延遲，即如果在di之后結(jié)束，那么這個(gè)服務(wù)就被延遲了，延遲的時(shí)間等于該服務(wù)的實(shí)際完成時(shí)刻f(i)+ti

5、減去預(yù)期結(jié)束時(shí)刻di。一個(gè)調(diào)度f(wàn)的最大延遲是所有客戶(hù)延遲時(shí)長(zhǎng)的最大值maxiAf(i)+ti di。附圖2所示是不同調(diào)度下的最大延遲。使用貪心策略找出一個(gè)調(diào)度使得最大延遲達(dá)到最小。2 .設(shè)計(jì)思想：貪心思想，按照他們的截止時(shí)間從小到大排序，如果截止時(shí)間相同按照花費(fèi)時(shí)間從小到大排序。然后按照 f_min (所有客戶(hù)延遲時(shí)長(zhǎng)的最大值)=max(worksi.cost+time-worksi.deadline,f_min);尋找最所有客戶(hù)延遲時(shí)長(zhǎng)的最大值。3 .代碼設(shè)計(jì)：最小延遲調(diào)度問(wèn)題輸入包含：任務(wù)，任務(wù)完成需要的時(shí)間，完成改任務(wù)的截止時(shí)間#include#include#include#inclu

6、deusing namespace std;const int maxn=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;elsereturn a.costb.cost;int dpmaxnmaxn;int main()while(scanf(%d,&n)!=EOF)for(int i=0;in;i+)scanf(%d,&worksi.cost);for(int

7、i=0;in;i+)scanf(%d”,&worksi.deadline),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

8、i=0;in;i+) coutworksi.id; coutendl;return 0;/*樣例輸入：55 8 4 10 310 12 15 11 20*/運(yùn)行結(jié)果：SB C5 8 4 10 310 12 15 11 20MaKimum delay:12Ciqplete the order of tasks ：14 2 3 52.5 思考題(1)哈夫曼編碼問(wèn)題的編程如何實(shí)現(xiàn)？答：哈夫曼樹(shù)，又名最優(yōu)樹(shù)，給定 n個(gè)權(quán)值作為n的葉子結(jié)點(diǎn)，構(gòu)造一顆二叉樹(shù)，若帶權(quán)路 徑長(zhǎng)度達(dá)到最小，成這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)哈夫曼樹(shù)。實(shí)現(xiàn)步驟：1、初始化：根據(jù)給定的 n個(gè)權(quán)值w1 , w2,wn.構(gòu)成n棵二叉樹(shù)的

9、集合F=T1,T2.加,其中每棵二叉樹(shù)中只有一個(gè)帶權(quán)Wi的根結(jié)點(diǎn)，左右子樹(shù)均空。2、找最小樹(shù)：在F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一-棵新的二叉樹(shù)，且至新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)，上根結(jié)點(diǎn)的權(quán)值之和。3、刪除與加入：在F中刪除這兩棵樹(shù)，并將新的二叉樹(shù)加入F中。4、判斷：重復(fù)前兩步(2和3),直到F中只含有一棵樹(shù)為止。該樹(shù)即為哈夫曼樹(shù)。(2)使用貪心策略求解背包問(wèn)題。答：首先計(jì)算每種物品單位重量的價(jià)值vi/wi,然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未達(dá)到w,則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝

10、入背包。依此策略一直地進(jìn)行下去直到背包滿(mǎn)重為止。算法的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排 序。因此，算法的計(jì)算時(shí)間上界為O(nlogn)。(3)分析普里姆算法和克魯斯卡爾算法中的貪心策略。答：1、普里姆算法貪心策略：要記錄到S中的下一條邊(u, v)是一條不在 S中，且使得SUu,v的權(quán)值之和也是最小的 邊時(shí)間復(fù)雜度：O(nA2)空間復(fù)雜度：O(nA2)2、克魯斯卡爾算法中的貪心策略：選取屬于不同聯(lián)通分量且構(gòu)成權(quán)值最小且不形成回路的兩個(gè)頂點(diǎn)組成的邊、黛/唬打下大?y TAIYUAN UNERSIIV OF TECHNOLOGY本科實(shí)驗(yàn)報(bào)告課程名稱(chēng)：算法設(shè)計(jì)與分析實(shí)驗(yàn)項(xiàng)目：動(dòng)

11、態(tài)規(guī)劃實(shí)驗(yàn)地點(diǎn)：計(jì)算機(jī)系實(shí)驗(yàn)樓110專(zhuān)業(yè)班級(jí)： 物聯(lián)網(wǎng)1601 學(xué)號(hào)： 2016002105學(xué)生姓名：俞夢(mèng)真指導(dǎo)教師： 郝曉麗2018年 05月07日實(shí)驗(yàn)三動(dòng)態(tài)規(guī)劃算法3.1 實(shí)驗(yàn)?zāi)康呐c要求1 .理解動(dòng)態(tài)規(guī)劃算法的基本思想；2 .運(yùn)用動(dòng)態(tài)規(guī)劃算法解決實(shí)際問(wèn)題，加深對(duì)貪心算法的理解和運(yùn)用。3.2 實(shí)驗(yàn)課時(shí)4學(xué)時(shí)(課內(nèi)2學(xué)時(shí)+課外2學(xué)時(shí))3.3 實(shí)驗(yàn)原理動(dòng)態(tài)規(guī)劃(Dynamic Programming )算法思想：把待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后由這些子問(wèn)題的解得到原問(wèn)題的解。動(dòng)態(tài)規(guī)劃求解過(guò)的子問(wèn)題的結(jié)果會(huì)被保留下來(lái)，不像遞歸那樣每個(gè)子問(wèn)題的求解都要從頭開(kāi)始反復(fù)求解。動(dòng)態(tài)規(guī)劃求解

12、問(wèn)題的關(guān)鍵在于獲得各個(gè)階段子問(wèn)題的遞推關(guān)系式：(1)分析原問(wèn)題的最優(yōu)解性質(zhì)，刻畫(huà)其結(jié)構(gòu)特征；(2)遞歸定義最優(yōu)值；(3)自底向上(由后向前)的方式計(jì)算最優(yōu)值；(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。3.4 實(shí)驗(yàn)題目1 .上機(jī)題目：最大子段和問(wèn)題給定n個(gè)整數(shù)(可以為負(fù)數(shù))組成的序列(a1,a2,an),使用動(dòng)態(tài)規(guī)劃思想求該序列的子段和的最大值。注：當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)，其最大子段和為0。例如，對(duì)于六元組(2,11, 4,13, 5, 2),其最大字段和為：a2 + a3 + a4 = 20除了動(dòng)態(tài)規(guī)劃，該問(wèn)題可以使用順序求和+比較(蠻力法)和分治法求解，思考其求解過(guò)程。2 .設(shè)計(jì)思想

13、動(dòng)態(tài)規(guī)劃思想：dpi,表示到當(dāng)前i的最大字段和為多少，而他的字段和時(shí)要不就是前面的最大字段和加上本身的數(shù)值要不就是自身的數(shù)值。狀態(tài)轉(zhuǎn)移方程：dpi=max(dpi,dpi-1+ai);3 .代碼設(shè)計(jì)#include#include#include#includeusing namespace std;const int maxn=1000+10;int dpmaxn;int amaxn;/動(dòng)態(tài)規(guī)劃思想：dpi,表示到當(dāng)前i的最大字段和為多少，而他的字段和時(shí)要不就是前面的最大字段和加上本身的數(shù)值要不就是自身的數(shù)值/dpi=max(dpi,dpi-1+ai);int main()int n;whi

14、le(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;齷 C;WI N D OWS&y&tE-rri 32crri d 田百6-2 11 -4 13 -5 -2203.5 思考題(1)深刻理解動(dòng)態(tài)規(guī)劃與遞歸求解問(wèn)題的區(qū)別是什么？、答：動(dòng)態(tài)規(guī)劃其實(shí)和分治策略是類(lèi)似的，也是將一個(gè)原問(wèn)題分解為若干個(gè)規(guī)模較小的子問(wèn)題，遞歸的求解這些子問(wèn)題，然后合并子問(wèn)題的解得到原問(wèn)題的解。區(qū)別在于這些子問(wèn)題會(huì)有重疊，一個(gè)子問(wèn)題在求解后，可能會(huì)再次求解，

15、于是我們想到將這些子問(wèn)題的解存儲(chǔ)起來(lái)，當(dāng)下次再次求解這個(gè)子問(wèn)題時(shí)，直接拿過(guò)來(lái)就是。(2)動(dòng)態(tài)規(guī)劃思想解題的步驟是什么？答：第一步：確定子問(wèn)題。在這一步重點(diǎn)是分析那些變量是隨著問(wèn)題規(guī)模的變小而變小的，那些變量與問(wèn)題的規(guī)模無(wú)關(guān)。第二步：確定狀態(tài)：根據(jù)上面找到的子問(wèn)題來(lái)給你分割的子問(wèn)題限定狀態(tài)第三步：推到出狀態(tài)轉(zhuǎn)移方程：這里要注意你的狀態(tài)轉(zhuǎn)移方程是不是滿(mǎn)足所有的條件，注意不要遺漏。第四步：確定邊界條件：先根據(jù)題目的限制條件來(lái)確定題目中給出的邊界條件是否能直接推導(dǎo)出，如果不行也可以嘗試從邊界條件反推(舉個(gè)例子：a(n) -a(2)遞推關(guān)系，但是a(2)-a(1)不符合上述遞推關(guān)系，我們就可以考慮用 a

16、(1)來(lái)倒推出a(2),然后將遞推的終點(diǎn)設(shè)置為a(2);第五步：確定實(shí)現(xiàn)方式：這個(gè)依照個(gè)人習(xí)慣就像是01背包的兩層for循環(huán)的順序第六步：確定優(yōu)化方法：很多時(shí)候你會(huì)發(fā)現(xiàn)走到這里步的時(shí)候你需要返回第1步重來(lái)。首先考慮降維問(wèn)題(優(yōu)化內(nèi)存)，優(yōu)先隊(duì)列、四邊形不等式(優(yōu)化時(shí)間)等等。(3)動(dòng)態(tài)規(guī)劃思想和貪心算法在求解問(wèn)題時(shí)的區(qū)別是什么？答：共同點(diǎn)：求解的問(wèn)題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)區(qū)別點(diǎn)：動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。(4)使用動(dòng)態(tài)規(guī)劃算法求解最長(zhǎng)公共子序列( LCS)問(wèn)

17、題。答：LCS問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，得其狀態(tài)轉(zhuǎn)移方程或者說(shuō)遞歸式：dpij表示記錄aibj的LSC的長(zhǎng)度 時(shí)間復(fù)雜度：O(m+n);ai=bjdpi-1j-1+1；ai!=bjmax(dpi-1j,dpij-1);(5)使用動(dòng)態(tài)規(guī)劃算法求解最長(zhǎng)最大字段和問(wèn)題。答：動(dòng)態(tài)規(guī)劃思想：dpi,表示到當(dāng)前i的最大字段和為多少，而他的字段和時(shí)要不就是前面的最大字段和加上本身的數(shù)值要不就是自身的數(shù)值。dpi=max(dpi,dpi-1+ai)14可以修改20TAIYUAN UNERSIIV OF TECHNOLOGY本科實(shí)驗(yàn)報(bào)告課程名稱(chēng)：算法設(shè)計(jì)與分析實(shí)驗(yàn)項(xiàng)目：回溯算法實(shí)驗(yàn)地點(diǎn)：計(jì)算機(jī)系實(shí)驗(yàn)樓110專(zhuān)業(yè)班級(jí)

18、:物聯(lián)網(wǎng)1601 學(xué)號(hào)： 2016002105俞夢(mèng)真郝曉麗學(xué)生姓名:指導(dǎo)教師：實(shí)驗(yàn)四回溯算法4.1 實(shí)驗(yàn)?zāi)康呐c要求1 .通過(guò)回溯算法的示例程序理解回溯算法的基本思想；2 .運(yùn)用回溯算法解決實(shí)際問(wèn)題，進(jìn)一步加深對(duì)回溯算法的理解和運(yùn)用。4.2 實(shí)驗(yàn)課時(shí)4學(xué)時(shí)(課內(nèi)2學(xué)時(shí)+課外2學(xué)時(shí))。4.3 實(shí)驗(yàn)原理回溯算法(Backtrack)的基本做法是搜索，或是一種組織得井井有條的、能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題?；厮菟惴ㄔ趩?wèn)題的解空間樹(shù)中， 按深度優(yōu)先策略， 從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。 算法搜索至 解空間樹(shù)的任意一點(diǎn)時(shí)， 先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解： 如果肯定不包

19、含， 則跳過(guò)對(duì)該結(jié)點(diǎn)為 根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索?；厮菟惴ǖ幕静襟E：(1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。常用剪枝函數(shù)：(1)用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿(mǎn)足約束的子樹(shù)；(2)用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)。4.4 實(shí)驗(yàn)題目1 .上機(jī)題目：排兵布陣問(wèn)題某游戲中，不同的兵種處于不同的地形上時(shí)，其攻擊能力也一樣，現(xiàn)有n個(gè)不同兵種的角色（1,2,，n）,需安排在某戰(zhàn)區(qū) n個(gè)點(diǎn)上，角色i在j點(diǎn)上的攻擊力為 Aj,使用回溯法設(shè)計(jì)一個(gè)布 陣方案，使

20、總的攻擊力最大。注：個(gè)人決定A矩陣的初始化工作。該問(wèn)題求解算法的輸入數(shù)據(jù)形如附圖4所示。2 .設(shè)計(jì)思想：利用回溯法搜索尋找解空間樹(shù)。深度優(yōu)先搜索，設(shè)立訪問(wèn)標(biāo)記進(jìn)行剪枝，并將總共的攻擊力作為參數(shù)不斷傳入。尋找最大的攻擊力。數(shù)值的存儲(chǔ)用的是二位數(shù)組，用ans_pos記錄過(guò)程。3 .代碼設(shè)計(jì)/角色i在j點(diǎn)上的攻擊力為Aij#include#include#includeusing namespace std;const int maxn=100+10;int n,ans=0;int mapmaxnmaxn;bool vismaxn;int posmaxn,ans_posmaxn;void dfs(i

21、nt 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=0;jn;j+)scanf(%d”,&mapij);memset(vis,0,sizeof(vis);dfs(0,0)；printf(Max ATC:%dn,ans)

22、;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*/運(yùn)行結(jié)果:曬 C:WI NDOW$iystem 3d. cjjc56。 46 80 50 609(1 60 80 70 20J Cl 50 40 50 8090 40 30 70 906。 80 90 60 50Kik ATC：400 pjstian: 315424.5 思考題(1)什么是啟發(fā)式搜

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

24、這時(shí)背包容量可以放下第i件物品，我們就要考慮拿這件物品是否能獲取更大的價(jià)值。狀態(tài)轉(zhuǎn)移方程：if(j=wi)mij=max(mi-1皿mi-1j-wi+vi);elsemij=mi-1j；(4) n皇后問(wèn)題使用回溯法如何求解？答：首先找出解空間：給棋盤(pán)的行和列都編上1到N的號(hào)碼，皇后也給編上1到N的號(hào)碼。由于一個(gè)皇后應(yīng)在不同的行上，為不失一般性，可以假定第i個(gè)皇后將放在第i行上的某列。因此N皇后問(wèn)題的解空間可以用一個(gè)N元組(X1 , X2,.Xn)來(lái)表示，其中 Xi是放置皇后i所在的列號(hào)。這意味著所有的解都是N元組(1, 2, 3,.，N)的置換。解空間大小為N!。其次我們看約束條件：因?yàn)榻饪臻g

25、已經(jīng)給我們排除了不在同一行(因?yàn)槊總€(gè)皇后分別已經(jīng)對(duì)應(yīng)不同的行號(hào))的約束條件。我們要判斷的是不在同一列和不在同一斜線(xiàn)的約束。因?yàn)閄i表示皇后所在的列號(hào)，所以第 k個(gè)皇后和第i個(gè)皇后同列的判斷條件是X (k) =X (i)。所以不同列的判段條件是X (k)! =X (i), 1ki。又因?yàn)橥恍本€(xiàn)的特征是要么行號(hào)和列號(hào)之和不變(右高左低)要么是行號(hào)和列號(hào)只差相等(左高右低)，所以第k個(gè)皇后和第i個(gè)皇后在同斜線(xiàn)的判斷條件是i+X (i) = k+X (k)或 i-X(i) =k-X(k),兩式合并得 |X(i)-X(k)|=|i-k|。(5) 使用回溯法求解裝載問(wèn)題。答：基本思路：容易證明，如果一個(gè)

26、給定裝載問(wèn)題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿(mǎn)；(2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿(mǎn)等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱重量之和最接近C1。由此可知，裝載問(wèn)題等價(jià)于以下特殊的0-1背包問(wèn)題?？梢孕薷?7TAIYUAN UNERSIIV OF TECHNOLOGY本科實(shí)驗(yàn)報(bào)告課程名稱(chēng)：算法設(shè)計(jì)與分析實(shí)驗(yàn)項(xiàng)目：分支限界算法實(shí)驗(yàn)地點(diǎn)：計(jì)算機(jī)系實(shí)驗(yàn)樓110專(zhuān)業(yè)班級(jí):物聯(lián)網(wǎng)1601 學(xué)號(hào)： 2016002105俞夢(mèng)真郝曉麗學(xué)生姓名:指導(dǎo)教師：實(shí)驗(yàn)五分支限界算法5.1 實(shí)驗(yàn)?zāi)康呐c要求1 .通過(guò)分支限界算法的示例程序進(jìn)一步理解分支限界

27、算法的基本思想；2 .運(yùn)用分支限界算法解決實(shí)際問(wèn)題，進(jìn)一步加深對(duì)分支限界算法的理解和運(yùn)用。5.2 實(shí)驗(yàn)課時(shí)4學(xué)時(shí)（課內(nèi)2學(xué)時(shí)+課外2學(xué)時(shí)）。5.3 實(shí)驗(yàn)原理分枝限界（Branch-and-Bound ）算法是另一種系統(tǒng)地搜索解空間的方法，它與回溯算法的主要區(qū)別在于對(duì)E-結(jié)點(diǎn)的擴(kuò)充方式。每個(gè)活結(jié)點(diǎn)有且僅有一次機(jī)會(huì)變成E-結(jié)點(diǎn)。當(dāng)一個(gè)結(jié)點(diǎn)變?yōu)镋-結(jié)點(diǎn)時(shí)，則生成從該結(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所有新結(jié)點(diǎn)。在生成的結(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的結(jié)點(diǎn)，其余結(jié)點(diǎn)加入活結(jié)點(diǎn)表，然后從表中選擇一個(gè)結(jié)點(diǎn)作為下一個(gè)E-結(jié)點(diǎn)。從活結(jié)點(diǎn)表中取出所選擇的結(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充過(guò)程才結(jié)束。有兩

28、種常用的方法可用來(lái)選擇下一個(gè)E-結(jié)點(diǎn)（雖然也可能存在其他的方法）：（1）先進(jìn)先出（FI F O）即從活結(jié)點(diǎn)表中取出結(jié)點(diǎn)的順序與加入結(jié)點(diǎn)的順序相同，因此活結(jié) 點(diǎn)表的性質(zhì)與隊(duì)列相同。（2）（優(yōu)先隊(duì)列）最小耗費(fèi)（LC）或最大收益法在這種模式中，每個(gè)結(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的耗費(fèi)或收益。如果查找一個(gè)具有最小耗費(fèi)的解，則活結(jié)點(diǎn)表可用最小堆來(lái)建立，下一個(gè)E-結(jié)點(diǎn)就是具有最小耗費(fèi)的活結(jié)點(diǎn)； 如果希望搜索一個(gè)具有最大收益的解，則可用最大堆來(lái)構(gòu)造活結(jié)點(diǎn)表，下一個(gè)E-結(jié)點(diǎn)是具有最大收益的活結(jié)點(diǎn)。5.4 實(shí)驗(yàn)題目1 .上機(jī)題目：運(yùn)動(dòng)員最佳配對(duì)問(wèn)題羽毛球隊(duì)有男女運(yùn)動(dòng)員各n人。給定兩個(gè)nxn矩BP和Q; Pij表示男運(yùn)動(dòng)員i和

29、女運(yùn)動(dòng)員j配對(duì)組成混合雙打的男運(yùn)動(dòng)員競(jìng)賽優(yōu)勢(shì)，Qij表示女運(yùn)動(dòng)員i和男運(yùn)動(dòng)員j配對(duì)組成混合雙打的女運(yùn)動(dòng)員競(jìng)賽優(yōu)勢(shì)(注意：由于多種原因，Pij未必等于Qji),男運(yùn)動(dòng)員i和女運(yùn)動(dòng)員j配對(duì)組成混合雙打的男女運(yùn)動(dòng)員雙方總體競(jìng)賽優(yōu)勢(shì)為Pi j* Qji。用分支限界法設(shè)計(jì)一個(gè)算法，計(jì)算男女運(yùn)動(dòng)員的最佳配對(duì)，即各組男女運(yùn)動(dòng)員雙方總體競(jìng)賽優(yōu)勢(shì)的總和達(dá)到最大。2 .設(shè)計(jì)思想對(duì)于n個(gè)男運(yùn)動(dòng)員，從第1個(gè)開(kāi)始搭配女運(yùn)動(dòng)員：第 1個(gè)有n種搭配方法，第2個(gè)有n-1種搭配方法第n個(gè)有n-(n-1)種搭配方法；根據(jù)問(wèn)題給出的示例：輸入 n的值為3,表示男女運(yùn) 動(dòng)員各有3名；男運(yùn)動(dòng)員123按順序搭配女運(yùn)動(dòng)員，他們分別對(duì)應(yīng)的女

30、運(yùn)動(dòng)員可以是：女運(yùn)動(dòng)員 1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1所以其解空間是(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1),整個(gè)問(wèn)題可看成是 1,2,3 的全排 列問(wèn)題，將解空間組織成一棵排列樹(shù)。解空間樹(shù)的第i層到第i+1層邊上的標(biāo)號(hào)給出了變量的值。從樹(shù)根到葉的任一路徑表示解空間中的一個(gè)元素。用LC分支界限法的搜索策略搜索整個(gè)解空間3 .代碼設(shè)計(jì)/運(yùn)動(dòng)員最佳配對(duì)-效益最大/分支限界法#include#include#include#include#include using namespace std; const

31、 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()int temp=0;for(int i=1;i=dep;i+) temp+=pixi*qxii;return temp;bool operator (const node &u)constreturn winu.win;int bfs()priority_queue q;node t(0