2014研究生算法分析与设计上机实现题目要求.doc

2014研究生算法分析与设计上机实现题目要求.doc

  1. 1、本文档共2页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2014研究生算法分析与设计上机实现题目要求

PAGE  PAGE 3 第页 共 NUMPAGES 3页 计算机学院 2013级研究生“算法分析与设计”上机实现题 2013学年~2014学年第2学期 2014年4月 总体要求 本次上机实现题目是为了配合“算法分析与设计”课程的讲授而设置的,目的在于培养学生理论联系实际的问题求解能力。上机题共三道。前两题需要采用动态规划算法求解;第三题为回溯法求解问题。分数划分如下:一、二题每题30分,第三题40分。以小组为单位检查,自由组合,每组人数不超过3人。每组提交1份报告。 对于“动态规划”问题,报告中必须对最优值函数和标记函数的含义进行详细说明,列出子问题计算中所使用的有关最优值函数和标记函数的递推关系(一般采用递归式加以描述)和初值。对于“回溯法”问题,要说明解向量、有哪些信誉好的足球投注网站树结构、代价函数(如果存在)。给出所设计算法的时间复杂度。 每组自备2、3个相关问题的实例,报告中以实例中的数据描述算法的执行步骤。 TSP问题 所谓TSP问题是指旅行商要去n个城市推销商品,其中每个城市到达且仅到达一次,并且要求所走的路程最短(该问题又称货郎担问题、邮递员问题、售货员问题等)。TSP问题最容易想到、也肯定能得到最优解的算法是穷举法,即考察所有可能的行走线路,从中选出最佳的一条。但是用穷举法求解TSP问题的时间复杂性为O(n!),属于NP问题。请用数学语言对该TSP问题加以抽象,在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明,并简述算法求解步骤。用一种你熟悉的程序设计语言加以实现。 广义背包问题 广义背包问题的描述如下:给定载重量为M的背包和n种物品,每种物品有一定的重量和价值,现在需要设计算法,在不超过背包载重量的前提下,巧妙选择物品,使得装入背包的物品的总价值最大化。规则是,每种物品均可装入背包多次或不装入(但不能仅装入物品的一部分)。请用数学语言对上述背包问题加以抽象,在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明,并简述算法的求解步骤。用一种你熟悉的程序设计语言加以实现。 ???续邮资问题 假设某个国家发行了n种不同面值的邮票,并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,即在1张信封上可贴出从邮资1开始,增量为1的最大连续邮资区间。例如,当n=5和m=4时,面值为(1,3,11,15,32)的5种邮票可以贴出的邮资的最大连续邮资区间是1-70。试用回溯法设计求解算法,要求对解向量空间给出定义、对所涉及的符号的确切含义加以说明,并简述算法的求解步骤。用一种你熟悉的程序设计语言加以实现。

文档评论(0)

juhui05 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档