文档介绍：算法设计与分析
实验报告
|
|
姓名:徐一洲
专业班级:信安1101
学号:201109040128
指导教师:刘军
实验一:矩阵连乘问题
实验内容
给定n个矩阵{A1,A2,….An},其中Ai与Ai+1是可乘的,我们要计算这n个矩阵的连乘积。由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多种不同的计算次序。这种计算次序可以用加括号的方式来确定。连乘积的计算次序不同,计算连乘积的计算量也不同。如何计算才能确定一种最好的计算次序,使得最后的计算量最小?即矩阵连乘积的最优计算次序问题。
二、算法设计
方法1 穷举搜索法
找出所有可能的计算次序。然后计算出相应的乘法次数。
这是不现实的!计算量太大,算法复杂性为指数级别。
方法2 动态规划法求解
分析最优解的结构(问题是否具有最优子结构)
A[i:j]表示矩阵AiAi+1….Aj
原问题变为求A[1:n]的一个最优次序。矩阵Ai的维数为pi-1Pi
2、建立递归关系
设计算A[i][j]所需的最少乘法次数为m[i][j],原问题最优解为m[1][n]。下面对m[i][j]分析:
当i==j时A[i][j]为一个单个矩阵,无需计算
当i<j时,假设最优次序是在Ak和Ak+1之间断开
则m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj
3、计算最优值
上述公式是一个递归公式,显然我们可以设计一个递归算法来计算m[1][n],然而我们也会注意到问题的重复计算。
我们可以由低向上来计算,在计算过程中,保存已经解决的子问题答案,每个子问题只计算一次,再后面计算时,只需要简单查一下即可。下面给出具体算法:
输入参数{p0,p1,p2,….pn}存储在数组p中,S数组存储最优断开位置k的值。
4、构造最优解
上述算法只是给出了一个最优值,,,把最优断开位置k保存在数组s[][]中,我们可以利用它来构造最优解。我们可以利用类似于二叉树的后序遍历算法来实现。
实验结果
实验心得
此次实验在同学的帮助下较顺利地完成了。通过这次实验,对动态规划法有了更深的体会。动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。而我设计的程序也存在一些问题,当第二次输入数据个数与第一次输入的n不符时,就直接默认为A0A1…An了。
实验二:n皇后问题
实验内容
要求在一个n*n的棋盘上放置n个皇后,使得它们彼此不受攻击。一个皇后可以攻击与之处在同一行或同一列或同一斜线上的任何其他棋子。即N后问题等价于在n*n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。
算法思想
问题的解可表示为x[1:n],x[i]表示皇后i放在棋盘的第i行的第x[i]列(隐含约束:任何两个皇后不在同一行)。
a)x[i]≠x[j] ,i≠j :不允许将任何两个皇后放在同一列上;
b)|j-i|≠|x[j]-x[i]| :不允许两个皇后位于同一条斜线上。
问题的解空间的形式为:
要找出”四皇后”问题的解,最可靠的方法就是把各种情况全