算法设计与分析实验报告.doc

华北电力大学
实验报告
|
|
实验名称计算机算法设计与分析实验
课程名称计算机算法设计与分析

专业班级: 学生姓名:
学号: 成绩:
指导教师: 实验日期:
实验一:矩阵连乘问题
实验内容
给定n个矩阵{A1,A2,….An},其中Ai与Ai+1是可乘的,我们要计算这n个矩阵的连乘积。由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多种不同的计算次序。这种计算次序可以用加括号的方式来确定。矩阵计算次序不同,对计算量有很大影响,如何计算才能确定一种最好的计算次序,使得最后的计算量最小?即矩阵连乘积的最优计算次序问题。
本次实验就是要通过动态规划法来求出最优值并求出最优解。
算法思想
动态规划法求解
分析最优解的结构
A[i:j]表示矩阵Ai ,Ai+1,…,Aj,则原问题变为求A[1:n]的一个最优次序。矩阵Ai的维数为Pi-1Pi 。设这个计算次序在矩阵Ak和Ak+1之间断开(1<=k<n),依次次序,先计算A[1:k]和A[k+1:n],然后将计算结果相乘得到A[1:n]。依此计算次序,总计算量为A[1:k]的计算量加上A[k+1:n]的计算量,再加上A[1:k]和A[k+1:n]相乘的计算量。
2、建立递归关系
m[i][j]为A[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
计算最优值
输入参数{P0,P1,P2,…Pn}存储在数组P中,S数组存储最优断开位置k的值。
构造最优解
在构造最优值的同时,把最优断开位置k保存在数组s中,可以利用它来构造最优解,利用类似于二叉树的后序遍历算法来实现。
实验结果


实验心得
此次实验较顺利地完成了,通过这次实验,对动态规划法有了更深的体会。动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。
实验二: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)|