注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

动态规划算法初探  

2015-06-16 10:28:36|  分类: 常用算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


    本人是学控制出生的,对动态规划比较敏感,每次见到动态规划都是联想到控制里面求解最优值的问题。严格来说算法里面的动态规划还是和控制上有一定的区别的,我的理解是尽管二者都是把比较大的问题化为小问题来做,而控制上的问题一般会遇到维数灾难的问题,主要是因为它智能递归求解,不能迭代求解。所以这里先从最简单的递归到动态规划问题转化谈起,而动态规划的本质是将比较复杂的问题分解为容易求解的子问题。

    斐波拉契数列

    这个应该是学习算法遇到的第一个动态规划求解的问题,问题可以这么表述:

a[0]=1,a[1] =1,给定递推公式a[i]=a[i-1]+a[i-2];求解a[n]。如果对一个没有学过算法的cs同学话,以上肯定会写递归的,课本上的例题就是这么干的。不过想想,如果n=10000,这个递归栈该需要开多少空间啊!一旦数字一大,肯定爆栈的,所以一般来说,我们能用迭代方法就不会用递归的,这个在我的另一篇博客里面也有写到。而且这么写递归的话,还有一个问题,就是不断重复计算子问题。我们可以看到如果求解a[10]的话,需要有a[10]=a[9]+a[8],调用递归的时候计算一次a[9]和a[8],而可以看到a[9]=a[8]+a[7],所以计算a[9]的时候,又会计算到a[8],所以很多子问题会被计算很多次。如果读者能画出递归树的话,就能看到,越到树下面,子问题被计算的次数会越多,导致整个问题是指数复杂度。

    这里我们可以想一下,反正要求解子问题的,不如开始的直接求好了,存在那里,后面直接用就可以了,不必每次都计算。所以这里开一个数组dp[i],表示当前的a[i]。可以做一个循环,从2->n,依次计算,计算dp[i]的时候dp[i-1]和dp[i-2]都计算好了,所以循环能够顺利的进行下去,而且分析一下可以看到解决该问题是线性复杂度的!!!

    股票量化交易问题I

问题:给定一段时间的股票价格,至多交易一次(购买必须在卖出之前),求能获得的最大利润?

    第一眼看到,我去什么鬼?直接遍历区间就行了。抱歉,暴力遍历是n^2复杂度,不行。那很多牛人都想了不少法子,目前最好的方法就是动态规划了。首先我们希望把这个问题转化容易求解的子问题,

给定一个数组dp[i]:表示以0-i天交易的最大收益

等我们计算出dp[i-0:n-1]之后。但是如何得到dp的递推公式呢?我们看一个序列[ 4 6 -3 7],首先从2开始,如果卖出的话收益是2,接着如果是i=2卖出的话收益是0,因为这个地方卖出的是负值,不要交易,然后i=3的话,我们找到7,就需要找7前面的最小值(因为这样才能找到最大利润),lowest价格是-3,所以在i=3卖出的话能得到10的收益,扫描一下,最大收益就是10。

    在上面的简单分析中我们直到dp[i]是全局最优值(全局最优是我们要求解的)。这里的过程是这样的,每次遇到一个pricec[i]我们就要计算prices[i]-lowest值(局部最优),看它是否是比dp[i-1],如果大的话那么dp[i]就更新,否则dp[i]=dp[i-1]。递推公式这样描述,

dp[i]=max(dp[i-1],prices[i]-lowest)

dp[i-1]描述0-i-1天的最大收益,prices[i]-lowest表示i天卖出的最大收益(局部最优),所以dp[i](全局最优)肯定是两个中间的较大值。关于局部最大和全局最大后面会讨论,所以整个过程的代码如下:

class Solution {
public:
int maxProfit(vector<int>& prices) {
return getProft(prices);
}
//可以维护两个数组,dpMin dpMax,存储当前的最小值和最大值,最后扫描一遍即可
int getProft(vector<int>& prices)
{
if (prices.size() == 0) return 0;
int profit = 0;
int lowest = prices[0];
for (int i = 0; i < prices.size(); i++)
{
//更新上界 可以记录她的最大值
if (prices[i] - lowest > profit) profit = prices[i] - lowest;
if (prices[i] < lowest) lowest = prices[i]; //更新下界
}
return profit;
}
};


 

    股票量化交易问题II

问题:给定一段时间的股票价格,至多交易无数次(购买必须在卖出之前),求能获得的最大利润?

    如果这个问题单独拿出来其实很好解的,如果和I放在一起的话就会混淆我们的思维。我们可以这么想,反正可以交易无数次,只要我们遇到价格上身地方我们就交易,下降的就不交易,这个问题就好解决了,所以这里并未用到动态规划。

    股票量化交易问题III

问题:给定一段时间的股票价格,至多交易两次(购买必须在卖出之前),求能获得的最大利润?

    同理这一题目,咋看起来也没有什么思维,不过我们可以用划分的方法,从i=0:n-1,固定当前i,i前面完成第一次交易,i后面是第二次交易,这样最后求一下和,扫描一下找最大值,这样问题就得到解决了。代买如下:

 

class Solution {
public:
int maxProfit(vector<int>& prices) {
return getProfit(prices);
}
//可以维护两个数组,dpMin dpMax,存储当前的最小值和最大值,最后扫描一遍即可
int getProfit(vector<int>& prices)
{
if (prices.size() == 0) return 0;
int n = prices.size();
vector<int>dpLeft(n, 0), dpRight(n, 0);
int lowest = prices[0];
dpLeft[0] = 0;
for (int i = 1; i < prices.size(); i++)
{
//更新下界 可以记录她的最大值
lowest = min(prices[i],lowest);
dpLeft[i] = max(dpLeft[i-1],prices[i]-lowest);
}
dpRight[n - 1] = 0;
int highest = prices[n - 1];
for (int i = n - 2; i >= 0; i--)
{
//更新上界
highest = max(prices[i],highest);
dpRight[i] = max(dpRight[i+1],highest-prices[i]);
}
int profit=0;
for (int i = 0; i < n; i++) profit = max(dpRight[i] + dpLeft[i] ,profit);
return profit;
}
};


    动态规划中的全局最优和局部最优

为什么我们需要局部最优?开篇我们已经说过了,动态规划的本质是将复杂的问题划分为简单的小问题,但是这个过程怎么做的呢?一般而言,很多问题就需要先找局部最优,最后线性扫描得到全局最优。这里分析一下量化交易I,我们开的数组dp[i]其实就是全局最优。我们的递推公式是这样的 dp[i]=max(dp[i-1],prices[i]-lowest),很多动态规划问题都是将大问题划分为求局部最优的子问题的,再通过局部最优的子问题往上递推。在问题III中,因为几乎是问题I的复用,所以思想是一样的,只不过开了两个数组,一个是dpLeft[i]表示从左到右交易,dpRight[i]表示从右向做交易,dpLeft[i]和dpRight[i]都是i处的全局最优,线性扫描比较一遍,最后就是至多两次交易的最大值。后面关于局部最优和全局最优还会更基于实际问题给出说明。

 

股票量化交易问题IV

问题:给定一段时间的股票价格,至多交易k次(购买必须在卖出之前),求能获得的最大利润?(极限情况是可以k>=交易天数,下面分析暂时不考虑这种特殊情况,它在II中已经解决)

    这里详细用局部最优和全局最优来解释动态规划的过程。这里假设两个变量

global[i][j]:当前达到第i天可以进行最多j次交易,所得到最大利润

local[i][j]: 当前达到第i天可以进行最多j次交易,而且最后一次交易是在第j天完成的最大利润。

我们可以看到关于局部最大利润的定义都是涉及到最后一天的,而全局最优就没有这个限制,例如在I问题里面局部最优是prices[i]-lowest,当然上面的题也可以开一个数组local来维护这个变量,但是没有必要

    下面回到我们这边的问题,有了这个问题分解,如果求解状态转移方程呢?

状态转移:global[i][j] = max(global[i][j],local[i][j])

从这个公式我们看到全局最优一定是,前一个状态全局最优和当前状态的局部最优,在问题里面的转移方程也是 dp[i]=max(dp[i-1],prices[i]--lowest),所以说这个公式是很重要,后面还会提到。

 

有了全局最优转移方程,如何确定局部的转移方程了

local[i][j] = max(global[i-1][j-1] + max(diff, 0), local[i-1][j] + diff)

对于局部最优,这里可以这么去想,我们在最后一天完成交易,可以是全局前面global[i-1][j-1]加上后面最后一天的交易,也可以是local[i-1][j],前面一天我们不卖了,我在第i天买,也就是就是local[i-1][j]+dff赚的。

global[i-1][j-1] + max(diff, 0): 全局到i-1天进行j-1次交易,然后加上今天的交易(如果今天的交易赚钱的话)。

local[i-1][j] + diff : 取局部第i-1天进行j次交易,然后加上今天的差值(local[i-1][j]是第i-1天卖出的交易,它加上diff后变成第i天卖出,并不会增加交易次数。无论diff是正还是负都要加上,否则就不满足local[i][j]必须在最后一天卖出的条件了)

 

class Solution{
public:
/*
*其实可以求至少k次交易的最大利润。
*我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易
*在最后一天卖出的最大利润,此为局部最优。
*然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润,此为全局最优
* local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
* global[i][j] = max(local[i][j], global[i - 1][j]),
* 其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值,
* 和前一天的局部最优加上差值后相比,两者之中取较大值,而全局最优比较局部最优和前一天的全局最优。
*/
int maxProfit(int k, vector<int> &prices)
{
if (prices.empty() || k == 0)
return 0;

if (k >= prices.size()) //次数很多的样子
return solveMaxProfit(prices);

vector<int> global(k + 1, 0);
vector<int> local(k + 1, 0);

for (int i = 1; i < prices.size(); i++)
{
int diff = prices[i] - prices[i - 1];
for (int j = k; j >= 1; j--)
{
local[j] = myMax(local[j] + diff, global[j - 1] + myMax(diff, 0));
global[j] = myMax(global[j], local[j]);
}
}

return global[k];
}
int myMin(int a, int b)
{
return a > b ? b : a;
}
int myMax(int a, int b)
{
return a > b ? a : b;
}
private:
int solveMaxProfit(vector<int> &prices)
{
//这个是解可以交易任意次的,也就是II那一道题的
int res = 0;
for (int i = 1; i < prices.size(); i++)
{
int diff = prices[i] - prices[i - 1];
if (diff > 0)
res += diff;
}
return res;
}
};



最大连续子组和

问题:给定一个数组,求数组里面连续元素和的最大值。例如对于[4, -2, 1, 6]。

对于最大连续子组和,我们同样用局部最优和全局最优来分析这个问题。首先我们开一个数组

dp[i]:表示以a[i]结尾元素的连续数组的最大和,这是一个局部最优值

那么它的转移方程就是dp[i]=max(dp[i-1]+a[i],a[i])

为什么会是这样呢?因为dp[i-1]可能变成负数了,如果只用dp[i-1]+a[i],就不是最大值了。那么有人会问,为什么一定是dp[i-1]+a[i]而不是a[k-i]呢?k表示dp[i-1]起点后面的一个index。这里假设你说的正确的dp[i-1]的起点是j,那么sum(a[f-i])<sum(s[k-i]),就有那么sum(a[f-i-1])<sum(s[k-i-1]),这样dp[i-1]就不是局部最优了!!所以这种情况是不存在的。既然右了局部最优,最后扫描一下这个序列就能得到全局最优值了,或者你在dp计算的过程中也可以记录一下。

    在实际的最大连续子组和求解程序里面,其实我们并不需要维护dp,秩序要直到当前的dp[i]就能得到最终的结果。这里是我写的一个求解最大子组和的代码。

我们这里可以分析一下ps,pe维护的是全局最优的区间,ts,te维护的是局部最优的区间,sum维数的是dp[i],max维护的全局最优值,在dp计算的过程中max就可以同时计算出来。

    首先当sum<=0的时候,dp[i]重置,就是转移方程里面第二项,ts和te重置

    如果sum>0,说明序列还在递增,te下标向前,而sum+=prices[i],这就是局部最优

    同时如果sum>max,说明全局最优要更新,max=sum, ps和pe都需要更新为ts,te。

整个过程中并没有看到dp[i]的影子,但其实是放在sum和ps,pe里面了。

 

int maxProfit1(int* prices, int pricesSize) {
// 动态规划 复杂度是o(n)
// 递推公式是 dp[i] = max(dp[i-1]+nums[i],nums[i])
int i, j;
int ps, pe;
int ts, te; //记录临时起点和终点
int max = INT_MIN; //初始化最小值
if (pricesSize <= 0)
return 0;
int sum = 0;
for (i = 0; i < pricesSize; i++)
{
if (sum <= 0)
{
sum = prices[i]; //把当前值赋给sum
ts = i; // 临时下标计数重置
te = i;
}
else
{
sum += prices[i];
// 如果sum为正数,把后面这个放进去
te = i;
}

if (sum > max)
{
//记录最大序列的和以及起点和终点
max = sum;
ps = ts;
pe = te;
}
}
printf("from %d to from %d == %d\n", ps, pe, max);
return max;
}


最大连续子组乘积

问题:给定一个数组,求数组里面连续元素乘积的最大值,例如[4, -2, 1, 6]。

    这个问题和上面的uida连续子组和几乎是一样的,不过这里需要开两个数组dpMax[i]和dpMin[i]来维护局部最优,因为可能如果只用一个dp[i]来维护的话可能出现正负,以及(0,1)区间,这个不好计算。所以状态转移方程是这样

dpMax[i] = max( a[i], dpMax[i-1]*a[i], dpMin[i-1]*a[i]);

dpMin[i] = min( a[i], dpMax[i-1]*a[i], dpMin[i-1]*a[i]);

而全局最优值,max每次和最新的dpMax[i]比较,就可以了,最后就输出了最优结果。

 

class Solution {
public:
//维护两个数组
//max[i]表示以a[i]结尾的数组的最大乘积
//min[i]表示以a[i]结尾的数组的最小乘积

//这样的话max[i] = max(a[i],max[i-1]*a[i],min[i-1]*a[i])
//这样的话min[i] = min(a[i],max[i-1]*a[i],min[i-1]*a[i])
int maxProduct(vector<int>& nums) {

int len = nums.size();
if (len < 1)
return 0;
vector<int>Max(len, 0);
vector<int>Min(len, 0);
Max[0] = nums[0];
Min[0] = nums[0];
int i;
vector<int> array(3,0);
int maxValue = nums[0];
int maxPro,minPro;
for (i = 1; i < len; i++)
{
array[0] = nums[i];
array[1] = Max[i - 1] * nums[i];
array[2] = Min[i - 1] * nums[i];
Max[i] = myMax(array);
Min[i] = myMin(array);
if (maxValue < Max[i])
maxValue = Max[i];
}
return maxValue;
}
int myMin(vector<int> array)
{
int i = 0;
int len = array.size();
int min = array[0];
for (i = 1; i < len; i++)
if (array[i] < min)
min = array[i];
return min;
}
int myMax(vector<int> array)
{
int i = 0;
int len = array.size();
int max = array[0];
for (i = 1; i < len; i++)
if (array[i] > max)
max = array[i];
return max;
}
};


  

小结

个人感觉动态规划精髓就是在于局部最优和全局最优交替迭代的过程,通过不断迭代求解局部最优,最优找到全局最优,无论是股票交易、连续子组、子组乘积以及最大公共子序列问题(在我的另一篇博客里面专门写了这个算法)。在这个过程中需要准确构造出局部最优的转移方程或者全局最优转移方程,上面讲的几个例子里里面股票交易IV算是状态转移最复杂的一个。但是如果真的分析透彻了的话,就会发现,他们的全局最优值的转移方程都是一样的都是取前一个状态的全局最优和当前状态的局部最优得到当前状态的全局最优global[i][j] = max(global[i][j],local[i][j]),而当前状态的局部最优,形式就比较多了,需要实际问题区别对待,但是只要把握住第一条关于global的规则,一般都能求解出来。

 

 

参考

http://wanghaitao8118.blog.163.com/blog/static/1398697722015414914581/

http://wanghaitao8118.blog.163.com/blog/static/13986977220154149545965/

http://wanghaitao8118.blog.163.com/blog/static/139869772201541693230158/

http://wanghaitao8118.blog.163.com/blog/static/13986977220154229338506/

http://wanghaitao8118.blog.163.com/blog/static/13986977220154219414350/

http://blog.csdn.net/foreverling/article/details/43911309

  评论这张
 
阅读(61)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017