int lcs_len(char *a, char *b, int c[ ][ N])
{ int m=strlen(a), n=strlen(b), i,j;
for (i=0;i<=m;i++) c[i][0]=0;
for (i=0;i<=n;i++) c[0][i]=0;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
if (a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
return c[m][n];
}

char *buile_lcs(char s[ ],char *a, char *b)
{ int k, i=strlen(a), j=strlen(b);
k=lcs_len(a,b,c);
s[k]=’\0’;
while (k>0)
if (c[i][j]==c[i-1][j]) i--;
else if (c[i][j]==c[i][j-1]) j--;
else { s[--k]=a[i-1];
i--; j--;
}
return s;
}

void main()
{ printf (“Enter two string（<%d）!\n”,N);
scanf(“%s%s”,a,b);
printf(“LCS=%s\n”,build_lcs(str,a,b));
}
1、动态规划的适用条件
任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
（1）最优化原理（最优子结构性质）
最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

图2
例如图2中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。这可用反证法证明：假设有另一路径J’是B到C的最优路径，则A到C的路线取I和J’比I和J更优，矛盾。从而证明J’必是B到C的最优路径。
最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。根据最优化原理导出的动态规划基本方程是解决一切动态规划问题的基本方法。
（2）无后向性
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
（3）子问题的重叠性
动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。
所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。
2、动态规划的基本思想
前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的（即不包含公共的子子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
3、动态规划算法的基本步骤
设计一个标准的动态规划算法，通常可按以下几个步骤进行：
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
（4）写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。
一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：
标准动态规划的基本框架
1. 对fn+1(xn+1)初始化; {边界条件}
for k:=n downto 1 do
for 每一个xk∈Xk do
for 每一个uk∈Uk(xk) do
begin
5. fk(xk):=一个极值; {∞或－∞}
6. xk+1:=Tk(xk,uk); {状态转移方程}
7. t:=φ(fk+1(xk+1),vk(xk,uk)); {基本方程(9)式}
if t比fk(xk)更优 then fk(xk):=t; {计算fk(xk)的最优值}
end;
9. t:=一个极值; {∞或－∞}
for 每一个x1∈X1 do
11. if f1(x1)比t更优 then t:=f1(x1); {按照10式求出最优指标}
12. 输出t;
但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：
（1）分析最优解的性质，并刻划其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
（4）根据计算最优值时得到的信息，构造一个最优解。
步骤（1）～（3）是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省略，若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速地构造出一个最优解。

【问题】 凸多边形的最优三角剖分问题
问题描述：多边形是平

此新闻共有11页 上一页 1 2 3 4 5 6 7 8 9 10 11 下一页