第四章基本的算法策略

第四章基本的算法策略内容摘要：

,先取者胜 .以 A先取为例： 取数结果为： A 6,27,12,5,11=61 胜 B 16,6,9,6,2=39 上节 下节 但若选另一组数据： 16,27,7,12,9,2,11,6。 仍都用贪婪算法 ， 先取者 A败。 取数结果为： A 16,7,9,11=43 B 27,12,6,2=47 胜 其实 ， 若我们只能看到两边的数据 ， 则此题无论先取还是后取都无必胜的策略。 这时一般的策略是用 近似贪婪算法。 但若取数者能看到全部 2n个数 ， 则此问题可有一些简单的方法 ， 有的虽不能保证所取数的和是最大 ， 但确是一个先取者必胜的策略。 上节 下节 数学模型建立 ： N个数排成一行 ， 我们给这 N个数从左到右编号 ，依次为 1， 2， …， N， 因为 N为偶数 ， 又因为是我们先取数 ， 计算机后取数 ， 所以一开始我们既可以取到一个奇编号的数 （ 最左边编号为 1的数 ） 又可以取到一个偶编号的数 （ 最右边编号为 N的数 ）。 如果我们第一次取奇编号 （ 编号为 1） 的数 ， 则接着计算机只能取到偶编号 （ 编号为 2或 N） 的数； 如果我们第一次取偶编号 （ 编号为 N） 的数 ， 则接着计算机只能取到奇编号 （ 编号为 1或 N1） 的数； 即无论我们第一次是取奇编号的数还是取偶编号的数 ， 接着计算机只能取到另一种编号 （ 偶编号或奇编号 ） 的数。 这是对第一个回合的分析，显然对以后整个取数过程都适用。 也就是说，我们能够控制让计算机自始自终只取一种编号的数。 这样，我们只要比较奇编号数之和与偶编号数之和谁大，以决定最开始我们是取奇编号数还是偶编号数即可。 （如果奇编号数之和与偶编号数之和同样大，我们第一次可以任意取数，因为当两者所取数和相同时，先取者为胜。 算法设计 ：有了以上建立的高效数学模型，算法就很简单了，算法只需要分别计算一组数的奇数位和偶数位的数据之和，然后就先了取数者就可以确定必胜的取数方式了。 以下面一排数为例： 1 2 3 10 5 6 7 8 9 4 奇编号数之和为 25（ =1+3+5+7+9），小于偶编号数之和为 30（ =2+10+6+8+4）。 我们第一次取 4，以后，计算机取哪边的数我们就取哪边的数（如果计算机取 1，我们就取 2；如果计算机取9，我们就取 8）。 这样可以保证我们自始自终取到偶编号的数，而计算机自始自终取到奇编号的数。 main( ) {int i,s1,s2,data。 input(n)。 s1=0； s2=0。 for(i=1。 i=n。 i=i+1) {input( data)。 if (i mod 2=0) s2=s2+data。 else s1=s1+data。 if(s1s2) print(“first take left”)。 else print(“first take right”)。 这个例题又一次说明 ， 解决问题时数学模型的选择是非常重要的。 ： 从问题的某一个初始解出发逐步逼近给定的目标 ， 每一步都作一个不可回溯的决策 ,尽可能地求得最好的解。 当达到某算法中的某一步不需要再继续前进时 ， 算法停止。 上节 下节 关于贪婪策略讨论 ： 贪婪算法对问题只需考虑 当前局部信息 就要做出决策 ， 也就是说使用贪婪算法的前提是 “ 局部最优策略能导致产生全局最优解 ”。 该算法的适用范围较小 , 若应用不当 , 不能保证求得问题的最佳解。 一般情况下通过一些实际的数据例子 (当然要有一定的普遍性 ),就能从直观上就能判断一个问题是否可以用贪婪算法 ， 如本节的例 2。 更准确的方法是通过数学方法证明问题对贪婪策略的选用性。 上节 下节 ： 从问题的某一初始解出发； while能朝给定总目标前进一步 do。 利用可行的决策 ， 求出可行解的一个解元素。 由所有解元素组合成问题的一个可行解。 上节 下节 : 首先贪婪算法的原理是通过局部最优来达到全局最优 ,采用的是逐步构造最优解的方法。 在每个阶段 ， 都作出一个看上去最优的 （ 在一定的标准下 ） ， 决策一旦作出 ， 就不可再更改。 用贪婪算法只能解决 通过局部最优的策略能达到全局最优的问题。 因此一定要注意判断问题是否适合采用贪婪算法策略 ， 找到的解是否一定是问题的最优解。 上节 下节 在动态规划算法策略中 ， 体现在它的决策不是线性的而是全面考虑不同的情况分别进行决策 , 并通过多阶段决策来最终解决问题。 在各个阶段采取决策后 , 会不断决策出新的数据 ,直到找到最优解 .每次决策依赖于当前状态 , 又随即引起状态的转移。 一个决策序列就是在变化的状态中产生出来的 ，故有 “ 动态 ” 的含义。 所以 ， 这种多阶段决策最优化的解决问题的过程称为 动态规划。 上节 下节 动态规划 我们通过一个简单的例子来说明动态规划的多阶段决策与贪婪算法有什么区别。 【 例 1】 数塔问题 上节 下节 认识动态规划 【 例 1】 数塔问题 有形如图 411所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。 问题分析 算法设计 算法 小结 问题分析 这个问题用贪婪算法有可能会找不到真正的最大和。 以图 411为例就是如此。 用贪婪的策略，则路径和分别为： 9+15+8+9+10=51 （自上而下）， 19+2+10+12+9=52（自下而上）。 都得不到最优解，真正的最大和是： 9+12+10+18+10=59。 在知道数塔的全貌的前提下，可以用 枚举法 或下一章将学习的搜索算法来完成。 上节 下节 算法设计 动态规划设计过程如下： ： 第一步对于第五层的数据，我们做如下五次决策： 对经过第四层 2的路径选择第五层的 19， 对经过第四层 18的路径选择第五层的 10， 对经过第四层 9的路径也选择第五层的 10， 对经过第四层 5的路径选择第五层的 16。 上节 下节 以上的决策结果将五阶数塔问题变为 4阶子问题，递推 出第四层与第五层的和为 : 21(2+19),28(18+10),19(9+10),21(5+16)。 用同样的方法还可以将 4阶数塔问题 ,变为 3阶数塔问题。 …… 最后得到的 1阶数塔问题，就是整个问题的最优解。 上节 下节 2．存储、求解： 1) 原始信息存储 原始信息有层数和数塔中的数据，层数用一个整型 变量 n存储，数塔中的数据用二维数组 data，存储成如 下的下三角阵 : 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 上节 下节 2) 动态规划过程存储 必需用二维数组 a存储各阶段的决策结果。 二维数组 a的存储内容如下： d[n][j]=data[n][j] j=1,2,„„ ,n； i=n1,n2,„„ 1， j=1,2,„„ ,i；时 d[i][j]=max(d[i+1][j]， d[i+1][j+1])+data[i][j] 最后 a[1][1]存储的就是问题的结果。 上节 下节 3) 最优解路径求解及存储 仅有数组 data和数组 a可以找到最优解的路径， 但需要自顶向下比较数组 data和数组 a是可以找到。 如图 和输出过程如下： 上节 下节 输出 a[1][1]9 b=d[1][1]data[1][1]=599=50 b与 d[2][1],d[2][2] 比较 b与 d[2][1]相等输出 data[2][1]12 b=d[2][1]data[2][1]=5012=38 b与 d[3][1],d[3][2] 比较 b与 d[3][1]相等输出 data[3][1]10 b=a[3][1]data[3][1]=3810=28 b与 d[4][1],d[4][2] 比较 b与 d[4][2]相等输出 data[4][2]18 b=d[4][2]data[4][2]=2818=10 b与 d[5][2],d[5][3] 比较 b与 d[5][3]相等输出 data[5][3]10“ 上节 下节 数组 data 数组 d 9 59 12 15 50 49 10 6 8 38 34 29 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 10 4 16 图 412 数塔及动态规划过程数据 上节 下节 为了设计简洁的算法，我们最后用三维数组 a[50][50][3]存储以上确定的三个数组的信息。 a[50][50][1]代替数组 data， a[50][50][2]代替数组 d, a[50][50][3]记录解路径。 上节 下节 数塔问题的算法 main( ) { int a[50][50][3],i,j,n。 print( 39。 please input the number of rows:39。 )。 input(n)。 for( i=1。 i=n。 i++) for j=1 to i do { input(a[i][j][1])。