动态规划(Dynamic Programming)
admin
2024-04-01 08:42:53
0次

我们清楚的知道使用分治算法来求解决斐波那契数列的效率惊人的低,其中的原因是,斐波那契数列分解成的两个子问题并不是独立的,它们之间有着非常多的交集,而在递归中,这些交集会被计算成百上千次,从而降低了算法的效率(这也是为什么分治算法要求子问题尽可能的不要相交)。如果观察斐波那契数列的通项公式f(n)=f(n-1)+f(n-2),我们会发现数列的第n项只与它之前的两项有关,那么知道这两项也就得到了f(n),这种从子问题出发,逐步得到原问题解的思想就是动态规划。

如果说递归思想是逆向的,我们先从原问题入手,逐步将它分割成最小的基本情况,然后再对它进行处理并得到原问题的答案,那么动态规划就可以看作是正向的。在动态规划中,我们先从子问题入手,逐步得到所有子问题的解,并将其保存在表中,最后组合成原问题的解,这与递归正好是逆向的。

动态规划实际上是递归问题的非递归写法。就像在拼图时,递归就是将整个拼图分割开,并递归的去解决各个部分(比如说,将拼图分为左右两部分,并将所有的拼图放在它们相应的部分),直到最后解决基本情况(可以是将两块拼图拼接起来,在递归的程序下,到此这个问题就已经得到了解决,因为所有拼图都处在正确的位置上,剩下的操作无非是一些简单的拼接);而动态规划则是将拼图一块一块得拼起来,最终得到整个拼图。虽然过程不同,但是递归与动态规划都得到了正确的解。

如果一个问题在数学上是递归的,那么它就一定可以写成递归算法,唯一的问题在于性能。通过前面的分析已经知道,如果子问题有交集,那么递归算法就会非常低效,所以当一个看起来是递归问题的子问题之间相交,那么最好使用动态规划来解决它。并且,只要是能从子问题中得到原问题最优解的问题,都可以使用动态规划来解决。

下面介绍动态规划的两个例子:

递归公式的求解:

求解递归公式C(N)=\frac{2}{N}\sum_{i=0}^{N-1}C(i)+N。

如果使用递归去解决这个问题,那么在求解第N项时的时间复杂度是T(N)=\sum_{i=0}^{N-1}T(i)+N,当N非常大时,这个时间复杂度显然非常的不理想,但是如果我们使用动态规划,将前N-1项的结果都保存在表中,那么算法的时间复杂度甚至可以提高到O(N),代码如下:

//递归解法,在n=30时就已经需要几秒的运行时间了
double solveRE(int i) {if (i == 0)return 1;double sum = 0;for (int j = i - 1; j >= 0; j--) {sum += solveRE(j);}return  2.0 * sum / i + i;
}//动态规划解法,即使是求第30000项,花费的时间也不长,两层for循环,时间复杂度为O(N^2),还可以优化
double solveDP(double* C, int n) {for (int i = 1; i <= n; i++) {double sum = 0;for (int j = 0; j < i; j++) {sum += C[j];}C[i] = 2.0 * sum / i + i;}return C[n];
}//优化后的动态规划算法,时间复杂度为O(N)
double solveDP(double* C, int n) {double sum = C[0];for (int i = 1; i <= n; i++) {C[i] = 2.0 * sum / i + i;sum += C[i];}return C[n];
}

矩阵乘法顺序安排:

有四个矩阵,A[50][10],B[10][40],C[40][30],D[30][5]。虽然矩阵乘法运算是不满足交换律的,但是满足结合律,这就意味着这四个矩阵任意添加括号来改变运算顺序,并且这些运算顺序得到结果需要的乘法次数也不相同,并存在着一个最优解。将两个阶数分别为p*q,q*r的矩阵相乘,所需要的乘法次数为pqr次。由于只有四个矩阵,所以可以先穷举出它的全部结果来看看不同顺序之间所需要的总乘法次数差距有多大:

乘法顺序乘法次数
(A((BC)D))16000
(A(B(CD)))10500
((AB)(CD))36000
(((AB)C)D)87500
((A(BC))D)34500

可以看到,最少的乘法次数几乎是最多乘法次数的九分之一,所以通过一些计算来得到最优的乘法顺序是值得的。并且要得到最小的乘法次数,就必须在所有的子问题中找出最小的那个解,所以这是一个动态规划问题。

对于有N个矩阵的乘法运算,其运算顺序总共有T(N)个,并且

T(N)=\sum_{i=1}^{N-1}T(i)T(N)

 设矩阵A_1,A_2,...,A_N,最后进行的乘法是(A_1A_2...A_i)(A_{i+1}A_{i+2}...A_N),那么有T(i)个可能计算(A_1A_2...A_i),T(N-i)个可能计算(A_{i+1}A_{i+2}...A_N),总共就有T(i)T(N-i)个可能,对于大的N来说,这个数量是非常巨大的,所以穷举搜索并不是一个可以接受的算法,所以需要使用一种更高效的算法。

我们设 c_i (1\leq i\leq N))是第i个矩阵的列数,那么它的行数就是c_{i-1},规定c_0是第一个矩阵的行数,这样就建立起了一个列数组c。

设m_{left,right}是进行矩阵乘法A_{left}A_{left+1}...A_{right-1}A_{right}所需要的乘法次数,为方便起见,设m_{left,left}=0.如果最后进行的乘法是(A_{left}...A_i)(A_{i+1}...A_{right}),其中left\leq i<right,那么需要的乘法次数是m_{left-1,i}+m_{i+1,right}+c_{left}c_ic_{right}.

我们定义M_{left,right}是A_{left}A_{left+1}...A_{right-1}A_{right}所需要乘法的最小次数,那么

M_{left,right}=min\left \{ M_{left,i}+M_{i+1,right}+c_{left-1}c_ic_{right} \right \}

 当所有子问题都达到最优解时,原问题也就达到了最优解,否则,若子问题是次优解,我们就可以使用最优解来代替它,从而使原问题达到最优解。

 矩阵最优乘法顺序代码:

#include #define MAX 4
#define inf 999999999int FindMinDP(int* c, int M[][MAX+1], int lastchange[][MAX+1], int n) {for (int i = 1; i <= n; i++) {M[i][i] = 0;//根据定义,将所有只有一个矩阵的乘法次数设置为0}for (int k = 1; k < n; k++) {//k用来控制left与right之间的距离for (int left = 1; left <= n - k; left++) {//left的范围int right = left + k;//right与left的关系由k控制M[left][right] = inf;//将M矩阵初始化,最开始的最小次数未知,所以定义为无穷大for (int i = left; i < right; i++) {//i就是定义中的iint ThisM = M[left][i] + M[i + 1][right] + c[left - 1] * c[i] * c[right];//计算该顺序下的次数if (ThisM < M[left][right]) {//如果该顺序下的次数要比之前得到的次数小,就进行更新M[left][right] = ThisM;lastchange[left][right] = i;//并记录从left到right之间最佳的划分}}}}return M[1][MAX];//M[1][MAX]就代表从第一个矩阵到最后一个矩阵的最小次数
}int main() {//建立列数组cint c[MAX+1] = { 50,10,40,30,5 };//建立M数组,有4个矩阵,并且下标从1开始,所以M矩阵为5*5int M[MAX+1][MAX+1] = { 0 };//建立一个能够保存括号位置的矩阵,记录每次M改变时的下标iint lastchange[MAX+1][MAX+1] = { 0 };int min = FindMinDP(c, M, lastchange, MAX);printf("这%d个矩阵乘法需要的最少次数为%d\n", MAX, min);return 0;
}

由于算法中使用了三个for循环,所以时间复杂度为O(N^3),这个时间复杂度虽然看起来不太理想,但是与最坏的矩阵乘法次数所消耗的时间比起来,这个算法所节省的时间就是可以接受的。

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...