精华内容
下载资源
问答
  • 常见算法设计策略

    2019-05-10 15:49:00
    常见算法设计策略 1.分治 分治法的设计思想是,将一个难以直接解决的大问题,分割成k个规模较小的子问题,这些子问题相互独立,且与原问题相同,然后各个击破,分而治之。 分治法常常与递归结合使用:...

     常见的算法设计策略

    1.分治

          分治法的设计思想是,将一个难以直接解决的大问题,分割成k个规模较小的子问题,这些子问题相互独立,且与原问题相同,然后各个击破,分而治之。

          分治法常常与递归结合使用:通过反复应用分治,可以使子问题与原问题类型一致而规模不断缩小,最终使子问题缩小到很容易求出其解,由此自然导致递归算法。

          根据分治法的分割原则,应把原问题分割成多少个子问题才比较适宜?每个子问题是否规模相同或怎样才为适当?这些问题很难给与肯定的回答。但人们从大量实践中发现,在使用分治法时,最好均匀划分,且在很多问题中可以取k=2。这种使子问题规模大致相等的做法源自一种平衡子问题的思想,它几乎总是比使子问题规模不等的做法好。

     

    2.动态规划

          动态规划法与分治法类似,其基本思想也是将原问题分解成若干个子问题。与分治法不同的是,其分解出的子问题往往不是相互独立的。这种情况下若用分治法会对一些子问题进行多次求解,这显然是不必要的。动态规划法在求解过程中把所有已解决的子问题的答案保存起来,从而避免对子问题重复求解。

          动态规划常用于解决最优化问题。对一个最优化问题可否应用动态规划法,取决于该问题是否具有如下两个性质:

          1.最优子结构性质

          当问题的最优解包含其子问题的最优解时,称该问题具有最优子结构性质。

          要证明原问题具有最优子结构性质,通常采用反证法。假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在该假设下可构造出比原问题的最优解更好的解,从而导致矛盾。

          2.子问题重叠性质

          子问题重叠性质是指由原问题分解出的子问题不是相互独立的,存在重叠现象。

     

          用动态规划法解题过程中,应当先找出最优解的结构特征,即原问题的最优解与其子问题的最优解的关联。然后有如下两种程序设计方法:

           1.自底向上递归法

           利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。

           2.自顶向下递归法(即备忘录法)

           利用问题的最优子结构性质,用与直接递归法相同的控制结构自顶向下地进行递归求解。初始时在表格中为每个子问题存入一个标识解。在求解过程中,对每个待求子问题,首先查看表格中相应的记录项。若记录项为初始时的标识值,则表示该子问题是初次遇到,此时应利用问题的最优子结构性质进行递归求解,并将结果存入表格,以备以后查看。否则则说明该问题已被求解过,直接返回表格中相应的值即可,不必重新计算。

          当一个问题的所有子问题都要求解时,应当用自底向上递归法。当子问题空间中的部分子问题可不必求解时,自底向上递归法会进行多余的计算,此时应采用自顶向下递归法。

     

    3.贪心

          当一个问题具有最优子结构性质时,可用动态规划法求解。但有时会有比动态规划更简单更直接效率更高的算法——贪心法。贪心法总是做出在当前看来最好的选择,也就是说贪心法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优选择。虽然贪心法并不能对所有问题都得到整体最优解,但是对许多问题它能产生整体最优解。有些情况下,贪心法虽然不能得到整体最优解,但其最终结果却是最优解的很好的近似。

          贪心法常用于解决最优化问题。对一个最优化问题可否应用贪心法,取决于该问题是否具有如下两个性质:

          1.贪心选择性质

          贪心选择性质是指原问题总有一个整体最优解可通过当前的局部最优选择,即贪心选择来达到。

          对于一个具体问题,要确定它是否具有贪心选择性质,通常可考察问题的一个整体最优解,并证明可修改这个最优解,使其以贪心选择开始。由此证明该问题总有一个最优解可通过贪心选择得到,即具有贪心选择性质。

         2. 最优子结构性质

          这一点与动态规划相同。做出贪心选择后,由于最优子结构性质,原问题简化为规模更小的类似子问题。如果将子问题的最优解和之前所做的贪心选择合并,则可得到原问题的一个最优解。

     

          贪心问题的整体最优解可通过一系列局部的最优选择,即贪心选择来达到。这也是贪心法与动态规划的主要区别。在动态规划中,每一步所做出的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后,才能做出选择。而在贪心法中,仅做出当前状态下的最好选择,即局部最优选择。然后再去解做出这个选择之后产生的相应的子问题。贪心法所做出的贪心选择可以依赖于以往所做过的选择,但绝不依赖于将来所做的选择,也不依赖于子问题的解。正是由于这种差别,动态规划通常以自顶向上的方式解各子问题,而贪心法通常以自顶向下的方式进行,以迭代的方式做出相继的贪心选择,每做出一次贪心选择就将所求问题简化为规模更小的子问题。

         

    4.回溯

          回溯法是对问题的解空间树进行深度优先搜索 ,但是在对每个节点进行DFS之前,要先判断该节点是否有可能包含问题的解。如果肯定不包含,则跳过对以该节点为根的子树的搜索,逐层向其祖先节点回溯。如果有可能包含,则进入该子树,进行DFS。  

          回溯法通常的解题步骤如下:

         (1)定义问题的解空间。

         (2)将解空间组织成便于进行DFS的结构,通常采用树或图的形式。

         (3)对解空间进行DFS,并在搜索过程中用剪枝函数避免无效搜索。

          用回溯法解题时并不需要显式地存储整个解空间,而是在DFS过程中动态地产生问题的解空间。在任何时刻,算法只保存从根节点到当前节点的路径。如果解空间树的高度为h,则回溯法的空间复杂度通常为O(h) 

          用回溯法解题时,常会遇到以下两类典型的解空间树:

          (1)当所给的问题是从n个元素的集合S中找出S满足某种性质的子集时,相应的解空间树称为子集树。

          (2)当所给的问题是找出n个元素满足某种性质的排列时,相应的解空间树称为排列树。

          回溯法中的剪枝函数通常分为两类:

          (1)用约束函数在指定节点处剪去不满足约束的子树。

          (2)用限界函数在指定节点处剪去得不到最优解的子树。

     

    5.分支限界      

          回溯法是对解空间进行深度优先搜索,事实上任何搜索遍整个解空间的算法均可解决问题。所以采用通用图搜索(树可抽象为特殊的图)的任何实现作为搜索策略均可解决问题,只要做到穷举即可。除了深度优先搜索之外,我们还可采用广度优先搜索,而分支限界法则是对解空间进行优先级优先搜索。

          分支限界法的搜索策略是,在当前节点处,先生成其所有的子节点(分支),并为每个满足约束条件的子节点计算一个函数值(限界),再将满足约束条件的子节点全部加入解空间树的活结点优先队列。然后再从当前的活节点优先队列中选择优先级最大的节点(节点的优先级由其限界函数的值来确定) 作为新的当前节点。重复这一过程,直到到达一个叶节点为止。所到达的叶节点就是最优解。                                                                                                                                                                                                                                      

     
    分类:  算法

    转载于:https://www.cnblogs.com/superXIAOZHI/p/10844826.html

    展开全文
  • 算法设计与分析实验报告:递归与分治策略,用python写的,附源码。主要处理问题如下: 1.ackerman函数实现; 2.大数划分; 3. 数据集合{1,2,3,4,5,6,7,8,9,10}的排列组合;
  • 常用算法设计方法

    2018-04-13 08:55:36
    计算机程序要对问题的每个对象和处理规则给出正确详尽的描述,其中程序 的数据结构和变量用来描述问题的对象,程序结构、函数和语句用来描述问题的算法算法数据 结构是程序的两个重要方面。
  • 常用算法设计方法+搜集常用算法设计方法+搜集常用算法设计方法+搜集常用算法设计方法+搜集常用算法设计方法+搜集常用算法设计方法+搜集常用算法设计方法+搜集常用算法设计方法+搜集常用算法设计方法+搜集常用算法...
  • 算法设计是一件非常困难的工作,经常采用的算法设计技术主要迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和描述算法,在算法设计时又常常采用递归技术,用...
  • 常见算法设计方法

    千次阅读 2019-08-01 20:22:46
    然而,作为探寻问题求解思路的基本思想和方法,对于任何算法设计都是有用的。 1 穷举法 穷举法亦称作枚举法。它的基本思想是,首先根据求解问题的部分条件确定答案的大致范围,即列举出解的所有可能的情况;然后在...

    为了获得有效的算法,必须了解一些解体的基本思想和方法。对于很多问题,只要仔细分析了数据对象后,相应的处理方法就有了;对于有些问题则不然。然而,作为探寻问题求解思路的基本思想和方法,对于任何算法设计都是有用的。

    1 穷举法

    穷举法亦称作枚举法。它的基本思想是,首先根据求解问题的部分条件确定答案的大致范围,即列举出解的所有可能的情况;然后在此范围内对所有可能的情况逐一验证,若某个情况经过验证符合问题条件则为一个解,若全部情况验证后均不符合问题条件则问题无解,从而得出求解问题的完整解。
    例如,要找出200~500之间的所有素数,只要对这个范围内的每一个数逐个用素数的定义去判断就行了。
    穷举法的特点是算法简单,但是有时运算量大、效率较低。在可以确定解的取值范围,但一时又找不到更好的算法时,就可以使用穷举法求解。

    2 迭代法

    迭代法的基本思想是,由一个量的原值求出它的新值,不断地再用新值代替原值求出他的下一个新值,直到得到满意的解。新值和原值之间存在一定的关系,这种关系可以用一个公式来表示,称为迭代公式。
    迭代法主要用于那些很难用或者无法用解析法求解的一类计算问题,如高次方程和超越方程等,使得复杂问题的求解过程,转化为相对简单的迭代算式的重复执行过程,用数值方法求出问题的近似解。

    • 迭代求解算法的基本方法

    使用迭代法构造这一类问题求解算法的基本方法是,先确定一个收敛性能好(即收敛速度快)的迭代公式,选取解的一个近似值(即迭代初值)和解的精度要求(即允许的最大误差范围),然后用循环处理实现迭代过程,终止循环的条件是前后两次得到的近似值之差的绝对值小于解的精度要求,并认为最后一次得到的近似解为问题的解。这种方法称作逼近迭代,如著名的牛顿迭代法就是这种逼近迭代方法。
    此外,精度值的计算也可以使用迭代法。例如计算 s = 1 +2 +3 +…+1000,可选取迭代公式s +i ->s 和 迭代初值0(即0->s),当i分别取1,2,3…1000时重复计算迭代公式,最后一次便可以求出s的精确值。

    3 递推法

    递推法是从前面的一些量推出后面的一些量的一种方法,它从已知的初始条件出发,逐次推出所需要求解的各中间结果和最终结果。递推过程往往表现为迭代,即由一些量的原值推出他的新值,不断的用新值替代原值推出下一个新值,直到推出最终结果,新值和原值之间的关系用递推公式表示。
    例如Fibonacci数列存在递推关系:
    F(1) = 1, F(2) = 2, F(n) = F(n-1) + F(2) (n>=2)

    4 递归法

    如果一个过程直接或间接的调用它自身,则称该过程是递归的;直接调用自身称作直接递归,间接调用自身称作间接递归。递归是构造算法的一种基本方法,它将一个复杂问题归结为若干个较为简单的问题,然后将这些较为简单的问题进一步归结为更简单的问题,这个过程一直进行下去直到归结为最简单的问题时为止。这个最简单的问题即为递归终止条件,也称作递归出口。
    著名的汉诺(Hanoi)塔问题的求解算法就是递归法的典型运用。

    • 递归和递推是既有区别又有联系的两个概念
      递推是从已知初始条件出发逐次推出最后所求的值;而递归则是从函数本身出发,逐次上溯调用其本身求解过程直到递归出口,然后再从里向外倒推回来得到最终的值。
      一般来说,一个递推算法总可以转换为一个递归算法。对于同一问题所设计的递归算法往往要比相应的非递归算法(如递推算法)付出更多的执行时间代价和更多的辅助存储空间开销。

    5 回溯法

    回溯法是算法设计中的一种基本策略,回溯法是一种优选搜索法,又称为试探法,按优选条件向前搜索,以达到目标,但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术称为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
    在那些涉及寻找到一组解的问题或者满足某些约束条件的最优解的问题中,许多都可以使用回溯法求解。例如,在国际象棋棋盘上的骑士周游问题和走迷宫问题,都是使用回溯法进行的。

    • 基本思想
      在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。
      若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。
      而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。

    • 用回溯法解题的一般步骤
      (1)针对所给问题,确定问题的解空间:
      首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。
      (2)确定结点的扩展搜索规则
      (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

    6 贪婪法

    贪婪法又称贪心算法,它是通过一系列的选择来得到问题的一个解。贪婪法在每一步所做出的选择,都是在当前状态下看来是最好的选择即贪婪选择,并希望通过每次所作的贪婪选择导致最终结果是求解问题的一个最优解。换句话说,贪婪法并不从整体最优伤进行考虑,它做出的选择只是在某种意义上的局部最优选择,但希望算法得到的最终结果也是整体的。
    贪心算法不是对所有问题都能得到最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

    • 贪心算法的基本思路
      (1)建立数学模型来描述问题。
      (2)把求解的问题分成若干个子问题。
      (3)对每一子问题求解,得到子问题的局部最优解。
      (4)把子问题的解局部最优解合成原来解问题的一个解。

    7 分治法

    在计算机科学中,分治法是一种很重要的算法,字面上的解释是“分而治之”,就是在求解一个复杂问题时,尽可能的把这个问题分解成若干较小的子问题,在找出各个较小的问题的解之后再组合成为整个问题的解,这就是所谓的分治法。
    使用分治法时,往往要按问题的输入规模来衡量问题的大小,当要求解问题的输入贵哦相当大时,应选择适当策略将输入划分成若干子集合得到一组子问题,在求解出各子问题的解之后用适当的方法把他们合并成整个问题的解,分治法并应用成功。

    • 分治法的基本步骤
      (1) step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
      (2) step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
      (3)step3 合并:将各个子问题的解合并为原问题的解。
    • 可使用分治法求解的一些经典问题
      (1)二分搜索
      (2)大整数乘法
      (3)Strassen矩阵乘法
      (4)棋盘覆盖
      (5)合并排序
      (6)快速排序
      (7)线性时间选择
      (8)最接近点对问题
      (9)循环赛日程表
      (10)汉诺塔

    8 动态规划

    • 基本概念
      动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

    • 基本思想与策略
      基本思想与分治法类似,也是将待求解的问题分解成若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是原始问题的解。
      由于动态规划解决的问题有多重叠子问题这个特点,为减少重复计算,对每个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。

    • 与分治法最大的区别
      适合于动态规划求解的问题,经分解后得到的子问题往往不是互相独立的(即下一子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)

    • 适用的情况
      能采用动态规划求解的问题一般要具有三个性质:
      (1)最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
      (2)无后效性:即某一阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
      (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能多次被使用到。(该性质并不是动态规划的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

    展开全文
  • 在能力方面要求:通过本课程的学习,学生要掌握几种常用算法设计策略,包括递归与分治策略、动态规划算法、贪心算法、回溯法、分支限界法概率算法、线性规划和网络流法和NP完全性理论与近似算法等,并会分析算法的...
  • MPI 第五章 并行算法的一般设计策略 详细的查阅了有关资料,并自己做了一个易懂的ppt
  • 必做:n 用分治思想设计实现二分搜索、合并排序,并且用不同数据量进行实验对比分析。 选做:阶乘(递归与分治)。
  • 常用算法设计方法.pdf

    2020-06-26 14:30:50
    常用算法设计方法 常用算法设计方法 要使计算机能完成人们预定的工作首先必须为如何完成预定的工作设计一个算法然后再根据算法 编写程序计算机程序要对问题的每个对象和处理规则给出正确详尽的描述其中程序的数据...
  • 主要介绍了基于C++的农夫过河问题算法设计与实现方法,简单描述了农夫过河问题,并结合实例形式详细分析了基于C++实现农夫过河问题的相关算法实现步骤与操作技巧,需要的朋友可以参考下
  • 为便于区别,把算法学习的内容分成五个不同的方面:(一)何设计算法设计算法的工作是不可能完全自动化的。本书是要使读者学会已被实践证明是有用的一些基本设计策略。这些策略不仅在计算机科学,而且在运筹学、电气...

    要制定一个算法,一般要经过设计确认分析编码调试计时等阶段,因此学习计算机算法必须涉及这些方面的内容。在这些内容中有许多都是现今重要而活跃的研究领域。为便于区别,把算法学习的内容分成五个不同的方面:

    (一)何设计算法

    设计算法的工作是不可能完全自动化的。本书是要使读者学会已被实践证明是有用的一些基本设计策略。这些策略不仅在计算机科学,而且在运筹学、电气工程等多个领域都是非常有用的,利用它们已经设计出了很多精致有效的好算法。读者们一旦掌握了这些策略,也一定会设计出更多新的、有用的算法。

    (二)如何表示算法

    语言是交流思想的工具,设计的算法也要用语言恰当地表示出来。本书基本采用结构程序设计的方式,选择了一种名为SPARKS的程序设计语言来简单明了地表示算法。至于结构程序设计的内容本书并不打算具体介绍,而是将所能收集到的那些主要结构用于本书所给出的算法之中,只是在本章的最后一节详细讨论了一种非常重要的结构——递归。

    (三)如何确认算法

    一旦设计出了算法,就应证明它对所有可能的合法输入都能算出正确的答案,这一工作称为算法确认(algorithm validation)。要指出的是,用SPARKS所描述的算法还不足以是一个可以立即投入机器运行的程序。确认的目的在于使我们确信这一算法将能正确无误地工作,而与写出这一算法所用的程序语言无关。一旦证明了算法的正确性,就可将其写成程序,在将程序放到机器上运行之前,实际上还应证明程序是正确的,即证明程序对所有可能的合法输入都能得到正确的结果,这一工作称为程序证明(program proving)。这一领域是当前很多计算机科学工作者集中研究的对象,还处于相当初期的阶段。在这一领域的工作还没取得突破性的进展之前,为了增强对所编制程序的置信度,只能用对程序的测试来权宜代替。

    (四)如何分析算法

    在前面对有穷性的讨论中,曾提及只应把能在相当有穷步内终止的算法实际投入计算机运行。细心的读者可能当时就会觉得“相当”一词用得非常含糊,能否对有穷步给出一个数量界限呢?这实际上是我们要在这里回答的问题。执行一个算法,要使用计算机的中央处理器(CPU)完成各种运算,要用存储器来存放程序和数据。算法分析(analysis of algorithms)是对一个算法需要多少计算时间和存储空间作定量的分析。分析算法不仅可以预计所设计的算法能在什么样的环境中有效地运行,而且可以知道在最好、最坏和平均情况下执行得怎么样,还可以使读者对解决同一问题不同算法的有效性作出比较判断。关于算法分析更确切的表征将在下一节讨论。

    (五)如何测试程序

        测试程序实际上由调试和作时空分布图两部分组成。调试(debugging)程序是在抽象数据集上执行程序,以确定是否会产生错误的结果,若有,则修改程序。但是,这一工作正如著名计算机科学家迪伊克斯特拉(E.Dijkstra)所说的那样,“调试只能指出有错误,而不能指出它们不存在错误。”尽管如此,在程序正确性证明还没取得突破性进展的今天,调试仍是不可缺少且必须认真进行的一项重要工作。作时空分布图是用各种给定的数据执行调试认为是正确的程序,并测定为计算出结果所花去的时间和空间,以印证以前所作的分析是否正确和指出实现最优化的有效逻辑位置。

    来源:我是码农,转载请保留出处和链接!

    本文链接:http://www.54manong.com/?id=8

    '); (window.slotbydup = window.slotbydup || []).push({ id: "u3646208", container: s }); })();
    '); (window.slotbydup = window.slotbydup || []).push({ id: "u3646147", container: s }); })();
    展开全文
  • 计算机算法设计与分析主要包括:算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、随机化算法、线性规划与网络流、NP完全性理论与近似算法等。本资料详细地总结了其相关的算法,希望对大家能有所...
  • VI基本算法设计策略;基本策略;6.1分治法 ; 从而仅需3次乘法即可完成 ? 该算法即STARSSEN矩阵乘法的来源 ;2FFT?该变换的逆变换为 令 则上式可写为 其它的一个重要性质时域卷积对应于频域积 ;多项式的积 两个多项式的...
  • 全书以算法设计策略为知识单元,系统介绍计算机算法的设计方法与分析技巧。主要内容包括:算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、随机化算法、线性规划与网络流、NP完全性理论与近似...
  • 计算机常用算法设计方法.pdf
  • 常用算法设计方法sfa.doc
  • 本书以各种算法设计技术(如贪心法、分支策略、动态规划、网络流、近似算法、随机算法等)为主线来组织素材,突出了算法设计的思想和分析的基本原则,为从事实际问题的算法设计与分析工作提供了清晰的、整体的思路和...
  • 很适合学习数学建模的同学阅读,既各种常用算法matlab实现,讲得很详细。
  • 机械优化设计经典方法的几点算法改进,李春明,,通过在《机械优化设计》教学实践和科研实践中对各种经典优化方法的研究,提出一些经典优化方法的改进算法。针对迭代终止准则(点
  • 算法设计技巧与分析

    热门讨论 2016-04-26 21:49:18
    算法设计技巧与分析》涵盖了绝大多数算法设计中的一般技术,在表达每一种技术时,阐述它的应用背景,注意用与其他技术比较的方法说明它的特征,并提供大量实际问题的例子。《算法设计技巧与分析》同时也强调了对每...
  • 基本算法设计策略

    千次阅读 2016-03-31 16:16:15
    基本算法设计策略 贪心法 分治法 回溯法 分支限界法 随机化算法 动态规划 贪心法 求解问题最优解,将问题分解为若干步,每一步都取当前最优解,即局部最优解。 例子:N人过桥问题 分治法 求解问题唯一解,将问题...

    基本算法设计策略

    • 贪心法

    • 分治法

    • 回溯法

    • 分支限界法

    • 随机化算法

    • 动态规划


    贪心法

    求解问题最优解,将问题分解为若干步,每一步都取当前最优解,即局部最优解。
    例子:N人过桥问题

    分治法

    求解问题唯一解,将问题分解为小规模的子问题,子问题之间相互独立。
    例子:汉诺塔

    回溯法

    求解问题最优解或唯一解。
    就是深度优先搜索,常用递归实现。
    约数条件:有不可行解时,判断当前选择是否符合可行解。
    限界条件:在找最优解时,判断当前选择是否符合最优解。
    例子:连通图着色问题。

    分支限界法

    求解问题最优解或唯一解。
    活结点。
    例子:集装箱分配问题

    随机化算法

    随机化算法分类:

    (1)数值随机算法

    用于数值问题的求解,得到近似解。

    (2)蒙特卡洛算法

    计算数学中的一种计算方法,用于求问题的准确解,得到正确解的概率以来与时间。

    (3)拉斯维加斯算法

    与蒙特卡洛算法相似,但是绝不返回错误的解。

    (4)舍伍德算法

    在确定性算法中加入随机性来降低最坏情况出现的概率。

    随机化算法分类:

    (1)线性同余法
    (2)平方取中法
    (3)乘同余法
    (4)混合同余法

    例子:

    判断n是否为素数。
    相关定理:wilson定理、费马定理、二次探测定理。

    动态规划

    求解最优解。
    同分治法类似,只是动态规划保存了之前求得的所有子问题的解,以避免重复的计算。
    适用条件:

    (1)最优化原理(最优子结构)
    (2)无后向性
    (3)子问题的重叠性

    动态规划的根本目的是:解决冗余,利用空间复杂度减少时间复杂度。

    例子:师姐大赛胜率问题

    展开全文
  • 美国斯坦福大学计算机科学系C++编程课程多年以来成功使用的优秀教材,结构严谨,语言通俗精妙,编程实例和习题丰富精巧。
  • 由于我之前一直强调数据结构以及算法学习的重要性,所以就一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,...
  • 本书以各种算法设计技术(如贪心法、分支策略、动态规划、网络流、近似算法、随机算法等)为主线来组织素材,突出了算法设计的思想和分析的基本原则,为从事实际问题的算法设计与分析工作提供了清晰的、整体的思路和...
  • 该分类法站在通用问题求解策略的高度,对现有大多数算法准确分类,从而引领读者沿着一条清晰、一致、连贯的思路来探索算法设计与分析这一迷人领域。《算法设计与分析基础(第3版)》作为第3版,相对前版调整了多个章节...
  • 今天刚考完试,趁着有点回忆赶快记录下来,考的内容和之前的试题还是很大差别的,希望各位想投机取巧的同学还是要沉下心来复习,试卷内容在文档最下面。
  • 1、掌握搜索算法的基本设计思想与方法, 2、掌握 A*算法设计思想与方法, 3、熟练使用高级编程语言实现搜索算法, 4、利用实验测试给出的搜索算法的正确性。 寻路问题。以图 1 为例,输入一个方格表示的地图,要求...
  • 画H大字 图像处理算法的FPGA设计步骤及方法 以 Adaboost算法为例 画H大字 设计步骤 一顾感 算法研究 算法改进 算法模型向电路结构抽象转换 电路结构设计 功能模块划分 关键电路时序及模块间接口时序设计 具体电路...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 870,165
精华内容 348,066
关键字:

常用的算法设计策略有哪些