小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. 正文

解析动态规划问题(2)

2019年2月21日 957点热度 0人点赞 0条评论

最优三角剖分

与矩阵连乘的不同点

不同点就在于递归公式的不同,最优三角剖分的递归公式如下:
当i=j的时候,m[i][j]=0;
当i<j的时候,m[i][j]=min{m[i][k]+m[k+1][j]+w(v(i-1)vkvj)}

图解示例

我们以一个凸多边形为例,其每条边的权重如下表所示

g[][] 0 1 2 3 4 5
0 0 2 3 1 5 6
1 2 0 3 4 8 6
2 3 3 0 10 13 7
3 1 4 10 0 12 5
4 5 8 13 12 0 3
5 6 6 7 5 3 0

(1)初始化:令m[i][i]=0,s[i][i]=0
(2)计算赋值如下:

m[][] 1 2 3 4 5
1 0 8 22 40 54
2 0 17 41 52
3 0 35 42
4 0 20
5 0|3
s[][] 1 2 3 4 5
1 0 1 2 3 3
2 0 2 3 3
3 0 3 3
4 0 4
5 0

所以最优权值为m[1][5]=54
(3)构造最优解。过程与矩阵快速相乘类似,都是根据s[][]对应的位置来分成子问题,所以首先是看到s[1][5]=3,所以分为了v0~ v3 和 v3~v5。

  • 因为v0~v3中有结点,所以子问题1不为空,输出该弦v0v3;同理,输出v3v5。
  • 对于子问题1进行递归,读取s[1][3]=2,因为v0~v2有结点,所以输出v0v2……
  • 最后输出的最优解为v0v3,v3v5,v0v2。

代码实现

void  Convexpolygontriangulation()
{
    for(int i = 1 ;i <= n ; i++)    // 初始化
    {
        m[i][i] = 0 ;
        s[i][i] = 0 ;
    }
    for(int d = 2 ;d <= n ; d++)         // 枚举点的个数
      for(int i = 1 ;i <= n - d + 1 ; i++)  // 枚举起始点
      {
          int j = i + d - 1 ;         // 终点
          m[i][j] = m[i+1][j] + g[i-1][i] + g[i][j] + g[i-1][j] ;
          s[i][j] = i ;
          for(int k = i + 1 ;k < j ; k++)     // 枚举中间点
          {
              double temp = m[i][k] + m[k+1][j] + g[i-1][k] + g[k][j] + g[i-1][j] ;
              if(m[i][j] > temp)
              {
                  m[i][j] = temp ;   // 更新最优值
                  s[i][j] = k ;      // 记录中间点
              }
          }
      }
}
void print(int i , int j)  // 输出所有的弦
{
    if(i == j)  return ;
    if(s[i][j]>i)
      cout<<"{v"<<i-1<<"v"<<s[i][j]<<"}"<<endl;
    if(j>s[i][j]+1)
      cout<<"{v"<<s[i][j]<<"v"<<j<<"}"<<endl;
    print(i ,s[i][j]);
    print(s[i][j]+1 ,j);
    //cout<<"{ v"<<i-1<<" , v"<<s[i][j]<<" , v"<<j<<" }"<<endl; //输出所有剖分后的三角形
}

石子合并

递归公式:

设Min[i][j]代表从第i堆石子到第j堆石子合并的最小花费,Min[i][k]代表从第i堆石子到底k堆石子合并的最小花费,Min[k+1][j]代表从第k+1堆石子到第j堆石子合并的最小花费。那么递推式如下:
Min[i][j]=0,i=j
Min[i][j]=min{m[i][k]+m[k+1][j]+w(i,j)} i<j
同理,设Max[i][j]代表从第i堆石子到第j堆石子合并的最大花费,Max[i][k]代表从第i堆石子到底k堆石子合并的最大花费,Max[k+1][j]代表从第k+1堆石子到第j堆石子合并的最大花费。那么递推式如下:
Max[i][j]=0,i=j
Max[i][j]=max{m[i][k]+m[k+1][j]+w(i,j)} i<j

代码实现

void straight(int a[],int n)
{
    for(int i=1;i<=n;i++)  // 初始化
        Min[i][i]=0, Max[i][i]=0;
    sum[0]=0;
    for(int i=1;i<=n;i++)
       sum[i]=sum[i-1]+a[i];
    for(int v=2; v<=n; v++) // 枚举合并的堆数规模
    {
        for(int i=1; i<=n-v+1; i++) //枚举起始点i
        {
            int j = i + v-1; //枚举终点j
            Min[i][j] = INF; //初始化为最大值
            Max[i][j] = -1; //初始化为-1
            int tmp = sum[j]-sum[i-1];//记录i...j之间的石子数之和
            for(int k=i; k<j; k++) {   //枚举中间分隔点
                Min[i][j] = min(Min[i][j], Min[i][k] + Min[k+1][j] + tmp);
                Max[i][j] = max(Max[i][j], Max[i][k] + Max[k+1][j] + tmp);
            }
        }
    }
}
void Circular(int a[],int n)
{
    for(int i=1;i<=n-1;i++)
        a[n+i]=a[i];
    n=2*n-1;
    straight(a, n);
    n=(n+1)/2;
    min_Circular=Min[1][n];
    max_Circular=Max[1][n];
    for(int i=2;i<=n;i++)
    {
        if(Min[i][n+i-1]<min_Circular)
           min_Circular=Min[i][n+i-1];
        if(Max[i][n+i-1]>max_Circular)
           max_Circular=Max[i][n+i-1];
    }
}

时间复杂度为O(n3)

改进算法

最小值可以用四边形不等式来优化。
复杂度为O(n2)

void get_Min(int n)
{
    for(int v=2; v<=n; v++) // 枚举合并的堆数规模
    {
        for(int i=1; i<=n-v+1; i++) //枚举起始点i
        {
            int j = i + v-1; //枚举终点j
            int tmp = sum[j]-sum[i-1];//记录i...j之间的石子数之和
            int i1=s[i][j-1]>i?s[i][j-1]:i;
            int j1=s[i+1][j]<j?s[i+1][j]:j;
            Min[i][j]=Min[i][i1]+Min[i1+1][j];
            s[i][j]=i1;
            for(int k=i1+1; k<=j1; k++) //枚举中间分隔点
                if(Min[i][k]+ Min[k+1][j]<Min[i][j])
                {
                    Min[i][j]=Min[i][k]+Min[k+1][j];
                    s[i][j]=k;
                }
            Min[i][j]+=tmp;
        }
    }
}

void get_Max(int n)
{
    for(int v=2; v<=n; v++) // 枚举合并的堆数规模
    {
        for(int i=1; i<=n-v+1; i++) //枚举起始点i
        {
            int j = i + v-1; //枚举终点j
            Max[i][j] = -1; //初始化为-1
            int tmp = sum[j]-sum[i-1];//记录i...j之间的石子数之和
            if(Max[i+1][j]>Max[i][j-1])
               Max[i][j]=Max[i+1][j]+tmp;
            else
               Max[i][j]=Max[i][j-1]+tmp;
        }
    }
}

void straight(int a[],int n)
{
    for(int i=1;i<=n;i++)  // 初始化
        Min[i][i]=0, Max[i][i]=0, s[i][i]=0;
    sum[0]=0;
    for(int i=1;i<=n;i++)
       sum[i]=sum[i-1]+a[i];
    get_Min(n);
    get_Max(n);
}
void Circular(int a[],int n)
{
    for(int i=1;i<=n-1;i++)
        a[n+i]=a[i];
    n=2*n-1;
    straight(a, n);
    n=(n+1)/2;
    min_Circular=Min[1][n];
    max_Circular=Max[1][n];
    for(int i=2;i<=n;i++)
    {
        if(Min[i][n+i-1]<min_Circular)
           min_Circular=Min[i][n+i-1];
        if(Max[i][n+i-1]>max_Circular)
           max_Circular=Max[i][n+i-1];
    }
}
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 动态规划 算法
最后更新:2019年2月21日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
大二上学期期末考试复习计划 [leetcode]题目解析(190524) Leetcode题目解析(191105) WordPress风格—Brown World(个人修改版) 元旦竞猜活动开启 python处理csv文件,以锡特卡气温为例
标签聚合
leetcode 学习 linux Java 鸟哥的linux私房菜 生活 Python 算法 高中 python学习
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号