算法设计与分析实验报告(华北电力大学科技学院)

《算法设计与分析实验报告(华北电力大学科技学院)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、科技学院课程设计(综合实验)报告(2011--2012年度第1学期)名称：算法设计与分析题目：动态规划法和回溯法的应用院系：信息系班级：软件09K2学号：091909020227学生姓名：闫雪峰指导教师：刘军设计周数：1成绩：日期：2011年11月4日一、实验内容1．要求能够利用动态规划法解决矩阵连乘问题或0-1背包问题；2．要求能够利用回溯法解决N皇后问题。二、实验流程1．0-1背包问题1．1动态规划法解决问题的基本思想可利用动态规划法解决的问题要具有2个性质：最优子结构性质和子问题重叠性质。动态规划的

2、基本思想是将待求的问题分成若干个子问题，这些子问题往往具有重叠的性质，因此，动态规划法采用自底而上的方向不断解决子问题，同时用一个表记录已解决问题的相关重叠数据，以便调用，从而节省计算时间。动态规划法适于解最优问题，通常可按以下4个步骤设计：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以自底而上的方式计算出最优值并保存；（4）根据计算最优值时得到的信息，构造最优解。1.2利用动态规划法解决0-1背包问题1.3.1问题描述给定n种物品和一个背包。物品i的重量是，其价值为，背包的容

3、量是c。如何选择物品，使得背包中的物品价值最大？在选择物品时，对于任何一种物品i，只有两种选择：选和不选。不可选部分，也不可一个物品选多次。对该问题的一个形式化描述为：给定c>0，>0，>0，1≤i≤n，要求找出一个0-1向量,使得最大，同时满足。目标函数：约束函数：因此，0-1背包问题实际上是一个特殊的整数规划问题。1.3.2分析最优解的结构0-1背包问题具有最优子结构性质。设是所给0-1背包问题的一个最优解，则是的一个最优解。因若不然，设是上述子问题的一个最优解，而不是它的最优解。那么可以推出：是原问

4、题的最优解，与假设矛盾。显然，0-1背包问题也具有子问题重叠的性质。1.3.3建立递归关系设m[i][j]是容量为j，可选物品为I,i+1,…,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质可以建立递归关系如下：1.3.4计算最优值开始处理第n件物品：for(j=1;j<=c;j++){if(j<)m[n][j]=0;elsem[n][j]=}自底而上处理每一件物品：for(i=n-1;i>=1;i--){if(j<)m[i][j]=m[i+1][j];elsem[i][j]=max{m[i

5、+1][j],m[i+1][j-]+};}结束1.3.5实例运行结果：实例1：实例2：实例3：实例4：实例5：1.4利用回溯法解决N皇后问题1.4.1回溯法解决问题的基本思想回溯法有“万能解题法”之称。用回溯法可以系统地搜索一个问题的所有解或任意解，因回溯法是一个既带有系统性又带有跳跃性的搜索算法。回溯法在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索之空间的任一节点时，将此节点临时定义为“根节点”，然后利用剪枝函数判断该结点是否包含问题的解。如果肯定不包含，则回溯至祖先结点继续搜索

6、；如果包含，则继续深度搜索，直至搜索完根节点的所有子树才结束。回溯法适于解决组合数较大的问题。1.4.2N皇后问题描述在格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行、同一列及同一斜线上的皇后。1.4.3算法设计用n元组x[i](i=1,2,…,n)表示n后问题的解。其中，x[i]表示皇后i放在棋盘的第x[i]列。设2个皇后的位置分别为:(i,x[i])、(k,x[k])，则约束函数为：用回溯法n皇后问题时，用完全n叉树表示解空间。剪枝函数剪去不满足行、列和斜线约束的

7、子树。1.4.4算法流程开始遍历row1确定Q1的位置遍历下一行选取的位置满足剪枝函数Ni>nNY结束打印输出这组解Y遍历完所有子树1.4.5实际运行结果实例1：5个皇后的所有方案实例2：6个皇后的所有方案实例3：7个皇后的方案截图实例4：8个皇后的方案截图实例5：9个皇后的方案截图三、课程设计（综合实验）总结或结论通过本次课程实验，我加深了对动态规划法和回溯法的理解，并且熟悉了利用动态规划法和回溯法解决问题的基本流程。换言之，我掌握了两种解决问题的有效方法。理论指导实践，实践反过来使我们加深对理论的理解

8、。因此，在今后的学习中，多多动手上机实践，必定会使我们受益匪浅。最后，感谢刘军老师的谆谆教导。四、参考文献[1]王晓东，《计算机算法设计与分析》（第3版），北京：电子工业出版社，2007.5。附录