动态规划加速原理.cpp

算法分析部分

/*
动态规划加速原理：
许多动态规划求解问题具有类似的递归计算式。
设w(i,j)属于R,1<=i<j<=n。且m(i,j)的递归计算式为：
m(i,i)=0,1<=i<=n
m(i,j) = w(i,j) + min{i<k<=j}{m(i,k-1)+m(k,j)},1<=i<j<=n
最优二叉搜索树问题的动态规划递归式是上述递归式的特殊情形/
*/
/*
O(n^3)的时间算法：

*/
void DynamicProgramming( int n, int **m, int **s, int **w )
{
	for( int i = 1; i <= n; ++i )
	{
		m[i][i] = 0;
		s[i][i] = 0;
	}

	for( int r = 1; r <= n; ++r )
	{
		for( int i = 1; i <= n - r; ++i )
		{
			int j = i + r;
			w[i][j] = weight(i,j);
			m[i][j] = m[i+1][j];
			s[i][j] = i;
			for( int k = i + 1; k < j; ++k )
			{
				int t = m[i][k] + m[k+1][j];
				if ( t <= m[i][j] )
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
			m[i][j] += w[i][j];
		}
	}
}

/*
算法需要O(n^3)计算时间和O(n^2)空间
*/

/*
四边不等式：
在上述计算m(i,j)的递归式中，当函数w(i,j)满足
w(i,j) + w(i',j') <= w(i',j) + w(i,j'),i<=i'<j<=j'
时，称w满足四边形不等式。

当函数w(i,j)满足w(i',j)<=w(i,j')，i<=i'<j<=j'时，称w关于区间包含关系单调。
对于满足四边形不等式的单调函数w，可推知由递归式定义的函数m(i,j)
也满足四边形不等式，即：
m(i,j) + m(i',j') <= m(i',j) + m(i,j'),i<=i'<j<=j'
这一性质可用数学归纳法证明。我们对四边形不等式中的“长度”l=j'-i应用数学归纳法
当i==i'或j==j'时，不等式显然成立。由此可知，当l<=1时，函数m满足四边形不等式。
下面分两种情形进行归纳证明：
情形1：i<i' = j<j
*/
/*
加速算法：
根据前面的讨论，当w是满足四边形不等式的单调函数时
，函数s(i,j)单调，从而：
min{i<k<=j}{m(i,k-1)+m(k,j)} 
= min{s(i,j-1)<=k<=s(i+1,j)}{m(i,k-1)+m(k,j)}
*/

void SpeedDynamicProgramming( int n, int **m, int **s, int **w )
{
	for( int i = 1; i <= n; ++i )
	{
		m[i][i] = 0;
		s[i][i] = 0;
	}
	for( int r = 1; r < n; ++r )
	{
		for( int i = 1; i <= n - r; ++i )
		{
			int j = i + r;
			int i1 = s[i][j-1] > i ? s[i][j-1] : i;
			int j1 = s[i+1][j] > i ? s[i+1][j] : j - 1;
			w[i][j] = weight(i,j);
			m[i][j] = m[i][i1] + m[i1+1][j];
			s[i][j] = i1;
			for( int k = i1 + 1; k <= j1; ++k )
			{
				int t = m[i][k] + m[k+1][j];
				if ( t <= m[i][j] )
				{
					m[i][j] = t;
					s[i][j] = k;
				}
				m[i][j] += w[i][j];
			}
		}
	}
}