《算法設(shè)計(jì)與分析 綜合設(shè)計(jì)性實(shí)驗(yàn)》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《算法設(shè)計(jì)與分析 綜合設(shè)計(jì)性實(shí)驗(yàn)（5頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、《算法設(shè)計(jì)與分析》課程綜合設(shè)計(jì)性實(shí)驗(yàn)要求 、實(shí)驗(yàn)對(duì)象：必修或選修《算法設(shè)計(jì)與分析》課程的同學(xué)。 二、截至?xí)r間：2013-12-08之前，由學(xué)委統(tǒng)一收了并對(duì)文件名命名整理，后打包用郵件來(lái)交。 三、實(shí)驗(yàn)內(nèi)容: 0-1背包問(wèn)題是一例典型的組合優(yōu)化的NP完全問(wèn)題。問(wèn)題可以描述為：給定一組共n個(gè)物品，每種 物品都有自己的重量wi, i=1~n和價(jià)值vi, i=1?n，在限定的總重量（背包的容量C）內(nèi)，如何選擇才能使得 選擇物品的總價(jià)值之和最高。選擇最優(yōu)的物品子集放置于給定背包中，最優(yōu)子集對(duì)應(yīng)n元解向量（x1,...xn）, xie {0或1}，因此命名為0-1背包問(wèn)題。 0-1背包問(wèn)題是許多問(wèn)

2、題的原型，但它又是一個(gè)NP完全問(wèn)題。此實(shí)驗(yàn)主要研究和實(shí)現(xiàn)n（0<=n<=200） 和C（C<=2000, C為整數(shù)）都較大的情形，隨機(jī)產(chǎn)生n個(gè)物品的重量向量wi（1<=wi<=100, wi為整數(shù)）和價(jià)值向 量 vi （1<=vi<=100, vi 為整數(shù)）。 0-1背包問(wèn)題可以用許多方法來(lái)求解，有些算法可以得到問(wèn)題的精確最優(yōu)解，有些僅能獲得一個(gè)近似 最優(yōu)解。本綜合設(shè)計(jì)性實(shí)驗(yàn)要求用3種以上的方法求解0-1背包問(wèn)題，獲得精確最優(yōu)解或近似最優(yōu)解皆可， 并對(duì)所采用的多種算法從運(yùn)行時(shí)間、尋找是否為最優(yōu)解、能夠求解的問(wèn)題規(guī)模等方面進(jìn)行對(duì)比和分析。本 課程講述的所有算法思想都可以用來(lái)求解此問(wèn)題，甚至本課

3、程未涉及的許多算法也非常適合于求解此問(wèn) 題，學(xué)生可以先嘗試先用本課程已介紹的算法來(lái)實(shí)現(xiàn)和分析，學(xué)有余力或興趣驅(qū)動(dòng)下可以尋找一些智能算 法的資料來(lái)試一試。涉及的方法可以有：蠻力求解、遞歸求解、動(dòng)態(tài)規(guī)劃求解、貪心求解、回溯法求解、 廣度優(yōu)先的分支限界法求解，優(yōu)先隊(duì)列的啟發(fā)式分支限界法、遺傳算法、模擬退火算法、蟻群算法、粒子 群算法等。 為方便這種大規(guī)模輸入數(shù)據(jù)的調(diào)試，采用文件輸入，標(biāo)準(zhǔn)輸出（文件輸出當(dāng)然也可）的形式。數(shù)據(jù)輸入的 格式如下：每組測(cè)試數(shù)據(jù)包含n+1行，第1行為C和n，表示背包容量為C且有n個(gè)物品，接下來(lái)n行是這n 個(gè)物品的重量wi和價(jià)值vi。背包容量和物品重量都為整數(shù)。n, C ,

4、wi, vi范圍如上所述。 輸出n+1行。第1行為所選物品的最大價(jià)值之和，接下來(lái)n行為裝入背包的物品所對(duì)應(yīng)的n元最優(yōu)解向量 （x1,...xn）, xie{0或1}，但每行以"i xi"形式輸出。 提供一個(gè)參考的測(cè)試數(shù)據(jù)“0-1背包問(wèn)題測(cè)試數(shù)據(jù)（提供參考）.xls”）給大家，此數(shù)據(jù)僅用參考，你也可自 擬測(cè)試數(shù)據(jù)，對(duì)有些復(fù)雜度較高的算法可能算不到參考數(shù)據(jù)中的最大規(guī)模的數(shù)據(jù)（或算的時(shí)間過(guò)長(zhǎng)），但能算到 多大要測(cè)試一下你的算法。 四、實(shí)驗(yàn)形式: 不超過(guò)3人（小組成員人數(shù)W3人）形成一組，自由組合，若湊不夠人數(shù)就2人或單人也可。一組只交一 份報(bào)告，報(bào)告封面上需將小組所有成員的姓名和學(xué)號(hào)填入，在

5、報(bào)告中開(kāi)始部分說(shuō)明小組成員的分工。先透徹理 解實(shí)驗(yàn)內(nèi)容，然后思考算法及實(shí)現(xiàn)框架，并編程調(diào)試測(cè)試通過(guò)，最后執(zhí)筆完成《綜合設(shè)計(jì)性實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告》。 綜合設(shè)計(jì)性實(shí)驗(yàn)報(bào)告以“電子版”的形式上交，以班級(jí)為單位收集好，由每個(gè)班學(xué)習(xí)委員統(tǒng)一收齊電子版 并將全班電子作業(yè)打包，郵件發(fā)至：lucyzhengchan@。因人數(shù)太多了，最好不要每人單獨(dú)交郵件! 各班學(xué)委收集每個(gè)小組的文件（包含實(shí)驗(yàn)報(bào)告+源程序）時(shí)，注意以小組全部成員的學(xué)號(hào)和姓名來(lái)命名文件名。 如： 文件命名： “201030720509 何 XX201030720514 林 YY201030720526 葉 ZZ 實(shí)驗(yàn)報(bào)告.doc” 目錄命

6、名： “201030720509 何 XX201030720514 林 YY201030720526 葉 ZZ 源程序” 綜合設(shè)計(jì)性實(shí)驗(yàn)報(bào)告須有統(tǒng)一封面，封面設(shè)計(jì)如后頁(yè)所附。將提供給學(xué)生的封面貼于報(bào)告的首頁(yè)。 五、綜合設(shè)計(jì)性實(shí)驗(yàn)評(píng)分標(biāo)準(zhǔn)： 綜合性實(shí)驗(yàn)評(píng)分從以下11個(gè)方面給分，每個(gè)方面根據(jù)完成情況分為4個(gè)等級(jí)，每個(gè)方面在總分中的比重見(jiàn) 下表?？偡指鶕?jù)A-90、B-80、C-70、D-60，再乘以比重，相加之和得到，其余未列情況酌情增減幾分。 項(xiàng)目/分?jǐn)?shù) A B C D 比重％ 能夠?qū)崿F(xiàn)實(shí)驗(yàn)要求的功能 □ □ □ □ 35% 算法描述清晰 □ □ □ □

7、10% 算法有新意 □ □ □ □ 5% 程序運(yùn)行通過(guò) □ □ □ □ 10% 算法思想與程序設(shè)計(jì)參數(shù)等說(shuō)明 □ □ □ □ 5% 遇到的困難部分是否流暢解決 □ □ □ □ 5% 對(duì)每種算法的分析 □ □ □ □ 10% 對(duì)多種算法的對(duì)比 □ □ □ □ 5% 報(bào)告的整體結(jié)構(gòu) □ □ □ □ 5% 報(bào)告有總結(jié)和體會(huì) □ □ □ □ 5% 按期上交報(bào)告的文檔資料及附源程序 □ □ □ □ 5% 六、綜合性設(shè)計(jì)性實(shí)驗(yàn)報(bào)告書(shū)寫(xiě)要求： 1. 實(shí)驗(yàn)框架性題目：0-1背包問(wèn)題的多種算法設(shè)計(jì)

8、與分析 2. 實(shí)驗(yàn)報(bào)告應(yīng)該包含如下幾個(gè)方面內(nèi)容： （1）報(bào)告封面（2）實(shí)驗(yàn)內(nèi)容和要求（3）多種算法詳細(xì)設(shè)計(jì)（4）多種算法調(diào)試和測(cè)試（5）多種算法對(duì)比 （6）附錄多種算法實(shí)現(xiàn)清單 下面對(duì)報(bào)告的這幾方面內(nèi)容具體說(shuō)明一下： 3. 封面：采用給大家提供的封面模板，附于綜合實(shí)驗(yàn)報(bào)告首頁(yè)。首頁(yè)的“教師評(píng)語(yǔ)”和“成績(jī)欄”請(qǐng)勿填寫(xiě) （由教師批閱后填寫(xiě)），其他內(nèi)容學(xué)生填充完整。 4. 實(shí)驗(yàn)內(nèi)容和要求：簡(jiǎn)明扼要說(shuō)明實(shí)驗(yàn)的題目、要求完成的任務(wù)、輸入輸出。 5. 多種算法詳細(xì)設(shè)計(jì)：說(shuō)明用到的算法偽代碼、數(shù)據(jù)類(lèi)型的定義、主程序及其模塊之間的層次（調(diào)用）關(guān)系 等、并對(duì)算法進(jìn)行簡(jiǎn)略分析 6. 多種算法調(diào)試

9、和測(cè)試： 1) 調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的？ 2) 算法的時(shí)空分析和是否有改進(jìn)的設(shè)想？ 3) 測(cè)試用例選擇是否得當(dāng)？舉幾個(gè)自擬的有代表性的測(cè)試實(shí)例。 4) 調(diào)試的經(jīng)驗(yàn)和體會(huì)。 7. 多種算法對(duì)比：你所采用的多種算法從運(yùn)行時(shí)間、尋找是否為最優(yōu)解、能夠求解的問(wèn)題規(guī)模等方面進(jìn) 行列表對(duì)比和分析(列表對(duì)比或列圖對(duì)比都可)。 算法運(yùn)行時(shí)間的統(tǒng)計(jì)，可以在你程序的開(kāi)頭和結(jié)束分別獲取時(shí)間(精確到ms或us級(jí))，然后相減。 1. #include “stdio.h” 2. #include “stdlib.h” 3. #include “time.h” 4. 4. int main(

10、) 5. ( 6. clock_t start, finish; /*精確到 ms(毫秒)級(jí)的時(shí)間*/ 7. double duration; /*測(cè)量一個(gè)事件持續(xù)的時(shí)間*/ 8. start = clock(); 10 11 12. finish = clock(); 13. duration = (double)(finish - start) / CLOCKS_PER_SEC; 14. printf( "%f seconds\n", duration ); /*此 duration 單位為秒*/ 15. ) 1. #include “stdio.h” 2.

11、 #include “stdlib.h” 3. #include 4. 4. int main() 5. ( 6. struct timeval start, finish; /*精確到 us(微秒)級(jí)的時(shí)間*/ 7. long duration; /*測(cè)量一個(gè)事件持續(xù)的時(shí)間*/ 8. gettimeofday(&start, NULL); 10 11 12. gettimeofday(&finish, NULL); 13. duration = (finish.tv_sec - start.tv_sec) * 1000000; /*秒轉(zhuǎn)

12、化成微秒*/ 14. duration += finish.tv_usec - start.tv_usec; /*加上微秒數(shù)*/ 15. printf( "%d us\n", duration); /*此 duration 單位為微秒*/ 16. ) 8, 附錄多種算法實(shí)現(xiàn)清單：帶注釋和功能模塊說(shuō)明的源程序清單(若程序短，可以附報(bào)告中，也可不附。但 源程序都得另交一個(gè)或多個(gè)完整的文件)。 華南農(nóng)業(yè)大學(xué)《算法設(shè)計(jì)與分析》課程綜合性實(shí)驗(yàn) 實(shí)驗(yàn)起止日期：2013?2014學(xué)年第一學(xué)期 系別 班 級(jí) 學(xué) 號(hào) （最多三名） 姓 名 （最多三名）

13、 實(shí)驗(yàn) 題目 0-1背包問(wèn)題的多種算法設(shè)計(jì)與分析 口設(shè)計(jì)性□綜合性 學(xué)生 自我 評(píng)價(jià) 小組 成員 分工 說(shuō)明 教師 評(píng)語(yǔ) （此欄為“教師評(píng)閱的評(píng)語(yǔ)”，請(qǐng)學(xué)生不要填寫(xiě)?。?能夠?qū)崿F(xiàn)實(shí)驗(yàn)要求的功能 ^A全部 口：8大部分 □C部分 口。無(wú) 算法描述清晰 ^A很清晰 口：8好 口C 一般 口。雜亂 算法有新意 ^A很有亮點(diǎn) 口：8有點(diǎn)新意 □C 一般 口。無(wú)新意 程序運(yùn)行通過(guò) ^A有完整測(cè)試□B有通過(guò) 口C未提及 口。無(wú)通過(guò) 算法思想與程序設(shè)計(jì)參數(shù)等說(shuō)明^A完善 ^B簡(jiǎn)單提及 ^C僅功能 口。缺 遇到的困難部分是否流暢解決 ^A完美解決 ^B嘗試但效果不佳^C提及但未解決 口。缺 對(duì)每種算法的分析 ^A分析詳盡 ^B簡(jiǎn)單分析 ^C提及 口。忽視 對(duì)多種算法的對(duì)比 ^A有對(duì)比且完整 ^B簡(jiǎn)單對(duì)比 ^C提及 口。忽視 報(bào)告的整體結(jié)構(gòu) ^A撰寫(xiě)結(jié)構(gòu)合理 ^B某方面過(guò)重或過(guò)輕 ^C過(guò)于簡(jiǎn)單 口。不合理 報(bào)告有總結(jié)和體會(huì) ^A深刻總結(jié) 割一般 ^C提及 口。無(wú) 按期上交文檔報(bào)告及附屬源程序 ^A按期且資料全 ^B未按期 ^C缺源程序文件 口。無(wú) 其余評(píng)語(yǔ)： 成績(jī) （此欄為“教師評(píng)分”，請(qǐng)學(xué)生不要填寫(xiě)?。? 教師簽名: 批改日期： 年 月 日