数学之美系列二十四 -- 谈谈动态规划与如何设计动态规划算法

2024-04-29 17:48

本文主要是介绍数学之美系列二十四 -- 谈谈动态规划与如何设计动态规划算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

数学之美——动态规划

今 年九月二十三日,Google、T-Mobile 和 HTC 宣布了第一款基于开源操作系统 Android 的 3G 手机,其中一个重要的功能是利用全球卫星定位系统实现全球导航。这个功能在其它手机中早已使用,并且早在五六年前就已经有实现这一功能的车载设备出售。其 中的关键技术只有两个:第一是利用卫星定位;第二根据用户输入的起终点,在地图上规划最短路线或者最快路线。后者的关键算法是计算机科学图论中的动态规划 (Dynamic Programming)的算法。

在图论(请见拙著《图论和网络爬虫》) 中,一个抽象的图包括一些节点和连接他们的弧。比如说中国公路网就是一个很好的"图"的例子:每个城市一是个节点,每一条公路是一个弧。图的弧可以有权 重,权重对应于地图上的距离或者是行车时间、过路费金额等等。图论中很常见的一个问题是要找一个图中给定两个点之间的最短路径(shortest path)。比如,我们想找到从北京到广州的最短行车路线或者最快行车路线。当然,最直接的笨办法是把所有可能的路线看一遍,然后找到最优的。这种办法只 有在节点数是个位数的图中还行得通,当图的节点数(城市数目)有几十个的时候,计算的复杂度就已经让人甚至计算机难以接受了,因为所有可能路径的个数随着 节点数的增长而成呈指数增长(或者说几何级数),也就是说每增加一个城市,复杂度要大一倍。显然我们的导航系统中不会用这种笨办法。


所有 的导航系统采用的都是动态规划的办法(Dynamic Programming),这里面的规划(programming)一词在数学上的含义是"优化"的意思,不是计算机里面编程的意思。它的原理其实很简 单。以上面的问题为例,当我们要找从北京到广州的最短路线时,我们先不妨倒过来想这个问题:假如我们找到了所要的最短路线(称为路线一),如果它经过郑 州,那么从北京到郑州的这条子路线(比如是北京-> 保定->石家庄->郑州,称为子路线一),必然也是所有从北京到郑州的路线中最短的。否则的话,我们可以假定还存在从北京到郑州更短的路线 (比如北京->济南->徐州->郑州,称为子路线二),那么只要用这第二条子路线代替第一条,我们就可以找到一条从北京到广州的全程更 短的路线(称为路线二),这就和我们讲的路线一是北京到广州最短的路线相矛盾。其矛盾的根源在于,我们假设的子路线二或者不存在,或者比子路线一还来得 长。

 

在实际实现算法时,我们又正过来解决这个问题,也就是说,要想找到从北京到广州的最短路线,先要找到从北京到郑州的最短路线。当然, 聪明的读者可能已经发现其中的一个"漏洞",就是我们在还没有找到全程最短路线前,不能肯定它一定经过郑州。不过没有关系,只要我们在图上横切一刀,这一 刀要保证将任何从北京到广州的路一截二,如下图。

那 么从广州到北京的最短路径必须经过这一条线上的某个城市(图中蓝色的菱形)。我们可以先找到从北京出发到这条线上所有城市的最短路径,最后得到的全程最短 路线一定包括这些局部最短路线中的一条,这样,我们就可以将一个"寻找全程最短路线"的问题,分解成一个个小的寻找局部最短路线的问题。只要我们将这条横 切线从北京向广州推移,直到广州为止,我们的全程最短路线就找到了。这便是动态规划的原理。采用动态规划可以大大降低最短路径的计算复杂度。在我们上面的 例子中,每加入一条横截线,线上平均有十个城市,从广州到北京最多经过十五个城市,那么采用动态规划的计算量是 10×10×15,而采用穷举路径的笨办法是 10 的 15 次方,前后差了万亿倍。

 

那么动态规划和我们的拼音输入法又有什么关系呢?其实我们可以将汉语输入看成一个通信问题,而输入法则是一个将拼音串到汉字串的转换器。每一个拼音可以对应多个汉字,一个拼音串就可以对应图论中的一张图,如下:

其 中,Y1,Y2,Y3,……,YN 是使用者输入的拼音串,W11,W12,W13 是第一个音 Y1 的候选汉字,W21,W22,W23,W24 是对应于 Y2 的候选汉字,以此类推。从第一个字到最后一个字可以组成很多很多句子,我们的拼音输入法就是要根据上下文找到一个最优的句子。如果我们再将上下文的相关性 量化,作为从前一个汉字到后一个汉字的距离,那么,寻找给定拼音条件下最合理句子的问题就变成了一个典型的"最短路径"问题,我们的算法就是动态规划。

上面这两个例子导航系统和拼音输入法看似没什么关系,但是其背后的数学模型却是完全一样的。数学的妙处在于它的每一个工具都具有相当的普遍性,在不同的应用中都可以发挥很大的作用。

如何设计和实现动态规划算法

进行算法设计的时候,时常有这样的体会:如果已经知道一道题目可以用动态规划求解,那么很容易找到相应的动态规划算法并实现;动态规划算法的难度不在于实现,而在于分析和设计—— 首先你得知道这道题目需要用动态规划来求解。本文,我们主要在分析动态规划在算法分析设计和实现中的应用,讲解动态规划的原理、设计和实现。在很多情况下,可能我们能直观地想到动态规划的算法;但是有些情况下动态规划算法却比较隐蔽,难以发现。本文,主要为你解答这个最大的疑惑:什么类型的问题可以使用动态规划算法?应该如何设计动态规划算法?

动态规划第一讲——缓存与动态规划

一、缓存与动态规划

例一:有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?

分析:很显然,这道题的对应的数学表达式是F(n)=F(n-1) + F(n-2);其中F(1)=1, F(2)=2。很自然的状况是,采用递归函数来求解:

int  solution(int n){  if(n>0 && n<2) return n;  return solution(n-1) + solution(n-2);  
}  

 
 

    如果我们计算F(10), 先需要计算F(9) F(8); 但是我们计算F(9)的时候,又需要计算F(8),很明显,F(8)被计算了多次,存在重复计算;同理F(3)被重复计算的次数就更多了。算法分析与设计的核心在于 根据题目特点,减少重复计算。  在不改变算法结构的情况下,我们可以做如下改进:

int dp[11];  
int  solution(int n){  if(n>0 && n<2) return n;  if(dp[n]!=0) return dp[n];  dp[n] = solution(n-1) + solution(n-2);  return  dp[n];  
}  

这是一种递归形似的写法,进一步,我们可以将递归去掉:

int  solution(int n){  int dp[n+1];  dp[1]=1;dp[2]=2;  for (i = 3; i <= n; ++i){  dp[n] = dp[n-1] + dp[n-2];  }  return  dp[n];  
}  

当然,我们还可以进一步精简,仅仅用两个变量来保存前两次的计算结果; 这个算法留待读者自己去实现

例二:01背包问题

有n个重量和价值分别为vector<int> weight, vector<int> value的物品;背包最大负重为W,求能用背包装下的物品的最大价值?

输入:n =4 
weight=2, 1, 3, 2
value =3, 2, 4, 2
W=5
输出=7

思考一:我们可以采用穷举法,列出n个物品的所有组合形式,从中选取符合条件的最大价值:

采用穷举法,必然需要能够举出所有状态,不重不漏;而如何穷举,方法多种多样,我们的任务是要穷举有n个元素组成的所有子集。而穷举的方法主要有两种—— 递增式(举出1~100之内的所有数字, 从1到100);和分治式的穷举(例如举出n个元素的集合,包含两种—— 含有元素a和不含元素a的)。于是,我们基于穷举法得到背包问题的第一种算法—— 递归与分治。

int rec(int i, int j){//从i到n号物品,选择重量不大于j的物品的最大价值  int res;  if(i==n){  res=0;  }   else if(j< w[i]){  res = rec(i+1, j);  }  else{  res = max(rec(i+1, j), rec(i+1, j-w[i])+v[i]);  }  return res;  
}  

调用res(0, W), 即可得到结果. 时间复杂度O(2^n);我们来分析一下递归调用的情况。


为了偷懒,最后一行没有画出来,但是注意红色的部分,我们会发现(3, 2)这个子问题被计算了两次,很显然,如果问题规模足够大,数据足够多样,这种重复计算导致的时间耗费将更多。

改进:采用递归加缓存的策略
此时,时间复杂度是O(nW); 代码就省略不写了。

思考二:上文中的记忆化搜索,如果可以将递归变为循环,这就是动态规划,对应的数学表达式如下:

dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);//对应的计算表格如下和程序如下:  
void solution(){  fill(dp[n], dp[n]+W, 0);  for (int i = n-1; i >= 0; --i){  for (j = 0; j <= W; ++j){  if(j < w[i]) dp[i][j] = dp[i+1][j];  else dp[i][j] = max(dp[i+1][j], dp[i+!][j-w[i]]+v[i]);  }  }  return dp[0][W];  
}  

思考三:递归形式的多样化

我们刚才的递归计算,在i这个维度是逆向的,同样我们可以采用正向的DP。规定dp[i][j]表示前i号物品中能选出重量在j之内的最大价值,则有递推式
dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i]] + v[i]);

思考四:我们是如何想到递归算法的?

也许,DP算法的难度不在于告诉你这个题目需要用DP求解,然后让你来实现算法。而在于你首先得意识到这道题目需要用递归求解,这里我们通过分析上面的思考步骤来总结DP算法的典型特征:
1>DP算法起源于DC—— 一个问题的解,可以先分解为求解一系列子问题的解,同时包含重叠子问题:于是,我们得到DP算法的第一个黄金准则:某个问题具有独立而重叠的字问题;子问题不独立,没法进行分治;子问题不重叠,没有进行DP的必要,直接用普通的分治法就可以了。
2>DP算法黄金准则2: 最优子问题—— 子问题的最优解可以推出原问题的最优解。

我们还是来看上面的那个决策树,很明显,DP的本质就在于缓存。我们寻找DP结果的时候,往往是需要遍历这个树,从中找出最优解。但是有些情况下,我们需要寻找的不是最优解,而是可行解,这个时候往往使用DFS或者循环更为有效,后面,我们会给出例子。此时,我们仅仅需要记得,动态规划的第二个条件—— 最优子问题。

所以算法的设计思路不在于一下子就想到了某个问题可以使用DP算法,而在于先看能不能用穷举法,如果可以用问题可以分解,分治法+穷举可以解决;如果问题包含重叠字问题,并且是求解最优解,那么此时用动态规划。

动态规划第二讲——完全背包与多重背包问题

http://blog.csdn.net/trochiluses/article/details/38016349  完全背包
http://blog.csdn.net/trochiluses/article/details/38017007  序列号背包


这篇关于数学之美系列二十四 -- 谈谈动态规划与如何设计动态规划算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/946749

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl