动态规划实验

1. 实验预习报告

一、实验内容

学习和掌握动态规划算法的基本思想，能够使用动态规划算法解决相应的问题。分析动态规划算法在不同的情况下的时间复杂度。

二、基本原理

动态规划是一个每个决策都依赖于当前状态并导致状态转移的过程。在变化状态下生成决策序列，因此该多阶段优化决策求解过程称为动态规划（DP）。动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

三、实验的算法思想

与分治法相似，其基本思想是将要解决的问题分解为几个子问题（阶段），并按顺序解决子阶段。前一个子问题的解决为后一个子问题的解决提供了有用的信息。在求解任何子问题时，列出了各种可能的局部解，并通过决策保留最优的局部解，而丢弃其他的局部解。

依次解决每个子问题，最后一个子问题是对原问题的解。由于动态规划解决的大多数问题都有重叠子问题，为了减少双重计算，每个子问题只解一次，将不同阶段的不同状态存储在二维数组中。分治法的最大的区别在于，它适合用动态规划方法解决问题，和分解后获得的子问题往往不是相互独立的（也就是说，下一个子阶段的解决方案是建立的基础上进一步解决之前的子阶段的解决方案）。

四、实验准备

主要内容都是与动态规划思想相关，动态规划解题步骤：问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成，然后找出01背包问题的最优解以及解组成，然后编写代码实现。动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

对于分组背包问题：每组物体只能使用其中的一种，这个问题类似于01背包问题每种物体只能选择1次，只是多了一个for循环来遍历选择组合中的哪种物体。

五、预习小结

动态规划问题是算法的难点和重点，里面涉及到的知识点较多，难度较大，需要较强的逻辑思维。经过预习后，我对动态规划算法也有了一定的认识。动态规划法是一种求解最优化问题的重要算法设计策略。对于一个问题，如果能从较小规模子问题的最优解求得较大规模同类子问题的最优解，最终得到给定问题的最优解，这就是问题最优解的最优子结枸特性。最优子结构特性使动态规划算法可以来用自底向上的方式进行计算，如果能在求解中保存已计算的子问题的最优解，当这些子最优解被重复引用时，则无须再次计算，从而节省了大量的计算时间。在本次实验的准备中，我查阅了相关资料，请教了其他同学，从而对此有了一定的理解。

实验3 动态规划实验

1. 实验目的

1.实验结果跟实验设置的参数关系很大，简要分析参数对结果的影响。掌握算法时间复杂度分析。通过一个规模较大的实例比较不同方法的求解速度，分析不同算法的时间复杂度，并分析是否能获得最优解。

2.掌握与动态规划相关的算法的基本原理和思想。设计了动态规划相关问题的最优算法代码。并总结其学习方法。

3.掌握不同算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。

1. 可行性分析

1.可以去掉这个术语和变量的数量，并决定它是一维数组、二维数组还是多维数组。

2.写下初始值，通常是在某些变量为1或0的特殊情况下的解决方案。

3.通过循环，通常是两个循环，中间的每一层表示一个变量的增量。

4.在循环的中间，写出相应的递归关系表达式，解决问题的每个项。

1. 方案设计

1.在这个问题中，青蛙可以随意跳过n步，第n步是通过保存前面n-1步的值，并将自己添加到直接到达第n步的方法中而获得的。它可以分解成公式f (n)=f (1)+..f（n-1）+1以f（n-1）+1的形式存在，但通过以后的算法可以简化公式得到2的（n-1）次幂。

2.有向无环图（DAG）G的拓扑排序是通过将G中的所有顶点排列成一个线性序列，使图中的任何一对顶点u和v都有边&u，v>；∈E (G)，然后u以线性序列出现在v之前。通常，这种线性序列被称为拓扑序序列，或简称拓扑序列。简单地说，一个集合上的部分顺序导致该集合上的完整顺序。这个操作被称为拓扑排序。

3.给定一个带权有向图G=(V,E），其中每条边的权都是非负实数。另外，还给定V中的一个顶点，称为源，现在要求解的是从源到其他所有顶点的最短路长度，即所经过路径的权的和，这就是所谓的单源最短路径问题。

4.Dijkstra算法是解单源最短路径问题的一个贪心算法，其思想是：设置顶点集合S并不断做贪心选择来扩充这个集合，初始时，S中仅包含源，设u为G的某一顶点，并用数组dist记录当前每个顶点所对应的最短路径长度，Dijkstra算法每次从V-S中取出具有最短路径长度的顶点u，将u添加到S中，同时对数组dist做必要的修正。一旦S包含了所有V中的顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。dijkstra算法求单源最短路简单扩展，我们再创建一个value数组储存花费情况。在松弛时对value进行改变。松弛成功则value（s->i）=value(s->k->i)。若最短路相等则对value值进行比较，即value（s->i）=min(value(s->k->i),value（s->i))。s为源点，i为当前终点，k为中间点。最终输出最短路及对应value值即可。

1. 代码设计与开发

1.签到题之青蛙爬楼梯

测试方案：5

代码：

#include<stdio.h>

#include<math.h>

long long step[50];

long long climbStairs(int n)

{

    if(n==1)

 {

     step[n]=1;

 }

 else

 {

  step[n]=2*climbStairs(n-1);

 }

 return step[n];

}

int main()

{

 int n = 0;

 scanf("%d", &n);

 printf("%lld\n",climbStairs(n));

 return 0;

}

2.排名

测试方案：

4 3

1 4

4 3

2 3

代码：

#include<iostream>

#include<cstring>

#include<vector>

#include<set>

int v[501];//度

int c[501][501];

using namespace std;

int main()

{

int n,m,x,y;

while(cin>>n>>m)

{

 memset(v,0,sizeof(v));//全部清0

 memset(c,0,sizeof(c));

 for(int i=0;i<m;i++)

 {

  cin>>x>>y;

  if(!c[x][y])

  {

   c[x][y]=1;//标记度为0的节点

   v[y]++;//度加一

  }

 }

 for(int i=1;i<=n;i++)

 {

  for(int j=1;j<=n;j++)

  {

   if(!v[j])

   {

    v[j]--;//度减

    cout<<j;///输出度为0的点

    if(i!=n)

    cout<<" ";

    else

    cout<<endl;

    for(int k=1;k<=n;k++)

    {

     if(c[j][k])//寻找j的下一个点

     {

      v[k]--;

     }

    }

    break;

   }

  }

 }

}

return 0;

}

3.系兄弟

测试方案：

3 3 2 1

1 2 1

2 3 1

3 1 1

2 3

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 107;

const int inf = 0x3f3f3f3f;

int n,m,k,s;

int dis[maxn];  

int road[maxn][maxn];   

bool vis[maxn];    

int fans[maxn];     

void dijkstra(int s)

{

    memset(vis, false, sizeof(vis));

    vis[s] = true;

    for(int i = 1; i <= n; i++)

        dis[i] = road[s][i];

    for(int u = 1; u<n; u++)

    {

        int minD = inf,k = -1;

        for(int i = 1; i<= n; i++)

        {

            if(!vis[i]&&dis[i]<minD)

            {

                k = i;

                minD = dis[i];

            }

        }

        vis[k] = true;

        //松弛操作

        for(int i = 1; i<= n; i++)

        {

            if(!vis[i]&&dis[k]+road[k][i]<dis[i])

            {

                dis[i]=dis[k]+road[k][i];

            }//if

        }//for

    }

}

int main()

{

    while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF){

        memset(road,inf,sizeof(road));

        for(int i=1;i<=m;i++)

        {

            int a,b,d;

            scanf("%d%d%d",&a,&b,&d);

            road[b][a]=min(d,road[b][a]);//逆向建边

        //起点是fans[i],终点是S

        }

        for(int i=1;i<=k;i++)

        scanf("%d",&fans[i]);

        dis[s]=0;

        dijkstra(s);

        for(int i=1;i<=k;i++)

        {

            printf("%d",dis[fans[i]]);

            if(i==k)    printf("\n");

            else    printf(" ");

        }

    }

    return 0;

}

4.逛街

测试方案：

3 2

1 2 5 6

2 3 4 5

1 3

0 0

代码：

#include <stdio.h>

#include <string.h>

#define INF 0x3f3f3f3f

#define Min(a,b) a>b?b:a

struct Node

{

 int adj,val;

}g[1005][1005];

int dist[1005];//距离

int value[1005];//费用

int used[1005];//标记

int n,m,i,j;

void Dijkstra(int s)

{

 memset(dist,0x3f,sizeof(dist));

 memset(value,0x3f,sizeof(value));

 memset(used,0,sizeof(used));

 dist[s]=0;//从起点开始

 value[s]=0;

 while(1)

 {

  int k,u=-1,d[1005];

  int min=INF;

  memset(d,0,sizeof(d));

  for(i=1;i<=n;i++)

   if(used[i]==0&&dist[i]<min)//找出从起点到下一个最小距离的顶点

   {

    min=dist[i];//记录最小值

    u=i;//记录下标

   }

  if(u==-1)//判断所有顶点是否都到达过

   return ;

  

for(i=1,k=0;i<=n;i++)

   if(dist[u]==dist[i]&&used[i]==0)

    d[k++]=i;//从起点到下一个要访问的顶点的最小距离可能有多个

  for(i=0;i<k;i++)

   used[d[i]]=1;

  for(i=0;i<k;i++)//多个满足的点分别进行迪杰斯特拉最短路查找

   for(j=1;j<=n;j++)

    if(g[d[i]][j].adj!=INF && (dist[d[i]]+g[d[i]][j].adj)<=dist[j])

    {//原理与 main()函数中建立邻接矩阵一样

     if((dist[d[i]]+g[d[i]][j].adj)<dist[j])//小于的情况

      value[j]=value[d[i]]+g[d[i]][j].val;

     else

      value[j]=Min(value[j],value[d[i]]+g[d[i]][j].val);

     dist[j]=dist[d[i]]+g[d[i]][j].adj;

    }

 }

}

int main()

{

 while(scanf("%d%d",&n,&m) && (n||m))

 {

  int a,b,d,p;

  memset(g,0x3f,sizeof(g));

  for(i=1;i<=m;i++)

  {

   scanf("%d%d%d%d",&a,&b,&d,&p);

   if(d<=g[a][b].adj)//处理路径距离问题

   {

    if(d==g[a][b].adj)//如果距离相等，则存放最少的费用

     g[a][b].val=g[b][a].val=Min(p,g[a][b].val);

    else//否则，存放新路径距离的费用

     g[a][b].val=g[b][a].val=p;

    g[a][b].adj=g[b][a].adj=d;//填充路径距离

   

}

  }

  int s,t;

  scanf("%d%d",&s,&t);

  Dijkstra(s);

  printf("%d %d\n",dist[t],value[t]);

 }

 return 0;

}

1. 实验结果展示

1.签到题之青蛙爬楼梯

2.排名

3.系兄弟

4.逛街

1. 终身学习

自主学习的就要制订学习计划，加强时间管理。会搜集和处理信息，善于交流与合作;能自觉地制订学习计划，确定学习目标，组织学习活 动，自我监控学习过程;能主动选择学习策略，自我评价学习结果，积极创设最优化的学习内部环境与外部环境。这个领域很前沿的知识，这个可以去相关杂志网站去仔细查找，如通过知网进行文献查找和分析，了解相关领域的前沿信息和发展方向。