算法设计与分析实验二动态规划算法给定n个矩阵

《算法设计与分析》

实验二

专业班级 学 号 姓 名

网络08-1班

08083724 刘航

实验二 动态规划算法

一：最长公共子序列问题 一、实验目的与要求

1、熟悉最长公共子序列问题的算法； 2、初步掌握动态规划算法； 二、实验题

若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 三、实验代码

#include #include using namespace std; int i=0,j=0; int main(){

string s1,s2,r;

cout<<\输入两字符串\ cin>>s1; cin>>s2;

string subSequence

实验02动态规划算法

[实验目的]

1. 掌握动态规划算法的基本方法 2. 掌握动态规划算法中最优子结构的分析 3. 掌握递归求解最优值的方法 4. 掌握最优解的构造.

[预习要求]

1. 认真阅读算法设计教材,了解动态规划原理;

2. 设计用动态规划算法求解矩阵连乘、最长公共子序列以及电路布线的java程序.

[实验题]

1. 给定n个矩阵{A1, A2, …,An}，其中，Ai与Ai+1是可乘的，计算这n个矩阵的连乘积。

从中找出一种乘次数最少的计算次序。

2. 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 3. 在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))

将上端接线柱与下端接线柱相连，确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。

[实验步骤]

1. 设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2. 应用设计的算法和程序求解问题; 3. 将程序整理成功能模块存盘备用.

[实验报告要求]

1. 阐述实验目的和实验内容; 2. 阐述求解问

动态规划算法实验报告(算法设计与分析)

实验02动态规划算法

[实验目的]

1. 掌握动态规划算法的基本方法

2. 掌握动态规划算法中最优子结构的分析

3. 掌握递归求解最优值的方法

4. 掌握最优解的构造.

[预习要求]

1. 认真阅读算法设计教材,了解动态规划原理;

2. 设计用动态规划算法求解矩阵连乘、最长公共子序列以及电路布线的java程序.

[实验题]

1. 给定n个矩阵{A1, A2, …,An}，其中，Ai与Ai+1是可乘的，计算这n个矩阵的连乘积。从中找出一种乘次数最少的计算次序。

2. 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

3. 在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱与下端接线柱相连，确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。

[算法思路]

将步骤化为多步,自底向上,先求出矩阵链长为1的最优计算次序，链长为2的最优次序，...

最优解结构：

设A[1:n]=Ai...Aj最优计算次序在Ak和A(k+1)间断开，则总计算量=A[1:k]的计算量+A

实验标题

实验目的

1、矩阵连乘 2、最长公共子序列 3、最大子段和 4、凸多边形最优三角剖分 5、流水作业调度 6、0-1背包问题 7、最优二叉搜索树

掌握动态规划法的基本思想和算法设计的基本步骤。 实验内容与源码

1、矩阵连乘

#include #include using namespace std;

const int size=4;

//ra,ca和rb,cb分别表示矩阵A和B的行数和列数

void matriMultiply(int a[][4],int b[][4],int c[][4],int ra ,int ca,int rb ,int cb ) {

if(ca!=rb) cerr<<\矩阵不可乘\ for(int i=0;i

int sum=a[i][0]*b[0][j]; for(int k=1;k

void MatrixChain(int *p,int n,int m[][4],int s[][4]) {

for(int i=1;i<=n;i++) m[i][i]=0;//对角线 for(int r=2;r<=n;r++)//外维 for(int i=1;i<=n-r+1;i++)//上三角 {

int j=i+r-1;

m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]

题目：贪心算法、分治算法、动态规划算法间的比较

贪心算法：贪心算法采用的是逐步构造最优解的方法。在每个阶段，都在一定的标准下做出一个看上去最优的决策。决策一旦做出，就不可能再更改。做出这个局部最优决策所依照的标准称为贪心准则。 分治算法：分治法的思想是将一个难以直接解决大的问题分解成容易求解的子问题，以便各个击破、分而治之。

动态规划：将待求解的问题分解为若干个子问题，按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。 二、算法间的关联与不同 1、分治算法与动态规划

分治法所能解决的问题一般具有以下几个特征： ① 该问题的规模缩小到一定程度就可以容易地解决。

② 该问题可以分为若干个较小规模的相似的问题，即该问题具有最优子结构性质。

③ 利用该问题分解出的子问题的解可以合并为该问题的解。 ④ 该问题所分解出的各个子问题是相互独立的且子问题即之间不包含公共的子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是分治法

计算机研究与发展

./01234/5*/60891:9;931<=32>?9@94/692877

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

／／,!""#$%%%&$’()*#$$&$+++-（）：A’’’)A!’))，’%%B

中国邮递员问题的动态规划算法研究

费蓉

崔杜武

西安+）$%%AE

（西安理工大学计算机科学与工程学院（32259G"=/863G4H</6）F

!"#"$%&’()*’+)"#",(#-.$),%(/0".1"&+#+(),%(&"##20(%+-’.3

I9G:/22>*0G?0K0J3

（!）"##$$""’)*$+,-.$/-$0/12/./$$+./3.’0/)/.4$+5.**$-7/"#"3.’0/+$%%AE%&!(%%，6"&%6，

，2/#-%$&-*=G29;97/;869271/L496K

计算机研究与发展

./01234/5*/60891:9;931<=32>?9@94/692877

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

／／,!""#$%%%&$’()*#$$&$+++-（）：A’’’)A!’))，’%%B

中国邮递员问题的动态规划算法研究

费蓉

崔杜武

西安+）$%%AE

（西安理工大学计算机科学与工程学院（32259G"=/863G4H</6）F

!"#"$%&’()*’+)"#",(#-.$),%(/0".1"&+#+(),%(&"##20(%+-’.3

I9G:/22>*0G?0K0J3

（!）"##$$""’)*$+,-.$/-$0/12/./$$+./3.’0/)/.4$+5.**$-7/"#"3.’0/+$%%AE%&!(%%，6"&%6，

，2/#-%$&-*=G29;97/;869271/L496K

动态规划算法在水电经济运行中的应用

摘 要：在竞价上网中，针对拥有多台机组的水电站在全厂总负荷变化的情况下，在各机组间分配负荷时存在的问题，采用改进的动态规划方法进行机组负荷的最优分配，降低了计算的复杂性，分配后制定的发电计划在满足负荷需求的条件下，确保了总成本的最低，可以明显提高水电站运行的经济性。

关键词：负荷最优分配；动态规划；发电机出力；

当电网按经济调度原则，给一个特定电厂的负荷确定之后，负荷在各并列运行的发电机之间如何取得一个经济合理的分配，是一个能有效降低电厂成本、提高经济效益的重要途径。在多台机组间的负荷分配上，通常是让效率高的机组多带负荷，或是在各机组间平均分配负荷，这在大多数情况下并不是科学的、经济的，特别是当全厂总负荷下降较多时，在各台机组间的负荷分配就更无依据可言。因此，在电厂多台机组间的负荷调度中迫切需要一种调度依据，既能在各种运行工况下科学地、简便地提供机组间负荷分配的结果，又能保证负荷分配的结果是经济的、可信的，以弥补电厂因参与调峰而造成的经济损失。如何确定全厂在某一时刻参与运行的机组组合，使得在满足机组设备安全、运行安全和供电需求的情况下发电厂在整个调度周期内总的成本(包括运行成本和启动成本)达到最小，属于电力系统经

实验二：分治法实验

一、实验目的

（1）掌握设计有效算法的分治策略。

（2）通过快速排序学习分治策略设计技巧

二、实验要求

（1）熟练掌握分治法的基本思想及其应用实现。

（2）理解所给出的算法，并对其加以改进。

三、分治法的介绍

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

如果原问题可分割成k个子问题，1

分治法的适用条件：

（1）该问题的规模缩小到一定的程度就可以容易地解决；

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

（3）利用该问题分解出的子问题的解可以合并为该问题的解；

（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于

《算法设计与分析》实验报告

学号： 姓名：

实验一 分治法求解**问题

一、实验目的

1.掌握分治法的设计思想并能熟练应用；

2.理解分治与递归的关系。

二、实验题目

在有序序列中(r1,r2,…,rn)中,存在序号i（1≤i≤n）,使得ri=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n).

三、实验程序

//以(0,2,3,3,5,7,8,10,12,13)为例

#include<iostream>

using namespace std;

void PrintData(int data[],int length)

{

}

int Bisearch(int data[],int begin ,int last)

{

if ( mid < data[mid] ) int mid=(begin + last) /2; if (mid+1 == data[mid]) { } return mid; cout<<"有序序列是："; for (int i=0;i