1、算法分析與設(shè)計(jì)實(shí)驗(yàn)指導(dǎo).實(shí)驗(yàn)一 錦標(biāo)賽問(wèn)題實(shí)驗(yàn)?zāi)康?. 基本掌握分治算法的原理.2. 能用程序設(shè)計(jì)語(yǔ)言求解錦標(biāo)賽等問(wèn)題的算法;預(yù)習(xí)要求1. 認(rèn)真閱讀數(shù)據(jù)結(jié)構(gòu)教材和算法設(shè)計(jì)教材,了解分治算法原理;2. 設(shè)計(jì)用分治算法求解背包問(wèn)題的數(shù)據(jù)結(jié)構(gòu)與程序代碼.實(shí)驗(yàn)題【問(wèn)題描述】設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽?，F(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：（1）每個(gè)選手必須與其他n-1個(gè)選手各賽一次； （2）每個(gè)選手一天只能參賽一次； （3）循環(huán)賽在n-1天內(nèi)結(jié)束。 請(qǐng)按此要求將比賽日程表設(shè)計(jì)成有n行和n-1列的一個(gè)表。在表中的第i行，第j列處填入第i個(gè)選手在第j天所遇到的選手。其中1in，1jn-1。 實(shí)驗(yàn)

2、提示我們可以按分治策略將所有的選手分為兩半，則n個(gè)選手的比賽日程表可以通過(guò)n/2個(gè)選手的比賽日程表來(lái)決定。遞歸地用這種一分為二的策略對(duì)選手進(jìn)行劃分，直到只剩下兩個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這兩個(gè)選手進(jìn)行比賽就可以了。12345671234567821436785341278561234321856712345678143212143658721431234127856321421432187654321（1） （2） （3）圖1 2個(gè)、4個(gè)和8個(gè)選手的比賽日程表圖1所列出的正方形表（3）是8個(gè)選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5至選手8

3、前3天的比賽日程。據(jù)此，將左上角小塊中的所有數(shù)字按其相對(duì)位置抄到右下角，又將左下角小塊中的所有數(shù)字按其相對(duì)位置抄到右上角，這樣我們就分別安排好了選手1至選手4和選手5至選手8在后4天的比賽日程。依此思想容易將這個(gè)比賽日程表推廣到具有任意多個(gè)選手的情形。 實(shí)驗(yàn)步驟1. 設(shè)計(jì)并實(shí)現(xiàn)算法并準(zhǔn)備測(cè)試用例,修改并調(diào)試程序,直至正確為止;2. 應(yīng)用設(shè)計(jì)的算法和程序求錦標(biāo)賽問(wèn)題;3. 去掉測(cè)試程序,將你的程序整理成功能模塊存盤(pán)備用. 實(shí)驗(yàn)報(bào)告要求1. 闡述實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)內(nèi)容;2. 闡述分治算法原理;3. 提交實(shí)驗(yàn)程序的功能模塊;4. 記錄最終測(cè)試數(shù)據(jù)和測(cè)試結(jié)果。思考與練習(xí)【金塊問(wèn)題】老板有一袋金塊(共n塊，

4、n是2的冪（n>=2），將有兩名最優(yōu)秀的雇員每人得到其中的一塊，排名第一的得到最重的那塊，排名第二的雇員得到袋子中最輕的金塊。假設(shè)有一臺(tái)比較重量的儀器，請(qǐng)用最少的比較次數(shù)找出最重和最輕的金塊。實(shí)驗(yàn)二 背包問(wèn)題實(shí)驗(yàn)?zāi)康?. 能用程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)求解背包問(wèn)題的算法;4. 基本掌握動(dòng)態(tài)規(guī)劃法（貪心）的原理方法.預(yù)習(xí)要求3. 認(rèn)真閱讀數(shù)據(jù)結(jié)構(gòu)教材和算法設(shè)計(jì)教材,了解背包問(wèn)題的常用算法原理;4. 設(shè)計(jì)用動(dòng)態(tài)規(guī)劃算法求解背包問(wèn)題的數(shù)據(jù)結(jié)構(gòu)和遞歸程序.實(shí)驗(yàn)題【背包問(wèn)題】有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過(guò)指定的限制重量W，但選中物品的價(jià)值之

5、和最大。實(shí)驗(yàn)提示設(shè)n件物品的重量分別為w0、w1、wn-1，物品的價(jià)值分別為v0、v1、vn-1。采用遞歸尋找物品的選擇方案。設(shè)前面已有了多種選擇的方案，并保留了其中總價(jià)值最大的方案于數(shù)組option ，該方案的總價(jià)值存于變量maxv。當(dāng)前正在考察新方案，其物品選擇情況保存于數(shù)組cop 。假定當(dāng)前方案已考慮了前i-1件物品，現(xiàn)在要考慮第i件物品；當(dāng)前方案已包含的物品的重量之和為tw；至此，若其余物品都選擇是可能的話，本方案能達(dá)到的總價(jià)值的期望值為tv。算法引入tv是當(dāng)一旦當(dāng)前方案的總價(jià)值的期望值也小于前面方案的總價(jià)值maxv時(shí)，繼續(xù)考察當(dāng)前方案變成無(wú)意義的工作，應(yīng)終止當(dāng)前方案，立即去考察下一個(gè)

6、方案。因?yàn)楫?dāng)方案的總價(jià)值不比maxv大時(shí)，該方案不會(huì)被再考察，這同時(shí)保證函數(shù)后找到的方案一定會(huì)比前面的方案更好。對(duì)于第i件物品的選擇考慮有兩種可能：（1） 考慮物品i被選擇，這種可能性僅當(dāng)包含它不會(huì)超過(guò)方案總重量限制時(shí)才是可行的。選中后，繼續(xù)遞歸去考慮其余物品的選擇。（2） 考慮物品i不被選擇，這種可能性僅當(dāng)不包含物品i也有可能會(huì)找到價(jià)值更大的方案的情況。按以上思想寫(xiě)出遞歸算法如下：try(物品i，當(dāng)前選擇已達(dá)到的重量和，本方案可能達(dá)到的總價(jià)值tv)/*考慮物品i包含在當(dāng)前方案中的可能性*/if(包含物品i是可以接受的)將物品i包含在當(dāng)前方案中；if (i<n-1)try(i+1,tw+

7、物品i的重量,tv);else/*又一個(gè)完整方案，因?yàn)樗惹懊娴姆桨负茫运鳛樽罴逊桨?/以當(dāng)前方案作為臨時(shí)最佳方案保存;恢復(fù)物品i不包含狀態(tài)；/*考慮物品i不包含在當(dāng)前方案中的可能性*/if (不包含物品i僅是可男考慮的)if (i<n-1)try(i+1,tw,tv-物品i的價(jià)值)；else/*又一個(gè)完整方案，因它比前面的方案好，以它作為最佳方案*/以當(dāng)前方案作為臨時(shí)最佳方案保存;為了理解上述算法，特舉以下實(shí)例。設(shè)有4件物品，它們的重量和價(jià)值見(jiàn)表：物品0123重量5321價(jià)值4431并設(shè)限制重量為7。則按以上算法，下圖表示找解過(guò)程。由圖知，一旦找到一個(gè)解，算法就進(jìn)一步找更好的佳。如

8、能判定某個(gè)查找分支不會(huì)找到更好的解，算法不會(huì)在該分支繼續(xù)查找，而是立即終止該分支，并去考察下一個(gè)分支。Try(0,0,12)Try(1,5,12)Try(1,0,8)Try(2,5,8)Try(3,7,8)Try(2,3,8)Try(3,5,8)不能得到更好的解不能得到更好的解超重不能得到更好的解得到解：(1,0,1,0)maxv=7得到解：(0,1,1,1)maxv=8不能得到更好的解超重 實(shí)驗(yàn)步驟4. 設(shè)計(jì)并實(shí)現(xiàn)算法并準(zhǔn)備測(cè)試用例,修改并調(diào)試程序,直至正確為止;5. 應(yīng)用設(shè)計(jì)的算法和程序求解背包問(wèn)題;6. 去掉測(cè)試程序,將你的程序整理成功能模塊存盤(pán)備用. 實(shí)驗(yàn)報(bào)告要求5. 闡述實(shí)驗(yàn)?zāi)康暮蛯?shí)

9、驗(yàn)內(nèi)容;6. 闡述求解背包問(wèn)題的算法原理;7. 提交實(shí)驗(yàn)程序的功能模塊;8. 記錄最終測(cè)試數(shù)據(jù)和測(cè)試結(jié)果。思考與練習(xí)請(qǐng)用其它的算法（如貪心、分支限界等）求解背包問(wèn)題。實(shí)驗(yàn)三 作業(yè)調(diào)度問(wèn)題 實(shí)驗(yàn)?zāi)康?.熟悉多機(jī)調(diào)度問(wèn)題的算法；2.進(jìn)一步掌握貪心算法3.提高分析與解決問(wèn)題的能力。 預(yù)習(xí)要求1.認(rèn)真閱讀教材或參考書(shū), 掌握貪心算法的基本思想；2.寫(xiě)出求解“作業(yè)調(diào)度”的程序；3.設(shè)計(jì)好測(cè)試用例。實(shí)驗(yàn)題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。實(shí)驗(yàn)提示1.

10、把作業(yè)按加工所用的時(shí)間從大到小排序；2.如果作業(yè)數(shù)目比機(jī)器的數(shù)目少或相等，則直接把作業(yè)分配下去；3 .如果作業(yè)數(shù)目比機(jī)器的數(shù)目多，則每臺(tái)機(jī)器上先分配一個(gè)作業(yè)，如下的作業(yè)分配時(shí)，是選那個(gè)表頭上s最小的鏈表加入新作業(yè)。typedef struct Job    int ID;/作業(yè)號(hào)    int time;/作業(yè)所花費(fèi)的時(shí)間Job; typedef struct JobNode /作業(yè)鏈表的節(jié)點(diǎn)    int ID;     int time; &

11、#160;  JobNode *next;JobNode,*pJobNode; typedef struct Header  /鏈表的表頭    int s;    pJobNode next;Header,pHeader; int SelectMin(Header* M,int m)    int k=0;    for(int i=1;i<m;i+)        &

12、#160;   if(Mi.s<mk.s)k=i;        return k; 實(shí)驗(yàn)步驟1先用貪心算法求解該問(wèn)題，并測(cè)試你的程序，直至正確為止；2針對(duì)問(wèn)題實(shí)例，實(shí)錄運(yùn)行時(shí)的輸入、輸出文件；3將你的程序和實(shí)錄的界面存盤(pán)備用。 實(shí)驗(yàn)報(bào)告要求闡述實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)內(nèi)容；1提交模塊化的實(shí)驗(yàn)程序源代碼；2簡(jiǎn)述程序的測(cè)試過(guò)程，提交實(shí)錄的輸入、輸出文件；3鼓勵(lì)對(duì)實(shí)驗(yàn)內(nèi)容展開(kāi)討論，鼓勵(lì)提交思考與練習(xí)題的代碼和測(cè)試結(jié)果。實(shí)驗(yàn)四 回溯算法設(shè)計(jì)實(shí)驗(yàn)?zāi)康?. 掌握回溯法解題的基本思想；2. 掌握回溯算法的設(shè)計(jì)方法；3.

13、針對(duì)子集和數(shù)問(wèn)題，熟練掌握回溯遞歸算法、迭代算法的設(shè)計(jì)與實(shí)現(xiàn)。預(yù)習(xí)要求1. 認(rèn)真閱讀教材或參考書(shū), 掌握回溯法解題的基本思想, 算法的抽象控制策略；2. 了解子集和數(shù)問(wèn)題及解向量的定長(zhǎng)和變長(zhǎng)狀態(tài)空間表示；3. 針對(duì)解向量的定長(zhǎng)表示, 設(shè)計(jì)狀態(tài)空間樹(shù)節(jié)點(diǎn)擴(kuò)展的規(guī)范(限界)函數(shù)及實(shí)現(xiàn)方法；4. 分析深度優(yōu)先擴(kuò)展?fàn)顟B(tài)空間樹(shù)節(jié)點(diǎn)或回溯的條件；5. 分析和設(shè)計(jì)生成解向量各分量可選值的實(shí)現(xiàn)方法；6. 設(shè)計(jì)和編制回溯算法的遞歸和迭代程序。實(shí)驗(yàn)題【組合數(shù)】找出從自然數(shù)1，2，n中任取r個(gè)數(shù)的所有組合。實(shí)驗(yàn)提示回溯法也稱為試探法，該方法首先暫時(shí)放棄關(guān)于問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候選解按某種順序逐一枚舉和檢驗(yàn)

14、。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí)，就選擇下一個(gè)候選解；倘若當(dāng)前候選解除了還不滿足問(wèn)題規(guī)模要求外，滿足所有其他要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問(wèn)題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問(wèn)題的一個(gè)解。在回溯法中，放棄當(dāng)前候選解，尋找下一個(gè)候選解的過(guò)程稱為回溯。擴(kuò)大當(dāng)前候選解的規(guī)模，以繼續(xù)試探的過(guò)程稱為向前試探?？梢圆捎没厮莘ㄕ覇?wèn)題的解，將找到的組合以從小到大順序存于a0，a1，ar-1中，組合的元素滿足以下性質(zhì)：（1）  ai+1>ai，后一個(gè)數(shù)字比前一個(gè)大；（2）  ai-i<=n-r+1。按回溯法的思想，找解過(guò)程

15、可以敘述如下：首先放棄組合數(shù)個(gè)數(shù)為r的條件，候選組合從只有一個(gè)數(shù)字1開(kāi)始。因該候選解滿足除問(wèn)題規(guī)模之外的全部條件，擴(kuò)大其規(guī)模，并使其滿足上述條件（1），候選組合改為1，2。繼續(xù)這一過(guò)程，得到候選組合1，2，3。該候選解滿足包括問(wèn)題規(guī)模在內(nèi)的全部條件，因而是一個(gè)解。在該解的基礎(chǔ)上，選下一個(gè)候選解，因a2上的3調(diào)整為4，以及以后調(diào)整為5都滿足問(wèn)題的全部要求，得到解1，2，4和1，2，5。由于對(duì)5不能再作調(diào)整，就要從a2回溯到a1，這時(shí)，a1=2，可以調(diào)整為3，并向前試探，得到解1，3，4。重復(fù)上述向前試探和向后回溯，直至要從a0再回溯時(shí)，說(shuō)明已經(jīng)找完問(wèn)題的全部解。按上述思想寫(xiě)成程序如下： void

16、 comb(int n,int r)int i,j; i=0;ai=1;do if (ai-i<=n-r+1)/*還可以向前試探*/ if (i=r-1)/*已找到一個(gè)組合*/ for (j=0;j<r;j+) printf(“%4d”,aj); printf(“n”); ai+; continue;i+;ai = ai-1 + 1; /*向前試探*/ else if (i=0) return;/*已找到所有解*/ a-i+; /*回溯*/while (1); 實(shí)驗(yàn)步驟1. 錄入、修改并測(cè)試你的程序，直至正確為止；2. 針對(duì)問(wèn)題實(shí)例，實(shí)錄運(yùn)行時(shí)的輸入、輸出界面；3. 將你的程序和實(shí)

17、錄的界面存盤(pán)備用。實(shí)驗(yàn)報(bào)告要求1. 闡述實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)內(nèi)容；2. 提交模塊化的實(shí)驗(yàn)程序源代碼；3. 簡(jiǎn)述程序的測(cè)試過(guò)程，提交實(shí)錄的輸入、輸出界面；4. 鼓勵(lì)對(duì)實(shí)驗(yàn)內(nèi)容展開(kāi)討論，鼓勵(lì)提交思考與練習(xí)題的代碼和測(cè)試結(jié)果。思考與練習(xí)1在3×3個(gè)方格的方陣中要填入數(shù)字1到N（N10）內(nèi)的某9個(gè)數(shù)字，每個(gè)方格填一個(gè)整數(shù)，似的所有相鄰兩個(gè)方格內(nèi)的兩個(gè)整數(shù)之和為質(zhì)數(shù)。試求出所有滿足這個(gè)要求的各種數(shù)字填法。2試針對(duì)0/1背包問(wèn)題設(shè)計(jì)回溯算法，比較與子集和數(shù)問(wèn)題的算法差異。3求出在一個(gè)n×n的棋盤(pán)上，放置n個(gè)不能互相捕捉的國(guó)際象棋“皇后”的所有布局。實(shí)驗(yàn)五 旅行商問(wèn)題實(shí)驗(yàn)?zāi)康?掌握分支限界法算

18、法的解題的基本思想和設(shè)計(jì)方法；2區(qū)分分支限界算法與回溯算法的區(qū)別，加深對(duì)分支限界法的理解；3理解分支限界法算法中的限界函數(shù)應(yīng)遵循正確、準(zhǔn)確、高效的設(shè)計(jì)原則。預(yù)習(xí)要求1認(rèn)真閱讀教材或參考書(shū), 掌握分支限界法解題的基本思想；2設(shè)計(jì)狀態(tài)空間樹(shù)節(jié)點(diǎn)擴(kuò)展的規(guī)范(限界)函數(shù)及實(shí)現(xiàn)方法；3分析和設(shè)計(jì)生成解向量各分量可選值的實(shí)現(xiàn)方法。實(shí)驗(yàn)題某售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費(fèi))。他要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一次，最后回到駐地的路線，使總的路程(或總旅費(fèi))最小。 設(shè)計(jì)提示用分支限界求解旅行商問(wèn)題，其解空間是一個(gè)排列樹(shù)。有兩種基本的實(shí)現(xiàn)方法。第一種是只使用一個(gè)優(yōu)先隊(duì)列，隊(duì)列中的每個(gè)

19、元素中都包含到達(dá)根的路徑。另一種是保留一個(gè)部分解空間樹(shù)和一個(gè)優(yōu)先隊(duì)列，優(yōu)先隊(duì)列中的元素并不包含到達(dá)根的路徑。 參考數(shù)據(jù)類型或變量  /* 定義邊結(jié)構(gòu) */typedef struct _EDGE int head; int tail; EDGE;/* 定義路徑結(jié)構(gòu) */typedef struct _PATH EDGE edgeMAX_CITIES; int edgesNumber; PATH;/* 定義花費(fèi)矩陣結(jié)構(gòu) */typedef struct _MATRIX int distanceMAX_CITIESMAX_CITIES; int citiesNumber; MATRIX;

20、/* 定義樹(shù)結(jié)點(diǎn) */typedef struct _NODE int bound; / 相應(yīng)于本結(jié)點(diǎn)的花費(fèi)下界 MATRIX matrix; / 當(dāng)前花費(fèi)矩陣 PATH path; / 已經(jīng)選定的邊 struct _NODE* left; / 左枝 struct _NODE* right; / 右枝 NODE;參考子程序接口與功能描述int Simplify(MATRIX* c)功能：歸約費(fèi)用矩陣，返回費(fèi)用矩陣的歸約常數(shù) EDGE SelectBestEdge(MATRIX c)功能： 搜索所有花費(fèi)為零的邊中最合適的，使左枝下界更大 MATRIX LeftNode(MATRIX c, EDG

21、E edge)功能： 刪掉所選分枝邊 MATRIX RightNode(MATRIX c, EDGE edge, PATH path)功能： 刪除行列和回路邊后的矩陣 EDGE LoopEdge(PATH path, EDGE edge)功能： 計(jì)算回路邊的函數(shù)，除了加入的新邊，當(dāng)前結(jié)點(diǎn)路線集合中還可能包含一些已經(jīng)選定的邊，這些邊構(gòu)成一條或幾條路徑，為了不構(gòu)成回路，必須使其中包含新邊的路徑頭尾不能相連，本函數(shù)返回這個(gè)頭尾相連的邊，以便把這個(gè)回路邊的長(zhǎng)度設(shè)成無(wú)窮。int MatrixSize(MATRIX c, PATH path)功能： 計(jì)算花費(fèi)矩陣當(dāng)前階數(shù) void ShowPath(PAT

22、H path, MATRIX c)功能：顯示路徑void ShowMatrix(MATRIX c)功能： 顯示花費(fèi)矩陣 實(shí)驗(yàn)步驟1錄入、修改并測(cè)試你的程序，直至正確為止；2針對(duì)問(wèn)題實(shí)例，實(shí)錄運(yùn)行時(shí)的輸入、輸出界面；3將你的程序和實(shí)錄的界面存盤(pán)備用。實(shí)驗(yàn)報(bào)告要求1闡述實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)內(nèi)容；2提交模塊化的實(shí)驗(yàn)程序源代碼；3簡(jiǎn)述程序的測(cè)試過(guò)程，提交實(shí)錄的輸入、輸出文件；4鼓勵(lì)對(duì)實(shí)驗(yàn)內(nèi)容展開(kāi)討論，鼓勵(lì)提交思考與練習(xí)題的代碼和測(cè)試結(jié)果。思考與練習(xí)1試針對(duì)作業(yè)調(diào)度問(wèn)題設(shè)計(jì)分支限界算法，并上機(jī)測(cè)試其正確性。2試對(duì)本實(shí)驗(yàn)中的問(wèn)題，用回溯解法求解，并比較這兩種算法的區(qū)別與執(zhí)行效率。附：實(shí)驗(yàn)（設(shè)計(jì)）報(bào)告參考格式設(shè)計(jì)一多段圖問(wèn)題的動(dòng)態(tài)規(guī)劃算法與實(shí)現(xiàn)一、 實(shí)驗(yàn)?zāi)康?. 掌握有向網(wǎng)的成本鄰接矩陣表示法；2. 掌握多段圖問(wèn)題的動(dòng)態(tài)規(guī)劃遞推算法；3. 進(jìn)一步掌握動(dòng)態(tài)規(guī)劃法的基本思想和算法設(shè)計(jì)方法；二、 實(shí)驗(yàn)內(nèi)容1 任務(wù)描述1）多段圖問(wèn)題簡(jiǎn)介2）設(shè)計(jì)任務(wù)簡(jiǎn)介設(shè)計(jì)求解多段圖問(wèn)題的動(dòng)態(tài)規(guī)劃算法，即設(shè)計(jì)和實(shí)現(xiàn)多段圖問(wèn)題的表示方案、動(dòng)態(tài)規(guī)劃遞推算法，設(shè)計(jì)對(duì)算法或程序的測(cè)試方案并完成測(cè)試。2 多段圖問(wèn)題的表示方案本設(shè)計(jì)采用成本鄰接矩陣表示多段圖，針對(duì)多段圖(可插入圖例)描述成本鄰接矩陣的規(guī)模與元素意義3 遞推過(guò)程