算法设计技巧论述

算法设计技巧论述摘要：本文对几种经典算法设计技巧进行了分析和论述。包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法，系统的介绍了他们的原理、特点和算法设计的步骤，并对每一种算法进行了举例分析，对算法设计的发展趋势进行了展望。关键词：贪婪算法；分治算法；动态规划；随机化算法；回溯算法1刖曰随着科学技术的不断发展，算法设计变得越来越复杂，算法设计的研究受到人们越来越多的重视。特别是计算机技术的广泛应用，更促进了算法设计相关理论的研究与发展。2贪婪算法2.1基本概念概念：贪婪算法（又称贪心算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。2.2算法思想及算法实现步?2.2.1算法思想从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。2.2.2实现该算法的步骤：1、从问题的某一初始解出发；2、while能朝给定总目标前进一步do3、求出可行解的一个解元素；4、由所有解元素组合成问题的一个可行解;2.3贪婪算法的基本要素对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。2.3.1贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解决子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。2.3.2最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。2.4贪婪算法的不足及优势2.4.1贪婪算法的不足：1、不能保证求得的最后解是最佳的；2、不能用来求最大或最小解问题；3、只能求满足某些约束条件的可行解的范围。2.4.2贪婪算法的优势贪婪算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪婪算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪婪算法应该是最好的选择之一。2.5例题分析2.5.1背包问题题目要求：有一个背包，背包容量是M=150.有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品ABCDEFG重量35306050401025价值10403050354030算法分析：目标函数：£pi最大约束条件是装入的物品总重量不超过背包容量，既，讷＜=M(M=150)1、根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？2、每次选取挑选所占重量最小的物品装入是否能得到最优解？3、每次选取单位重量价值最大的物品，成为解决本题的策略。贪心算法是很常见的算法之一，这是由于它简单易行，构造贪心策略简单。但是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着整个问题的最优解一定是由在贪心策略中存在的子问题的最优解得来的。对于本例题中的3种贪心策略，都无法成立，即无法被证明，解释如下：1、贪心策略：选取价值最大者。反例：W=30物品ABC重量281212价值302020根据策略，首先选取物品A，接下来就无法选取了，可是，选取B、C则更好。2、贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。3、贪心策略：选取单位重量价值最大的物品。反例：W=30物品：ABC重量：282010价值：282010根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。比如，求最小生成树的Prim算法和Krushal算法都是漂亮的贪心算法。2.5.2均分纸牌问题题目要求：有N对纸牌，编号分别为1,2,...，n。每堆上有若干张，但纸牌总数必为n的倍数，可以在任一堆上取若干张纸牌，然后移动。纸牌的规则为：在编号为1上取纸牌，只能移动到编号为2的堆上；在编号为n的堆上取得纸牌，只能移动到编号为n-1的堆上；其他堆上取得纸牌，可以移动到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如：n=4,4堆纸牌分别为：①9②8③17④6移动三次可以达到目的：从③取4张牌放到④，再从③取三张放到②，取一张放到①。算法分析：设a[i]为第I堆纸牌的张数（0<=I<=n），v为均分后每堆纸牌的张数，s为最小移动次数。我们用贪心算法，按照从左到右的顺序移动纸牌。如第I堆的纸牌数不等于平均值，则移动一次（即s加1），分两种情况移动：1、若a[i]>v，则将a[i]-v张从第I堆移动到第I+1堆；2、若a[i]<v，则将v-a[i]张从第I+1堆移动到第I堆。为了设计的方便，我们把这两种情况统一看作是将a[i]-v从第I堆移动到第I+1堆，移动后有a[i]=v;a[I+1]=a[I+1]+a[i]-v在从第I+1堆取出纸牌补充第I堆的过程中可能回出现第I+1堆的纸牌小于零的情况。

贪婪算法均分纸牌流程图贪婪算法均分纸牌流程图如n=3,三堆指派数为1227，这时v=10,为了使第一堆为10,要从第二堆移9张到第一堆，而第二堆只有2张可以移，这是不是意味着刚才使用贪心法是错误的呢?我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张，第二堆剩下-7张，在从第三堆移动17张到第二堆，刚好三堆纸牌都是10，最后结果是对的，我们在移动过程中，只是改变了移动的顺序，而移动次数不便，因此此题使用贪心法可行的。3分治算法3.1基本概念概念：分治算法是指把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题即子问题的合并。题，再把子问题分成更小的子问题直到最后子问题可以简单的直3.2算法思想及算法实现步骤3.2.1分治算法的基本思想分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。3.2.2分治法解题的一般步骤分治法解题的一般步骤：1、分解，将要解决的问题划分成若干规模较小的同类问题；2、求解，当子问题划分得足够小时，用较简单的方法解决；3、合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。3.2.3算法设计模式它的一般的算法设计模式如下：Divide-and-conquer(P)1、if|P*02、thenreturn(ADHOc(P))3、将P分解为较小的子问题P1,P2,...,Pk4、fori—1tok5、doyiDivide-and-conquer(Pi)△递归解决Pi6、T-MERGE(y1,y2,...,yk)△合并子问题7、return(T)其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOc(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1,P2,...,Pk的相应的解y1,y2,...,yk合并为P的解。3.3分治算法的分治策略及复杂性分析3.3.1分治算法的分治策略当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案，或者是合并方案不明显，究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。3.3.2分治算法的复杂性分析从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，分治法的计算效率通常可以用递归方程来进行分析。为方便起见，设分解阈值n0=1，且算法ADHOC解规模为1的问题耗费1个单位时间。又设分治法将规模为n的问题分成k个规模为n/m的子问题去解，而且，将原问题分解为k个子问题以及用算法MERGE将k个子问题的解合并为原问题的解需用f(n)个单位时间。如果用T(n)表示该分治法Divide-and-conquer(P)解规模为|P|=n的问题P所需的计算时间，则有：1、T(1)=1T(n)=kT(n/m)+f(n)用算法的复杂性中递归方程解的渐进阶的解法介绍的解递归方程的迭代法，可以求得(1)的解：logm(n-1)2、T(n)=n"(logmK)+E(k"j)*f(n/(m"j))j=0注意，递归方程⑴及其解⑵只给出n等于m的方幕时T(n)的值，但是如果认为T(n)足够平滑，那么由等于m的方幕时T(n)的值可以估计T(n)的增长速度。通常，我们可以假定T(n)是单调上升的，从而当mi^nn0由于我们关心的一般是最坏情况下的计算时间复杂度的上界，所以用等于号（=）还是小于或等于号（忍）是没有本质区别的分治法的几种变形。3.4例题分析3.4.1找出伪币题目要求：给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。解决方案一：比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。解决方案二：利用分而治之方法。假如把16硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把16个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先16个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这16个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。现在假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，16硬币的问题就被分为两个8硬币皿组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。分治算法解决伪币流程图3.4.2金块问题题目要求：有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。解决方案一：假设袋中有n个金块。可以用函数Max思想通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。解决方案二：分而治之法。当n很小时，比如说，n^2,识别出最重和最轻的金块，一次比较就足够了。当n较大时（n>2），第一步，把这袋金块平分成两个小袋A和&第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA与LA，以此类推，B中最重和最轻的金块分别为HB和LB。第三步，通过比较HA和HB，可以找到所有金块中最重的；通过比较LA和LB，可以找到所有金块中最轻的。在第二步中，若n>2，则递归地应用分而治之方法。（开始:平均分堆—H<5=0>是丫否1FHi]分别分堆输出最小金块序号找到重量与其他堆1不同的金块堆H[i]（_结束）T—n取半值分治算法查找金块假设n=8。这个袋子被平分为各有4个金块的两个袋子A和B。为了在A中找出最重和最轻的金块，A中的4个金块被分成两组A1和A2。每一组有两个金块，可以用一次比较在A中找出较重的金块HA1和较轻的金块LA1。经过另外一次比较，又能找出HA2和LA2。现在通过比较HA1和HA2，能找出HA；通过LA1和LA2的比较找出LA。这样，通过4次比较可以找到HA和LA。同样需要另外4次比较来确定HB和LB。通过比较HA和HB（LA和LB），就能找出所有金块中最重和最轻的。因此，当n=8时，这种分而治之的方法需要10次比较。设c(n)为使用分而治之方法所需要的比较次数。为了简便，假设n是2的幕。当n=2时，c(n)=1。对于较大的n，c(n)=2c(n/2)+2。当n是2的幕时，使用迭代方法可知c(n)=3n/2-2。在本例中，使用分而治之方法比逐个比较的方法少用了25%的比较次数。4动态规划4.1基本概念概念：动态规划是指，每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策问题的过程就称为动态规划。4.2动态规划的基本思想及算法实现步骤4.2.1动态规划的基本思想动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。4.2.2动态规划实现基本步骤动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线（通常是求最优的活动路线）。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。初始状态f|决策1|f|决策2|f|决策n|f结束状态图1动态规划决策过程示意图1、划分阶段：按照问题的时间或空间特征，把问题分为若十个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。2、确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。3、确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。4、寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。实际应用中可以按以下几个简化的步骤进行设计：1、分析最优解的性质，并刻画其结构特征。2、递归的定义最优解。3、以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值4、根据计算最优值时得到的信息，构造问题的最优解4.3算法的适用情况及算法实现的说明4.3.1适用情况能采用动态规划求解的问题的一般要具有3个性质:1、最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。2、无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。3、有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势)。4.3.2算法实现的说明动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。使用动态规划求解问题，最重要的就是确定动态规划三要素：1、问题的阶段2、每个阶段的状态3、从前一个阶段转化到后一个阶段之间的递推关系。递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径，最长公共子序列，最大价值等)，填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。f(n,m)=max(f(n-1,m),f(n-1,m-w[n])+P(n,m)}4.4动态规划的优越性与缺点4.4.1动态规划的优越性k能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为一系列结构相似的子问题，每个子间题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。2、可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。3、能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解率。比如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速度。4.4.2动态规划的主要缺点1、没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的具体准则(大部分情况只能够凭经验判断是否适用动态规划)。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。2、用数值方法求解时存在维数灾(curseofdimensionality)o若一维状态变量有m个取值，那么对于n维问题，状态xk就有mn个值，对于每个状态值都要计算、存储函数fk(xk)，对于n稍大(即使n=3)的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。4.5例题分析[经典例题]背包问题题目要求：从n个物品中选取装入背包的物品，每件物品i的重量为wi,价值为pi。求使物品价值最高的选取方法。题目分析：初看这类问题，第一个想到的会是贪心，但是贪心法却无法保证一定能得到最优解，看以下实例：贪心准则1：从剩余的物品中，选出可以装入背包的价值最大的物品。利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2,w=[100,10,10],p=[20,15,15],c=105°（c为背包容量，n为物品数量）当利用价值贪婪准则时，获得的解为x=[1，0，0]，这种方案的总价值为20。而最优解为[0，1，1]，其总价值为30。贪心准则2：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n=2,w=[10,20],p=[5,100],c=25。当利用重量贪婪策略时，获得的解为x=[1,0],比最优解[0,1]要差。贪心准则3：价值密度pi/wi贪婪算法，这种选择准则为：从剩余物品中选择可装入包的pi/wi值最大的物品，但是这种策略也不能保证得到最优解。利用此策略n=3,w=[20,15,15],p=[40,25,25],c=30时的得到的就不是最优解。由以上的三种贪心策略可知，本题如果采用贪心方法求解，则完全取决于输入的数据，不管采用哪种方法都不能保证完全正确。要使物品价值最高，即p1*x1+p2*x1+...+pi*xi（其1<=i<=n，x取0或1，取1表示选取物品i）取得最大值。在该问题中需要决定x1...xn的值。假设按i=1，2，...n的次序来确定xi的值。如果置x1=0，则问题转变为相对于其余物品（即物品2,3,.，n），背包容量仍为c的背包问题。若置x1=1，问题就变为关于最大背包容量为C-W1的问题。现设r={c,C-W1}为剩余的背包容量。在第一次决策之后，剩下的问题便是考虑背包容量为r时的决策。不管x1是0或是[x2,.,xn]必须是第一次决策之后的一个最优方案。也就是说在此问题中，最优决策序列由最优决策子序列组成。这样就满足了动态规划的程序设计条件。动态规划思路：阶段i：在前i件物品中，选取若干件物品放入背包中；状态：在前i件物品中，选取若干件物品放入所剩空间为c的背包中的所能获得的最大价值；决策：第i件物品放或者不放；由此可以写出动态转移方程：用f[i,j]表示在前i件物品中选择若干件放在所剩空间为j的背包里所能获得的最大价值f[i,j]=max{f[i-1,j-wi]+pi(j>=wi),f[i-1,j]}这样，就可以自底向上地得出在前n件物品中取出若干件放进背包能获得的最大价值，也就是f[n,c]。5随机化算法5.1随机化算法的基本概述随机化算法是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。随机化算法基于随机方法，依赖于概率大小。这种算法看上去是凭着运气做事，其实，随机化算法是有一定的理论基础的，我们可以想象，在[1,10000]这个闭区间里，随机1000次，随机到2这个数的几率是多大(约为0.001)，何况1000次的随机在计算机程序中仅仅是一眨眼的功夫。可以看出，随机化算法有着广阔的前景。只是由于随机化算法比较难于掌控，所以并不是很多人都接触过他，但肯定有很多人都听说过。5.2随机化算法的基本原理及类别随机化算法的基本原理是:当某个决策中有多个选择，但又无法确定哪个是好的选择，或确定好的选择需要付出较大的代价时，如果大多数选择是好的，那么随机地选一个往往是一种有效的策略。通常当一个算法需要作出多个决策，或需要多次执行一个算法时，这一点表现得尤为明显。这个原理使得随机化算法有一个共同的性质:没有一个特别的输人会使算法执行出现最坏情况。实际算法设计时，随机化算法可大致分为如下四方面：1、在判定性问题中，如果待检查的状态非常之多，那么.可以考虑进行随机抽样，或者是考虑一个“不怎么对”的算法〔假设其正确率为p<100%）。那么如果将这个算法执行很多遍（设为k），那么其整体误判率为（1p）&，当k递增时，整体误判率就会趋近于零。这类算法被称作Monte-Carl算法。例如:一个判断算法，它有50%的几率将正确结果判成错误，但是错误一定能判断出来，那么当此算法运行10次，整体的误判率大约为0.1%。这样做的好处在于如果能找到一个时间复杂度的阶小于原算法的非完全正确算法，就可以将时间复杂度的阶降下来。比如上面的算法，如果运行20次，那么误判率将达到百万分之一的地步，但是时间复杂度只不过乘上一个20的常数。当问题规模很大的时候，用一点点的正确率去换大量的时间在实际应用上是非常值得的。事实上，以这种方式换取代码的简便甚至是降低思维难度都是不错的应用。但是值得注意的是，这个算法毕竟不是100%正确的。2、当一类算法对于数据的处理顺序敏感，并在极端情况下会令算法达到一个难以让人接受的时间复杂度下界，那么可以通过随机打乱数据的排列来使得算法尽量避免极端情况，从而使算法得到期望下的运行时间。这类算法被称Shersood算法。一个最好的例子便是快速排序。当给定待排序数组是有序的时候，最原始的快速排序会因为划分不均而退化到0（n2），那么这就失去了快速排序的意义了。常用的方法就是随机打乱数组的排列，或者更简单的，在取分割点的时候随机一个数组下标。当然这会牵扯出一个问题，就是随机的时候如果出现”运气不好”的情况怎么办?可以直观的想:是把一个普通的情况随机成极端情况几率大?还是把极端情况随机到普通情况大?这个是一目了然的。而且经验主义的看法认为:在统计情况下产生极端情况（如快速排序中的待排序列为有序序列）的概率是非常小的，这种情况通常都是利用算法特点被人为地特殊构造出来的。3、当一类问题的解很丰富，并且只要求一个任意解的时候（或者可以理解为不考虑解的优劣性），那么可在中间步骤作决策的时候干脆“猜”上一个来碰碰运气。尽管事前并不知道这个猜测会带来什么样的结果，但是这样至少省去了检查全部可能性的麻烦，况且可能状态的总数也许是一个天文数字，这对只要找一组解的任务来说无疑是代价太大了。这类算法被称作LasVegas算法。一个经典例子是随机n皇后问题。当n很大时，搜索无法胜任，那么可以考虑每一行乱放一个位置，这样有一定概率得到解，至少比搜索得不到解要来的好。要注意的是，这类算法很有可能找不到任何结果。所以可以考虑作如下改进:在算法里进行控制使得在允许期望时间内程序猜许多次，或者加人一些估价方法，让程序尽量去“猜”那些“看上去”能找到解的决策（注意，不一定是最优值，否则就退化成贪心了）。4、在部分数值计算问题中，由于精确解难以直接求得，通常采用一些概率方法来逼近要求的答案，利用计算机计算量大的特点来获得一定精度下的答案。这类算法被称为数值概率算法。例如用投点法计算圆周率:作一个2*2的正方形并作出其内接圆，然后在这个正方形内各处等概率投点。那么由于落下点概率与面积成正比，所以在圆内的点数除以总点数再乘以正方形的面积4就能得到圆周率的一个近似值。这种算法的最大特点是运行时间越长，理论上就能得到越精确的值。换句话说，如果能随机投无穷多个点，理论上就能得到精确的Pi值。但是话说回来，这毕竟是一种逼近算法，只是用于计算一些比较扭曲且精度要求不高的式子，对于要求精确的一些数值和公式还是得通过数学分析的方式来进行计算。但是在计算某些不规则的数值的时候还是能起到奇效的。5.3例题分析及应用5.3.1字符串问题题目要求：一个长度在4..10的字符串中，需要判定是否可以在字符串中删去若干字符，使得改变后字符串符合以下条件之一：（1）AAAA；（2）AABB；（3）ABAB；（4）ABBA

“D”两个字母，例如：长度为6字符串"POPKDK”，若删除其中的“O”，则原串变为：“PPKK”，符合条件(2)“D”两个字母，题目分析：这道题很容易想到一种算法：运用排列组合：枚举每4个字母，然后逐一判断。算法是可行的，但是如果需要题目中加上一句话：需要判断n个字符串，且n<=100000，那么这样的耗时是不能让人忍受①的，因为在枚举的过程中，是非常浪费时间的。(①：这里是指信息学中要求算法的普遍运算时间为：1000ms)所以这道题有可能可以借助于随机化算法，下面我们来算一下在10个字符中取4个字符一共有多少种取法：C(4,10)=210。那么很容易得知，随机化算法如果随机300次，能得到的结果基本上就正确了(概率为1-(209/210)^300，约为0.76)，而随机时的时间消耗是O(1)，只需要判断没有随机重复即可，判重的时间复杂度也为O(1)，并且最多随机300次，这样就可以有效地得到答案，最大运算次数为：O(300n)，这是在计算机的承受范围内(1000ms)的。随机算法流程图随机算法流程图从这里就能看出，随机化算法是一个很好的概率算法，但是它并不能保证正确，而且它单独使用的情况很少，大部分是与其他的算法：例如贪心、搜索等配合起来运用。5.3.2排序问题快速排序是排序方法中较为便捷的方法之一，但是由于它极不稳定，最好的时候时间复杂度为O(nlogn)，这里的log是指以2为底的对数运算。最坏的时候能达到与普通排序方法一样的O(n”2)。而制约快速排序的有两个：一是数据，越无序的数据，快排的速度越快；二是中间点的枚举。因为两个制约条件都与随机有着不可分开的关系。所以，在快速排序中加入随机化算法无疑是十分重要的。运用在：1、数据读入时，随机排放数据位置。2、中间点的枚举进行多次随机化后决定。这样就基本上将快速排序的时间复杂度维持在最好状态。6回溯算法6.1回溯算法的基本概念概念：回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。6.2回溯算法的算法思想及算法步骤6.2.1回溯算法的基本思想同溯算法是算法设计的基木方法之一，其主要思想是:不断地用修改过的规范函数V;}x;,x}}...，x;)}称限界函数)去测试止在构造中的n元组的部分量(}x;,x}}..}x;)，看其是否可能导致最优解，如果判定(x,,x},}',x;)不可能导致最优解，那么就将可能要测试的x;.;,x;十2,…,x.,个向量一概略去，因此，同溯算法作的测试次数要少的多。6.2.2回溯算法的算法步骤用回溯算法解决问题的一般步骤为：1、定义一个解空间，它包含问题的解。2、利用适于搜索的方法组织解空间。3、利用深度优先法搜索解空间。4、利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。6.3回溯算法的一般问题描述及解决方法6.3.1回溯算法的一般问题描述可用回溯法求解的问题P，通常要能表达为:对于已知的由n元组（x1，x2,…，xn）组成的一个状态空间E=（（x1，x2，…，xn）|x^Si，i=1，2，…，n｝，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。中Si是分量xi的定义域，且|Si|有限，i=1，2，„，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（j<i）元组（x1，x2，…，xj）一定也满足D中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。换句话说，只要存在0忍j忍n-1，使得（x1，x2，…，xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2,…，xi的一个约束，nNi>j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（xl,x2,…，xj）违反D中仅涉及（xl,x2,…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（xl，x2,…，xj，xj+1，…，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。6.3.2回溯算法的解题思路回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造：设Si中的元素可排成xi（1），xi（2），…，xi（mi-l），|Si|二mi，i=1，2，…，n。从根开始，让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1（1），xi+1（2），…，xi+1（mi），i=0，1，2，…，n-1。照这种构造方式，E中的一个n元组（x1，x2，…，xn）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x1，x2，…，xn，反之亦然。另外，对于任意的0织住n-1，E中n元组（x1，x2，…，xn）的一个前缀I元组（x1，x2，…，xi）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2,…，乂^反之亦然。特别，E中的任意一个n元组的空前缀（），对应于T的根。因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根叶子结点的路径上依次的n条边相应带的n个权x1,x2,…，xn满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1,x2）、…，前缀I元组（x1,x2,…，xi）,…，直到i=n为止。在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。对于具有完备约束集D的一般问题P及其相应的状态空间树T,利用T的层次结构和D的完备性，在T中搜索问题P的所有解的回溯法可以形象地描述为：从T的根出发，按深度优先的策略，系统地搜索以其为根的子树中可能包含着回答结点的所有状态结点，而跳过对肯定不含回答结点的所有子树的搜索，以提高搜索效率。具体地说，当搜索按深度优先策略到达一个满足D中所有有关约束的状态结点时，即“激活”该状态结点，以便继续往深层搜索；否则跳过对以该状态结点为根的子树的搜索，而一边逐层地向该状态结点的祖先结点回溯，一边“杀死”其儿子结点已被搜索遍的祖先结点，直到遇到其儿子结点未被搜索遍的祖先结点，即转向其未被搜索的一个儿子结点继续搜索。在搜索过程中，只要所激活的状态结点又满足终结条件，那么它就是回答结点，应该把它输出或保存。由于在回溯法求解问题时，一般要求出问题的所有解，因此在得到回答结点后，同时也要进行回溯，以便得到问题的其他解，直至回溯到T的根且根的所有儿子结点均已被搜索过为止。6.4例题分析6.4.1组合问题问题描述：找出从自然数1，2,…，n中任取r个数的所有组合。问题分析：采用回溯法找问题的解，将找到的组合以从小到大顺序存于a[0]，a[1]，…，a[r-1]中，组合的元素满足以下性质：1、a[i+1]>a[i]，后一个数字比前一个大；2、a[i]-i<=n-r+1o按回溯法的思想，找解过程可以叙述如下：首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件1，候选组合改为1，2。继续这一过程，得到候选组合1，2,3。该候选解满足包括问题规模在内的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因a[2]上的3调整4，以及以后调整为5都满足问题的全部要求，得到解1，2,4和1，2,5。由于对5不能再作调整，就要从a[2]回溯到a[1]，这时，a[1]=2,可以调整为3,并向前试探，得到解1,3,4。重复上述向前试探和向后回溯，直至要从a[0]再回溯时，说明已经找完问题的全部解。回溯法解决组合问题6.4.2填字游戏问题描述：在3X3个方格的方阵中要填入数字1到N(NN10)内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。问题分析：可用试探发找到问题的解，即从第一个方格开始，为当前方格寻找一个合理的整数填入，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填证书，就要回退到前一方格，调整前一方格的填入数。当第九个方格也填入合理的整数后，就找到了一个解，将该解输出，并调整第九个的填入的整数，寻找下一个解。为找到一个满足要求的9个数的填法，从还未填一个数开始，按