文档库

最新最全的文档下载
当前位置:文档库 > 算法设计与分析 综合设计性实验(实验报告的要求)

算法设计与分析 综合设计性实验(实验报告的要求)

《算法设计与分析》课程综合设计性实验要求

一、实验对象:必修或选修《算法设计与分析》课程的同学。

二、截至时间:2013-12-08之前,由学委统一收了并对文件名命名整理,后打包用邮件来交。

三、实验内容:

0-1背包问题是一例典型的组合优化的NP完全问题。问题可以描述为:给定一组共n个物品,每种物品都有自己的重量wi, i=1~n和价值vi, i=1~n,在限定的总重量(背包的容量C)内,如何选择才能使得选择物品的总价值之和最高。选择最优的物品子集放置于给定背包中,最优子集对应n元解向量(x1,…xn), xi∈{0或1},因此命名为0-1背包问题。

0-1背包问题是许多问题的原型,但它又是一个NP完全问题。此实验主要研究和实现n(0<=n<=200)和C(C<=2000, C为整数)都较大的情形,随机产生n个物品的重量向量wi(1<=wi<=100, wi为整数)和价值向量vi (1<=vi<=100, vi为整数)。

0-1背包问题可以用许多方法来求解,有些算法可以得到问题的精确最优解,有些仅能获得一个近似最优解。本综合设计性实验要求用3种以上的方法求解0-1背包问题,获得精确最优解或近似最优解皆可,并对所采用的多种算法从运行时间、寻找是否为最优解、能够求解的问题规模等方面进行对比和分析。本课程讲述的所有算法思想都可以用来求解此问题,甚至本课程未涉及的许多算法也非常适合于求解此问题,学生可以先尝试先用本课程已介绍的算法来实现和分析,学有余力或兴趣驱动下可以寻找一些智能算法的资料来试一试。涉及的方法可以有:蛮力求解、递归求解、动态规划求解、贪心求解、回溯法求解、广度优先的分支限界法求解,优先队列的启发式分支限界法、遗传算法、模拟退火算法、蚁群算法、粒子群算法等。

为方便这种大规模输入数据的调试,采用文件输入,标准输出(文件输出当然也可)的形式。数据输入的格式如下:每组测试数据包含n+1行,第1行为C和n,表示背包容量为C且有n个物品,接下来n行是这n 个物品的重量wi和价值vi。背包容量和物品重量都为整数。n, C , wi, vi范围如上所述。

输出n+1行。第1行为所选物品的最大价值之和,接下来n行为装入背包的物品所对应的n元最优解向量(x1,…xn), xi∈{0或1},但每行以"i xi"形式输出。

提供一个参考的测试数据(“0-1背包问题测试数据(提供参考).xls”)给大家,此数据仅用参考,你也可自拟测试数据,对有些复杂度较高的算法可能算不到参考数据中的最大规模的数据(或算的时间过长),但能算到多大要测试一下你的算法。

四、实验形式:

不超过3人(小组成员人数≤3人)形成一组,自由组合,若凑不够人数就2人或单人也可。一组只交一份报告,报告封面上需将小组所有成员的姓名和学号填入,在报告中开始部分说明小组成员的分工。先透彻理解实验内容,然后思考算法及实现框架,并编程调试测试通过,最后执笔完成《综合设计性实验的实验报告》。

综合设计性实验报告以“电子版”的形式上交,以班级为单位收集好,由每个班学习委员统一收齐电子版

并将全班电子作业打包,邮件发至:lucy_zhengchan@http://www.wendangku.net/doc/761c0a447fd5360cba1adbf6.html。因人数太多了,最好不要每人单独交邮件!各班学委收集每个小组的文件(包含实验报告+源程序)时,注意以小组全部成员的学号和姓名来命名文件名。如:

文件命名:“201030720509何XX201030720514林YY201030720526叶ZZ 实验报告.doc”

目录命名:“201030720509何XX201030720514林YY201030720526叶ZZ 源程序”

综合设计性实验报告须有统一封面,封面设计如后页所附。将提供给学生的封面贴于报告的首页。

五、综合设计性实验评分标准:

综合性实验评分从以下11个方面给分,每个方面根据完成情况分为4个等级,每个方面在总分中的比重见

算法设计与分析 综合设计性实验(实验报告的要求)

六、综合性设计性实验报告书写要求:

1.实验框架性题目:0-1背包问题的多种算法设计与分析

2.实验报告应该包含如下几个方面内容:

(1)报告封面(2)实验内容和要求(3)多种算法详细设计(4)多种算法调试和测试(5)多种算法对比(6)附录多种算法实现清单

下面对报告的这几方面内容具体说明一下:

3.封面:采用给大家提供的封面模板,附于综合实验报告首页。首页的“教师评语”和“成绩栏”请勿填写

(由教师批阅后填写),其他内容学生填充完整。

4.实验内容和要求:简明扼要说明实验的题目、要求完成的任务、输入输出。

5.多种算法详细设计:说明用到的算法伪代码、数据类型的定义、主程序及其模块之间的层次(调用)关系

等、并对算法进行简略分析

6.多种算法调试和测试:

1)调试过程中遇到的问题是如何解决的?

2)算法的时空分析和是否有改进的设想?

3)测试用例选择是否得当?举几个自拟的有代表性的测试实例。

4)调试的经验和体会。

7.多种算法对比:你所采用的多种算法从运行时间、寻找是否为最优解、能够求解的问题规模等方面进

行列表对比和分析(列表对比或列图对比都可)。

算法运行时间的统计,可以在你程序的开头和结束分别获取时间(精确到ms或us级),然后相减。

1.#include “stdio.h”

2.#include “stdlib.h”

3.#incl ude “time.h”

4.

5.int main()

6.{

7.clock_t start, finish; /*精确到ms(毫秒)级的时间*/

8.double duration; /*测量一个事件持续的时间*/

9.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.#include “stdlib.h”

3.#include

4.

5.int main()

6.{

7.struct timeval start, finish; /*精确到us(微秒)级的时间*/

8.long duration; /* 测量一个事件持续的时间*/

9.gettimeofday(&start, NULL);

10.……

11.……

12.gettimeofday(&finish, NULL);

13.duration = (http://www.wendangku.net/doc/761c0a447fd5360cba1adbf6.html_sec - http://www.wendangku.net/doc/761c0a447fd5360cba1adbf6.html_sec) * 1000000; /*秒转化成微秒*/

14.duration += http://www.wendangku.net/doc/761c0a447fd5360cba1adbf6.html_usec - http://www.wendangku.net/doc/761c0a447fd5360cba1adbf6.html_usec; /*加上微秒数*/

15.printf( "%d us\n", duration); /*此duration单位为微秒*/

16.}

8.附录多种算法实现清单:带注释和功能模块说明的源程序清单(若程序短,可以附报告中,也可不附。但

源程序都得另交一个或多个完整的文件)。

华南农业大学《算法设计与分析》课程综合性实验

算法设计与分析 综合设计性实验(实验报告的要求)

教师签名:

批改日期:年月日