算法設(shè)計與分析 綜合設(shè)計性實驗

算法設(shè)計與分析課程綜合設(shè)計性實驗要求、實驗對象：必修或選修算法設(shè)計與分析課程的同學(xué)。二、截至?xí)r間：2013-12-08之前，由學(xué)委統(tǒng)一收了并對文件名命名整理，后打包用郵件來交。三、實驗內(nèi)容:0-1背包問題是一例典型的組合優(yōu)化的NP完全問題。問題可以描述為：給定一組共n個物品，每種 物品都有自己的重量wi, i=1n和價值vi, i=1n，在限定的總重量（背包的容量C）內(nèi)，如何選擇才能使得 選擇物品的總價值之和最高。選擇最優(yōu)的物品子集放置于給定背包中，最優(yōu)子集對應(yīng)n元解向量（x1,.xn）, xie 0或1，因此命名為0-1背包問題。0-1背包問題是許多問題的原型，但它又是一個NP完全問題。此實驗主要研究和實現(xiàn)n（0<=n<=200） 和C（C<=2000, C為整數(shù)）都較大的情形，隨機產(chǎn)生n個物品的重量向量wi（1<=wi<=100, wi為整數(shù)）和價值向 量 vi （1<=vi<=100, vi 為整數(shù)）。0-1背包問題可以用許多方法來求解，有些算法可以得到問題的精確最優(yōu)解，有些僅能獲得一個近似 最優(yōu)解。本綜合設(shè)計性實驗要求用3種以上的方法求解0-1背包問題，獲得精確最優(yōu)解或近似最優(yōu)解皆可， 并對所采用的多種算法從運行時間、尋找是否為最優(yōu)解、能夠求解的問題規(guī)模等方面進行對比和分析。本 課程講述的所有算法思想都可以用來求解此問題，甚至本課程未涉及的許多算法也非常適合于求解此問 題，學(xué)生可以先嘗試先用本課程已介紹的算法來實現(xiàn)和分析，學(xué)有余力或興趣驅(qū)動下可以尋找一些智能算 法的資料來試一試。涉及的方法可以有：蠻力求解、遞歸求解、動態(tài)規(guī)劃求解、貪心求解、回溯法求解、 廣度優(yōu)先的分支限界法求解，優(yōu)先隊列的啟發(fā)式分支限界法、遺傳算法、模擬退火算法、蟻群算法、粒子 群算法等。為方便這種大規(guī)模輸入數(shù)據(jù)的調(diào)試，采用文件輸入，標準輸出（文件輸出當然也可）的形式。數(shù)據(jù)輸入的 格式如下：每組測試數(shù)據(jù)包含n+1行，第1行為C和n，表示背包容量為C且有n個物品，接下來n行是這n 個物品的重量wi和價值vi。背包容量和物品重量都為整數(shù)。n, C , wi, vi范圍如上所述。輸出n+1行。第1行為所選物品的最大價值之和，接下來n行為裝入背包的物品所對應(yīng)的n元最優(yōu)解向量 （x1,.xn）, xie0或1，但每行以"i xi"形式輸出。提供一個參考的測試數(shù)據(jù)“0-1背包問題測試數(shù)據(jù)（提供參考）.xls”）給大家，此數(shù)據(jù)僅用參考，你也可自 擬測試數(shù)據(jù)，對有些復(fù)雜度較高的算法可能算不到參考數(shù)據(jù)中的最大規(guī)模的數(shù)據(jù)（或算的時間過長），但能算到 多大要測試一下你的算法。四、實驗形式:不超過3人（小組成員人數(shù)W3人）形成一組，自由組合，若湊不夠人數(shù)就2人或單人也可。一組只交一 份報告，報告封面上需將小組所有成員的姓名和學(xué)號填入，在報告中開始部分說明小組成員的分工。先透徹理 解實驗內(nèi)容，然后思考算法及實現(xiàn)框架，并編程調(diào)試測試通過，最后執(zhí)筆完成綜合設(shè)計性實驗的實驗報告。綜合設(shè)計性實驗報告以“電子版”的形式上交，以班級為單位收集好，由每個班學(xué)習(xí)委員統(tǒng)一收齊電子版 并將全班電子作業(yè)打包，郵件發(fā)至：lucyzhengchan。因人數(shù)太多了，最好不要每人單獨交郵件!各班學(xué)委收集每個小組的文件（包含實驗報告+源程序）時，注意以小組全部成員的學(xué)號和姓名來命名文件名。如：文件命名： “201030720509 何 XX201030720514 林 YY201030720526 葉 ZZ 實驗報告.doc”目錄命名： “201030720509 何 XX201030720514 林 YY201030720526 葉 ZZ 源程序”綜合設(shè)計性實驗報告須有統(tǒng)一封面，封面設(shè)計如后頁所附。將提供給學(xué)生的封面貼于報告的首頁。五、綜合設(shè)計性實驗評分標準：綜合性實驗評分從以下11個方面給分，每個方面根據(jù)完成情況分為4個等級，每個方面在總分中的比重見 下表?？偡指鶕?jù)A-90、B-80、C-70、D-60，再乘以比重，相加之和得到，其余未列情況酌情增減幾分。項目/分數(shù)ABCD比重能夠?qū)崿F(xiàn)實驗要求的功能35%算法描述清晰10%算法有新意5%程序運行通過10%算法思想與程序設(shè)計參數(shù)等說明5%遇到的困難部分是否流暢解決5%對每種算法的分析10%對多種算法的對比5%報告的整體結(jié)構(gòu)5%報告有總結(jié)和體會5%按期上交報告的文檔資料及附源程序5%六、綜合性設(shè)計性實驗報告書寫要求：1. 實驗框架性題目：0-1背包問題的多種算法設(shè)計與分析2. 實驗報告應(yīng)該包含如下幾個方面內(nèi)容：（1）報告封面（2）實驗內(nèi)容和要求（3）多種算法詳細設(shè)計（4）多種算法調(diào)試和測試（5）多種算法對比（6）附錄多種算法實現(xiàn)清單下面對報告的這幾方面內(nèi)容具體說明一下：3. 封面：采用給大家提供的封面模板，附于綜合實驗報告首頁。首頁的“教師評語”和“成績欄”請勿填寫（由教師批閱后填寫），其他內(nèi)容學(xué)生填充完整。4. 實驗內(nèi)容和要求：簡明扼要說明實驗的題目、要求完成的任務(wù)、輸入輸出。5. 多種算法詳細設(shè)計：說明用到的算法偽代碼、數(shù)據(jù)類型的定義、主程序及其模塊之間的層次（調(diào)用）關(guān)系 等、并對算法進行簡略分析6. 多種算法調(diào)試和測試：1) 調(diào)試過程中遇到的問題是如何解決的？2) 算法的時空分析和是否有改進的設(shè)想？3) 測試用例選擇是否得當？舉幾個自擬的有代表性的測試實例。4) 調(diào)試的經(jīng)驗和體會。7. 多種算法對比：你所采用的多種算法從運行時間、尋找是否為最優(yōu)解、能夠求解的問題規(guī)模等方面進 行列表對比和分析(列表對比或列圖對比都可)。算法運行時間的統(tǒng)計，可以在你程序的開頭和結(jié)束分別獲取時間(精確到ms或us級)，然后相減。1. #include “stdio.h”2. #include “stdlib.h”3. #include “time.h”4.4. int main()5. (6. clock_t start, finish; /*精確到 ms(毫秒)級的時間*/7. double duration;/*測量一個事件持續(xù)的時間*/8. start = clock();10 11 12. finish = clock();13. duration = (double)(finish- start)/ CLOCKS_PER_SEC;14. printf( "%f secondsn", duration ); /*此 duration 單位為秒*/15. )1. #include “stdio.h”2. #include “stdlib.h”3. #include <sys/time.h>4.4. int main()5. (6. struct timeval start, finish; /*精確到 us(微秒)級的時間*/7. long duration; /*測量一個事件持續(xù)的時間*/8. gettimeofday(&start, NULL);10 11 12. gettimeofday(&finish, NULL);13. duration = (finish.tv_sec - start.tv_sec) * 1000000; /*秒轉(zhuǎn)化成微秒*/14. duration += finish.tv_usec - start.tv_usec;/*加上微秒數(shù)*/15. printf( "%d usn", duration); /*此 duration 單位為微秒*/16. )8, 附錄多種算法實現(xiàn)清單：帶注釋和功能模塊說明的源程序清單(若程序短，可以附報告中，也可不附。但 源程序都得另交一個或多個完整的文件)。華南農(nóng)業(yè)大學(xué)算法設(shè)計與分析課程綜合性實驗實驗起止日期：20132014學(xué)年第一學(xué)期系別班 級學(xué)號（最多三名）姓 名（最多三名）實驗題目0-1背包問題的多種算法設(shè)計與分析 口設(shè)計性綜合性學(xué)生 自我 評價小組 成員 分工 說明教師評語（此欄為“教師評閱的評語”，請學(xué)生不要填寫?。?能夠?qū)崿F(xiàn)實驗要求的功能A全部口：8大部分C部分口。無算法描述清晰A很清晰口：8好口C 一般口。雜亂算法有新意A很有亮點口：8有點新意C 一般口。無新意程序運行通過A有完整測試B有通過口C未提及 口。無通過算法思想與程序設(shè)計參數(shù)等說明A完善B簡單提及C僅功能口。缺遇到的困難部分是否流暢解決A完美解決 B嘗試但效果不佳C提及但未解決 口。缺對每種算法的分析A分析詳盡B簡單分析C提及口。忽視對多種算法的對比A有對比且完整 B簡單對比C提及口。忽視報告的整體結(jié)構(gòu)A撰寫結(jié)構(gòu)合理 B某方面過重或過輕 C過于簡單 口。不合理報告有總結(jié)和體會A深刻總結(jié)割一般C提及口。無按期上交文檔報告及附屬源程序 A按期且資料全 B未按期 C缺源程序文件 口。無其余評語：成績（此欄為“教師評分”，請學(xué)生不要填寫?。┙處熀灻?批改日期：年 月 日