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

《2014研究生算法分析与设计上机实现题目要求》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机学院2013级研究生“算法分析与设计”上机实现题2013学年~2014学年第2学期2014年4月总体要求本次上机实现题目是为了配合“算法分析与设计”课程的讲授而设置的，目的在于培养学生理论联系实际的问题求解能力。上机题共三道。前两题需要采用动态规划算法求解；第三题为回溯法求解问题。分数划分如下：一、二题每题30分，第三题40分。以小组为单位检查，自由组合，每组人数不超过3人。每组提交1份报告。对于“动态规划”问题，报告中必须对最优值函数和标记函数的含义进行详细说明，列出子问题计算中所使用的有关最优值函数和标记函数的递推关系（一般采用递归式加以描述）和初值。对于“回溯法”问题，要说明解

2、向量、搜索树结构、代价函数（如果存在）。给出所设计算法的时间复杂度。每组自备2、3个相关问题的实例，报告中以实例中的数据描述算法的执行步骤。一、TSP问题所谓TSP问题是指旅行商要去n个城市推销商品，其中每个城市到达且仅到达一次，并且要求所走的路程最短（该问题又称货郎担问题、邮递员问题、售货员问题等）。TSP问题最容易想到、也肯定能得到最优解的算法是穷举法，即考察所有可能的行走线路，从中选出最佳的一条。但是用穷举法求解TSP问题的时间复杂性为O(n!)，属于NP问题。请用数学语言对该TSP2第页共2页问题加以抽象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详

3、细说明，并简述算法求解步骤。用一种你熟悉的程序设计语言加以实现。一、广义背包问题广义背包问题的描述如下：给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）。请用数学语言对上述背包问题加以抽象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明，并简述算法的求解步骤。用一种你熟悉的程序设计语言加以实现。二、连续邮资问题假设某个国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮

4、票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，即在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当n=5和m=4时，面值为（1,3,11,15,32)的5种邮票可以贴出的邮资的最大连续邮资区间是1－70。试用回溯法设计求解算法，要求对解向量空间给出定义、对所涉及的符号的确切含义加以说明，并简述算法的求解步骤。用一种你熟悉的程序设计语言加以实现。2第页共2页