精华内容
下载资源
问答
  • 算法设计

    千次阅读 2010-01-06 16:09:00
    算法设计与分析”1、 什么是算法?算法有哪些基本特征?请指出算法同程序的相同点与不同点。(课件之“绪论”,教材之“绪论”,page:1)答:算法是解决问题的方法或过程,是满足以下四个性质的指令序列 1)输入...

    “算法设计与分析”

    1、 什么是算法?算法有哪些基本特征?请指出算法同程序的相同点与不同点。(课件之“绪论”,教材之“绪论”,page:1)

    答:算法是解决问题的方法或过程,是满足以下四个性质的指令序列

        1)输入:有0个以上的输入

    2)输出:至少有1个输出

    3)确定性:指令清晰、无歧义

    4)有限性:指令执行次数有限,时间有限

    算法和程序的相同点:两者都具有输入、输出和确定性的特征

    不同点:程序是算法用某种程序语言的具体实现,程序不满足算法具有的有限性性质

    2、 请描述算法设计的一般过程。(课件之“绪论”)

    答:算法设计的一般过程是

    1)提出问题

    2)确定数学模型

    3)明确目的、条件和约束关系

    4)设计求解步骤

    5)结果评估与分析

    如果在第5步的分析中对算法时间、空间复杂度或结果不满意,可以返回第1步或第4步进一步迭代,直至找到满意的算法。


     

    3、 什么是算法复杂性?它主要有哪两个方面构成?(课件之“绪论”)

    答:算法复杂性是算法运行时所需要的计算机资源的量,它包括两个方面:时间复杂性(需要时间资源的量)和空间复杂性(需要空间资源的量)。

    4、 时间复杂性分析主要分哪三种情况,哪种情况的可操作性最好,最具有实际价值?(课件之“绪论”)

    答:时间复杂性分为3种情况,最好情况、平均情况、最坏情况,可操作性最好,最具有实际价值的是最坏情况下的时间复杂性

    5、 如果算法A由三个步骤组成,其中第一步的时间复杂性为O(n2),第二步的时间复杂性为O(nlogn),第三步的时间复杂性为O(n),请问算法A的时间复杂性是多少?(教材之“绪论”,page:15)

    答:O(n2)

    6、 请问二分搜索算法、快速排序算法、线性时间选择算法和最近点对问题的时间复杂性各为多少?(教材之“递归与分治”,page:27,37,39,43)

    答:二分搜索算法:最坏情况O(logn)、

    快速排序算法:最坏情况O(n2),最好情况和平均情况均为O(nlogn)

    线性时间选择算法:最坏情况O(n)

    最近点对问题:时间复杂性O(nlogn)

    7、 分治算法和动态规划算法都是通过对问题进行分解,通过对子问题的求解然后进行解重构,从而实现对原问题的求解。请指出这两种算法在对问题进行分解时各自所遵循的原则。(课件之“递归与分治”,课件之“动态规划”)

    答:分治算法对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互独立且与原问题相同的子问题(不包含公共的子问题)。

    动态规划对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互关联的与原问题类似的子问题(包含公共的子问题),采用记录表的方法来保存所有已解决问题的答案,而在需要的时候再找出已求得的答案,避免大量的重复计算。

    8、 动态规划算法的本质是什么,请简要阐述。(课件之“动态规划”)

    答:动态规划的实质是分治思想和解决冗余,动态规划算法是将问题分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。

    9、 如果一个问题可以利用动态规划算法求解,那么该问题应满足什么条件?(教材之“动态规划”,page:67)

    答:该问题具有最优子结构性质(一个问题的最优解包含其子问题的最优解)和子问题重叠性质(每次递归产生的子问题不总是新问题,有些子问题被反复计算多次)

    10、动态规划算法的基本思想是什么?请简述动态规划算法主要设计步骤。(教材之“动态规划”,page:61)

    答:动态规划算法的基本思想是将待求解问题分解成若干个相互关联的与原问题类似的子问题,求解这些子问题,并保存子问题的答案,避免重复计算,然后从这些子问题的解得到原问题的解。

    动态规划算法主要设计步骤:

    1)找出最优解的性质,并刻画其结构特征;

    2)递归地定义最优值;

    3)以自底向上的方式计算出最优值;

    4)根据计算最优值时得到的信息,构造最优解;

    11、什么是备忘录方法?它同动态规划法相比主要不同点是什么?请指出动态规划法和备忘录方法各自的适用范围。(课件之“动态规划”)

    答:备忘录方法是动态规划算法的变形,它通过分治思想对原问题进行分解,以存储子问题的解的方式解决冗余计算,并采用自顶向下的递归方式获取问题的最终解。

    与动态规划算法的不同之处是动态规划算法的递归方式是自底向上递归求解,而备忘录方法的递归方式是自顶向下递归求解。

    当一个问题的所有子问题都至少要解一次时,使用动态规划算法。

    当子问题空间中的部分子问题不需要求解时,使用备忘录方法。

    12、贪心算法的设计思想是什么,有什么特点?如果一个问题用贪心算法可以获得全局最优解,那么该问题的求解应满足哪些条件?(课件之“贪心算法”,教材之“贪心策略”,page110)

    答:贪心算法的设计思想是在对问题求解时,总是做出在当前看来是最好的选择。

    它的特点是1)不是从整体考虑——得到的解可能不是全局最优 2)简单,直接,易理解,效率高。

    如使用贪心算法求解问题获得全局最优解,则问题应满足

    1)贪心选择性质(与动态规划的主要区别)

    所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选择)来达到

    2)最优子结构性质(动态规划算法和贪心算法的共同点)

    一个问题的最优解包含其子问题的最优解时。

    13、请简要描述回溯法的实现过程。用回溯法求解0/1背包问题、TSP问题、N皇后问题和连续邮资问题时,其各自的解空间树各是什么形式?(课件之“回溯法”,教材之“回溯法”page147)

    答:实现过程:确定解空间的组织结构,然后从开始结点(根结点)出发,以深度优先方式搜索整个解空间。这个开始结点成为活结点,同时也成为当前的扩展结点。

    在当前扩展结点处,搜索向纵深方向移至一个新结点。这个新结点成为新的活结点,并成为扩展结点。否则如果在当前扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时,应往回移动(回溯)到最近的活结点处,并使该结点成为当前的扩展结点。

    回溯法按上述方式递归地在解空间中搜索,直到找到所要求的解或解空间中以无活结点为止。

    0/1背包:n+1层的子集树  TSP问题:(n-1)!个叶节点的排列树

    N皇后问题:完全n叉树    连续邮资问题:n层树,其中结点的度随着本结点取值范围而变化的树??

    14、影响回溯法效率的主要因素有哪些?如何有效地估算回溯法在求解具体实例时产生的中间节点数量?(课件之“回溯法”,教材之“回溯法”page187,188)

    答:影响回溯法效率的主要因素

    1)产生x[k]的时间

    2)满足显约束的x[k]值的个数

    3)计算约束函数constrain的时间

    4)计算上界函数bound的时间

    5)满足约束函数和上界函数约束的所有x[k]的个数

    采用概率方法可以有效地估算回溯法在求解具体实例时产生的中间节点数量:

    (即在解空间树上产生一条随机路径,然后沿该路径估算解空间中满足约束条件的节点数m,由于使用静态约束函数,在某些情况下产生的估计较为保守。因此还可以多选取几条不同的路径,分别计算m,然后平均,这样的估算结果会更准确些。)

    15、请简述分支限界法的算法思想以及两种主要的实现方法。(课件之“分支限界法”,教材之“分支限界法”page195,196)

    答:分支限界法的算法思想是在问题的解空间树上以广度优先或最小耗费(最大效益)优先方式搜索问题的满足约束条件的一个解或最优解。(搜索策略:每一个活结点只有一次机会成为扩展结点。扩展结点一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。此后,从活结点表中按一定的策略取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。)

    分支限界法根据从活结点表中选择下一个扩展结点的方式有两种实现方法

    1)队列式FIFO分支限界法:按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。 

    2)优先队列式分支限界法:按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

    (最大优先队列:使用最大堆,体现最大效益优先

    最小优先队列:使用最小堆,体现最小费用优先)

    16、请指出回溯法与分支限界法的相同点与不同点。(课件之“分支限界法”)

    答:相同点:

    1)两者在进行问题求解前,都需要完成解空间的定义和组织;

    2)都是通过在解空间树上搜索来寻找问题的解;

    不同点:

    1)搜索方式

    回溯法:深度优先;

    分支限界法:广度优先;

    2)搜索策略

    回溯法:根据剪枝函数,选择下一个扩展接点并按深度优先方式进行搜索;

    分支限界法:在扩展结点处,先产生其所有的子结点(分支),然后根据限界函数,确定哪些子结点将导致不可行解或非最优解,将这些子结点剔除,用剩下的子结点构造当前的活结点表,然后从该表中取一个结点作为当前扩展结点,并重复上述过程;

    17、概率算法主要有哪些类型?它们各自的主要特点是什么?如何有效提高概率算法获得正确解的概率或提高算法的求解精度?(课件之“概率算法”,教材之“概率算法”page241)

    答:1)数值概率算法:常用于数值问题的求解,得到的往往是近似解

    (1)解的精度随计算时间的增加而提高

    (2)在许多情况下,计算出问题的精确解是不可能或没必要

    2)蒙特卡罗算法:用于求解问题的准确解,可以求得问题的一个解,但该解未必正确

    (1)求得正确解的概率依赖于算法的计算时间

    多次执行蒙特卡罗算法,可以提高获得正确解的概率

    (2)无法有效判定所得到的解是否肯定正确。

    3)拉斯维加斯算法:不会得到不正确的解

    (1)有时找不到问题的解

    (2)找到正确解的概率随算法计算时间的增加而提高

    (3)用同一拉斯维加斯算法反复对问题实例求解足够多次,可使求解失败的概率任意小。

    4)舍伍德算法:总能求解得到问题的一个解,而且所求得得解总是正确的。

    将确定性算法引入随机性改造成舍伍德算法,可消除或减少问题对于好坏实例间的差别。

     

    18)对于NP完全问题,我们一般采取的求解策略主要有哪些?(课件之“近似算法”,教材之“近似算法”page326)

    答:NP完全问题可行的解题策略

    1)只对问题的特殊实例求解

    2)用动态规划法或分支限界法求解

    3)用概率算法求解

    4)只求近似解

    5)用启发式方法求解

     

     

    展开全文
  • 从斐波那契数列讲解算法的设计思路从斐波那契到递归带备忘录的递归从递归到动态规划动态规划算法设计思路分治算法设计贪心算法设计斐波那契数列的用途与特性斐波那契数列的用途斐波那契数列的特性算法设计总结 ...

    从斐波那契到递归

      很多人在开始学计算机程序设计类的课程时,都听过一个再经典不过的例子,那就是斐波那契数列,也称兔子数列。为什么叫兔子数列呢,我们知道算法的研究当然是为了解决问题,这个问题越实际,这个算法的意义也就越大,而斐波那契数列的求解算法也应该有自己实际所需要解决的问题,这个问题最早开始就是兔子生长数目问题。
      问题说的是,有一对刚出生的兔子,两个月后每对刚出生的兔子又能诞生下一对兔子,假设兔子永远不会死去,并且只要出生的兔子过了两个月就可以一直生小兔子,现在问过了nn个月一共有多少对兔子。
      通过对这个问题的分析我们就可以得出一个条件,第nn个月的兔子有两个来源,第一个来源是n1n-1月就有的兔子,第二个来源就是这个月刚出生的兔子,如果把兔子的总数量当成关于nn的函数,第n个月兔子的数量记成f(n)f(n)。我们惊奇的发现,第n1n-1月出生的兔子到第nn个月还不能生兔子,所以出生的兔子都是之前出生的兔子生的,那就是前n2n-2个月兔子生的,每对兔子可诞生一对,那就意味着第nn个月出生的兔子数量就等于f(n2)f(n-2),两部分我们都表示出来了,我们就得到了大名鼎鼎的斐波那契数列的递归表达式,f(n)=f(n1)+f(n2)f(n)=f(n-1)+f(n-2),光有这个表达式还足够我们解决问题,我们应该注意到第一个月只有一对兔子,第二个月这对兔子还不生产,所以第二个月也只有一对兔子,即f(1)=1,f(2)=1f(1)=1,f(2)=1
      通过上面这个例子,我们就可以看出递归是一种非常适合人类思维的算法策略,第nn个月有多少对兔子这种大问题我们解决不了,我们可以解决小问题,如果n比较小我们可以解决,那么我们就去找寻如何把问题从大化小的办法。递归就深刻的体现了把大问题化成小问题,然后去解决小问题的思想。但是要注意,我们总是很不希望把问题化小的同时引来了新的难以处理的问题,最好这个问题我们能解决,那如果问题化小之后还是这个问题,这个样子就再好不过了。这也是递归需要的,那就是大问题在化解为小问题的时候,是重复的子问题。问题可以化解了,我们化解到什么程度呢,比如本例中的第1个月和第2个月,我们就觉得这样的问题可以解决,所以递归还需要有初始值,代表子问题化小的终点
      我们还知道,在计算机编程语言里,函数就是为了完成一种任务,我们去解决大问题,可以先调用小问题的解决函数,既然递归的大问题和小问题是同一种问题,这就相当于函数调用的小问题函数是自己,也就是出现了函数调用自身的情况,再使用初始值作为函数的结束条件,这就是程序中的递归。而栈的结构应用于这种递归思想再合适不过了,所以递归是一种既符合人类思维、又符合程序语言设计、还符合计算机底层设计的一种思路。
      递归的好处算是显而易见了,因为符合程序设计语言和人类思维,所以递归的代码写出来都是非常简洁的,无非就是设计好终止条件,然后根据不同的条件做递归就行了。在很多情况下都是非常好用的,比如在操作数据结构中的树,比如需要使用栈的一些特性中。但是递归也有自己的缺点,首先就是开销问题,因为使用递归要多次的调用函数,这是有开销的,当问题的规模非常大的时候,过于多次的调用会使得程序的栈溢出,这也是务必需要规避的。此外,递归还有一个缺点就是有可能带来重复计算的问题。在上述斐波那契数列的递归计算路径如下图。
    递归计算斐波那契f(6)路径
      如图所示,我们可以看到计算f(6)f(6)的时候,越底层的项重复计算的就越多。可以用数学证明,这个计算量是指数增加的,而其中又都是重复计算。

    带备忘录的递归

      有没有一种方法可以减少递归算法的重复计算,可以想到在递归过程中引入一个备忘录,专门用来存储已经计算过的值,通常采用的数据结构是数组,因为数组的随机访问可以实现真正意义上的O(1)O(1)查找。以上图为例,第一次递归调用计算f(3)f(3)的时候,我们就可以开辟一块数组,把计算结果记录下来,下次计算就去查找就行了。总的来说就时要计算一个值,我们直接去查找,如果找到就返回,找不到则计算。
      这种算法思路本质上还是递归,只是通过空间换时间,来减少了重复计算。有的人把这种算法称为动态规划,我不习惯这样,因为这种算法不具备动态规划自底向上的特征。动态规划后面会讲解到。
      尽管这种备忘录的方式减少了递归的重复计算,降低了算法的时间复杂度到O(n)O(n)级别,但是还是有可能出现递归的其他问题。同时空间也不是最优的。

    从递归到动态规划

      我么仔细研究递归的路径,我们有f(1)f(1)f(2)f(2)就可以计算f(3)f(3)了,此时计算出来的f(3)f(3)又可以帮助我们计算f(4)f(4),然后如此无穷无尽,想计算n为多少,都是可以的了。我们可以放弃原来递归那种自顶向下的算法策略,因为自顶向下容易让我们难以窥测全局。同时,自底向上也没有重复计算的弊端。我们现在可以采取从前到后的循环计算方式,计算后面的值只需要前两个值就可以了,我们也没有必要把计算到的所有值都存储起来,这样就大大的降低了空间复杂度。从原来递归的O(n)O(n)降到了现在的O(1)O(1)
      我们一步步的思考到这个循环算法都是有前提的,首先就是把大问题化小,在化小的过程中,我们发现了这个子问题和原来的问题是同一类问题,这个要素动态规划也会遇到,称之为重叠子问题要素
      到目前为止,我们就回避了递归的所有缺点,效率低和重复计算的问题,我们是通过循环来解决这个问题的,而这种自底向上的循环同时也是动态规划的基础。我们注意到上例中,我们在计算一个值得时候,这个值只和前面的值有关,当这个值一旦确定(状态一旦确定),就和后面的值无关了(状态),通俗来讲,就是某状态以后的过程不会影响以前的状态,这就是动态规划的另一个要素叫无后效性
      但是这个循环求解还不能被称为严格意义上的动态规划,原因在于动态规划还需要满足一个要素,就是最优子结构。这个要素说的就是我们在求解中间过程中我们每一次确定的中间状态(求解出来的值)都是最优的,而且最终的问题是也是寻找最优的,并且局部最优决定全局最优。这个最优的可以是时间最短,开销最小等等条件,总之体现最…就完事了。
      在这里说句题外话,我把兔子数目问题改一改,改成每对兔子过两个月最多可以生一对兔子,最终求n个月之后最多有多少对兔子。这样不就是动态规划了,甚至直接就是贪心了,求解还是一样的,所以最优子结构的要素不必过于拘泥细节。
      动态规划算法的设计的里程碑就是设计出状态转移方程,如在兔子的问题中状态转移方程就是f(n)=f(n1)+f(n2)f(n)=f(n-1)+f(n-2)这个表达式,通俗来说状态转移方程就是后面的状态由前面状态导出的关系式。这是我们编写代码的基础,从状态转移方程我们可以看到循环的过程,就是不断地计算后一个状态;同时也能够从中看到状态之间的联系。
      动态规划的应用有很多,也算是算法设计中的一个难点,但是也只有能做到灵活运用动态规划,掌握动态规划的步骤,设计思路来解决问题这样算是一个合格的算法设计者。下面将整体的梳理一下动态规划的算法设计思路。

    动态规划算法设计思路

     1. 分析问题(最优解)的性质,将问题化小,然后刻画子结构的特征
     2. 根据大问题与小问题的联系,分析推出状态转移方程,一般是一个递归的公式
     3. 根据状态转移的顺序,确定初始值,然后以自底向上的方式计算出最优质解
     4. 根据最优值的信息,构造出解。

      值得一提的是最后个过程,一般情况下根据状态转移方程算出来的答案就是最终解,但是很多时候也会存在转换的过程,求出来的值并不是最终的解,而是需要算法构思者自己建立联系,实现转换的过程。以动态规划一个经典的案例来说,最大子串和的最优解法并不是去计算子串的和,而是去计算到某一个数为止最大的的子串和。
      动态规划基于循环实现,动态规划和循环通常都是能够降低递归的开销,在遇到一个算法题的时候,如果我们能够很自然的想到递归解法,往往我们也需要想一想,能够将递归算法改为循环,甚至改成动态规划的自底向上计算,能不能减少开销,这也是一个重要的思路递进规程。

      动态规划的重点内容到此也就结束了,后面有机会我会讲解一些动态规划和贪心算法设计的的思路,也算是在这里给自己挖个坑,后面慢慢填。

    分治算法设计

      从递归的基础出发,还有一条重要的算法设计路径,就是分治的思想,分治就是分而治之,基于递归的基础将大问题划分成小问题的然后解决,划分后的小问题之间是独立的,共同决定了大问题的解。举快排的例子,根据pivot把一个数组分为两部分,这就是问题的划分,划分出的子问题就是两部分分别排序,两部分是不相交的,不存在需要排序的公共部分,分别排序后构成了总的排序。所以分治由两个步骤组成,一个步骤就是分,把问题划分成不相交的子问题,一个步骤就是治,解决划分后的问题
      很多分治算法还有一个最终的合并过程,因为划分后的子问题可能并不是直接得到总问题的解。以归并排序为例,划分成两段之后分别排序,但是排序好的两段不能直接作为排序的结果,需要一个两段的合并的过程。
      分治的算法一般不好直接分析算法的复杂度,所以才有了著名的主定理(master theorem),对于分治,算法的划分大概都可以得出一个类似于 T(n)=aT(nb)+f(n)T(n)=aT\left ( \frac{n}{b} \right )+f(n)的公式,其中aa表示划分后需要处理子问题的数量,nn为总问题的规模,nb\frac{n}{b}为每个子问题的规模。然后根据f(n)f(n)O(nlogba)O\left(n^{\log_ba}\right)的关系来判断算法复杂度。
      直观上来讲就是划分的问题越少,每个子问题的复杂度越小,总的复杂度越小。主定理的详细内容和推到再次不做讲解。

    贪心算法设计

      如果我们能够分析到动态规划的要素,我们敏感的嗅觉就能告诉我这是一个动态规划问题,但是知道这是一个动态规划问题和迅速的推导出状态转移方程,并写出代码还有一个巨大的差距,除非已经接触过这种问题。在这个时候,另一种算法设计思路就可以拉出来溜溜了,这就是贪心算法。贪心算法同样需要满足动态规划的最优子结构要素,甚至可以说,贪心算法是一种特殊的动态规划。这种特殊性体现在,贪心的最优子结构状态在选择上具有一定的特殊性质
      在一般的贪心算法中,求解子问题需要对多种情况进行计算,然后对计算值进行评价找出最优的的结构,但是有些结构可能我们能够很容易的判断是最优的结构,例如克鲁斯卡尔算法生成最小生成树,我们要保持加入一个节点的生成树最小,可能有多条路径选择,我们直接选择能加入的最小的边就可以了。这种根据最优性质选择最优状态的算法就是贪心算法。可见贪心算法相对于一般的动态规划算法最大的区别就在于最优结构能否通过某种性质获得。
      所以此时的问题变成了如何寻找最优,有简便方法,就使用,没有的话就只好继续使用一般动态规划思路求解,也就是在子结构的选择中使用暴力方法。而事实恰恰就是大多数问题中都不存在这种特殊的性质,所以动态规划是需要重点掌握的方法。贪心一般对于特殊问题有针对性,注意积累即可

    斐波那契数列的用途与特性

    斐波那契数列的用途

      斐波那契数列是一种需要使用一种迭代式求解的典型问题,可以给其他问题的求解提供一定的借鉴,甚至有些算法问题直接就是斐波那契数列套上了一层外衣,这样的问题有很多,本文引一两例。
      例1:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法?
      这个问题就是典型的斐波那契数列,一次可以跳一个或两个台阶,那么说明第nn个台阶可以是从第n1n-1n2n-2个台阶上跳上来的,所以就自然的推出了斐波那契的递推式。而且我们在做类似的题目不能过度拘泥于2阶的特性,可以不止前两项之和,也可以是前三项,或者之积等等。

    斐波那契数列的特性

      斐波那契和黄金分割的关系式非常密切的,以及特征值等等性质过于数学,感兴趣可以查找相关资料,在此讲解一种比较实用的计算斐波那契数列的方法,是基于线性代数的。

    斐波那契数列的矩阵计算
      这个推导应该很容易理解,根据这个矩阵的指数形式来计算f(n)f(n),直接乘的话复杂度仍然是O(n)O(n)的,但是指数的计算有个重要的性质指数相加,等于两个数相乘,使用如下公式可以省去很多计算,比如需要计算f(14)f(14)的时候,可以先依次计算f(3),f(6),f(7)f(3),f(6),f(7)。这样就可以把时间复杂度降低到O(logn)O(logn)
    xn={xn/2xn/2xxn/2xn/2xx x^n=\left\{ \begin{aligned} x^{n/2}\cdot x^{n/2}\quad x是偶数 \\ x^{n/2}\cdot x^{n/2}\cdot x \quad x是奇数\\ \end{aligned} \right.

    算法设计总结

      总的来说求解问题设计算法,一般都是一个递进式的思路,暴力算法大家可能很轻易就想到了,接下来就是根据问题的性质去做优化了,很可能大家也很自然的针对问题逐渐减小的规模构造出算法的递归求解,但是递归求解通常会带来资源的开销和重复计算的问题,如果这两个问题需要解决,可以考虑循环改写成循环的实现。再者可以考虑能够动过动态规划的方式来解决重复计算,通常动态规划求解的问题都是递归具有指数复杂度的问题。但是动态规划当中还存在着最优子结构选取的暴力求解,能否根据最优子结构的性质把这里优化了,直接根据性质选择到了最优子结构,这就是贪心算法了。也有可能优化算法的时候发现并不存在最优子结构的性质或者局部最优无法决定全局最优,动态规划算法失效。但是问题可以通过相似的划分,然后对划分后的问题逐个击破这就是分治了。
      本文着重于算法思想的理解,篇幅有限有很多的东西还未能一次性写到,重点的内容留给以后有机会继续解释,希望此文能够给看到的人一些帮助或者启示,也供阅读者交流之用。

    展开全文
  • 算法设计之概率算法

    千次阅读 2018-11-19 13:16:38
    算法设计之概率算法 1.为什么需要概率算法? 与确定性算法相比,若冒险,可能做得更好! 概率算法的分类? 数字算法。 求数字问题的近似解求数字问题的近似解 Monte Carlo算法 (MC算法) 这里我们指的MC算法是:...

    算法设计之概率算法

    • 1.为什么需要概率算法?

    与确定性算法相比,若冒险,可能做得更好!

    • 概率算法的分类?
    1. 数字算法。
      求数字问题的近似解求数字问题的近似解
    2. Monte Carlo算法 (MC算法)
      这里我们指的MC算法是: 若问题只有1个正确的解,而无近似解的可能时使用MC算法。
      特点:MC算法总是给出一个答案,但该答案未必正确,成功(即答案是正确的)的概率正比于算法执行的时间。
      缺点:一般不能有效地确定算法的答案是否正确。

      常见的场景:素数测定
      在这里插入图片描述

    所以MC算法的基本思想是:为了增加一个一致的、p-正确算法成功的概率,只需多次调用同一算法,然后选择出现次数最多的解。

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    3. Las Vegas(LV)
    LV算法绝不返回错误的答案。
    特点:获得的答案必定正确,但有时它仍根本就找不到答案。
    与MC算法一样,成功的概率正比于算法的执行时间。
    常见问题:N皇后问题。
    4.Sherwood算法
    当某些确定算法解决一个特殊问题平均的时间比最坏时间快得多时,我们可以使用Sherwood算法来减少,甚至是消除好的和坏的实例之间的差别。
    常见的场景: 离散对数计算,搜索有序表
    将输入实例随机化,从概率上消除实例的差异:
    可将随机预处理使用到f的计算上:
    ① 使用函数u将x加密为某一随机实例y
    ② 将y提交给f计算出f(y)的值
    ③ 使用函数v转换为f(x)

    展开全文
  • (1)算法设计与分析_算法设计思路

    千次阅读 2018-09-15 23:55:22
    昨天听了卜东波老师讲的算法设计与分析的课,他在课堂上,首先就给我们讲了算法设计需要注意的思路和问题,我整理了一下,算法设计过程如下: 同时老师也给我们提了一个算法解题思路,那就是,做任何问题的解法,...

    昨天听了卜东波老师讲的算法设计与分析的课,他在课堂上,首先就给我们讲了算法设计需要注意的思路和问题,我整理了一下,算法设计过程如下:

    算法设计过程

    同时老师也给我们提了一个算法解题思路,那就是,做任何问题的解法,首先从最简单的例子开始,然后再说继续往下做。

    老师说的话虽然很简洁,但是是真理啊!自己以后做算法设计也要时刻注意!不要一开始就往难的方向想,而是先用简单的例子去解决,寻找规律和策略再向下做!

    展开全文
  • 本博主自2020年6月1日起,如有任何问题可在博客贴吧留言或者私信博主(包括并不限于GUI软件编写、安装及编程语言中的bug、AI算法设计等),非诚勿扰! 导读:因为博主后台留言实在是太多太多,大多网友都是前来...
  • 算法设计方法1:贪心算法

    千次阅读 2019-03-02 23:14:50
    前言:走出数据结构的世界,进入算法设计的天地 。为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展,线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算...
  • 算法设计——五大算法总结

    千次阅读 2020-09-15 16:10:20
    算法设计总结一、【分治法】二、【动态规划法】三、【贪心算法】四、【回溯法】1、回溯法的一般描述五、【分支限界法】 一、【分治法】 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,...
  • 算法设计分析题库一

    千次阅读 多人点赞 2020-07-03 23:27:58
    ## 选择题 1. 下面(C)不是算法所必须具备的特性。...(1)算法设计(2)算法实现(3)数学建模 (4)算法分析(5)正确性证明 **A.**(3)(4)(1)(5)(2) **B.**(3)(1)(4)(5)(2) **C.**(1)(2)(3)
  • 大神们!请问弗洛伊德算法是不是使用了算法设计的贪心算法? 大神们!请问弗洛伊德算法是不是使用了算法设计的贪心算法?
  • FPGA算法设计随笔

    千次阅读 2018-06-09 10:30:16
    因此,进行算法设计时,算法设计中需要表示的数字用到的小数、符号、无穷大、整数、浮点数等等对应硬件来说都是一串0和1组合的数字。因此,当FPGA工程师设计算法时,需要对这些数字转换。一般转换为定点数值表示方式...
  • 算法设计与分析

    千次阅读 2017-09-23 22:34:44
    采用什么算法设计技术 正确性--是否对所有的实例都得到正确的解 分析算法--效率 算法+数据结构=程序 好的算法 提高求解问题的效率 节省存储空间 算法的研究目标 问题->建模并寻找算法 算法设计技术 ...
  • 文章目录1 算法的研究内容2 算法设计的两个例子2.1 调度问题2.2 算法设计的步骤2.3 投资问题3 总结 在学习算法涉及与分析的内容之前,先了解一下算法所涉及的几个大块的内容,方便以后学习。 1 算法的研究内容 算法...
  • 常用算法设计方法

    千次阅读 2018-05-02 20:22:25
    经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和藐视算法,在算法设计时又常常采用递归技术,用递归描述算法。一、迭代法 迭代法...
  • 算法设计之五大常用算法设计方法总结

    万次阅读 多人点赞 2013-09-08 19:22:13
    算法设计之五大常用算法设计方法总结 一、【分治法】  在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的...
  • 算法设计技巧与分析 答案整理

    万次阅读 多人点赞 2020-01-06 19:50:49
    算法设计技巧与分析(沙特版)》 这书答案真难找啊… 东拼西凑薅出这么些 文章目录第1章 算法分析基本概念1.41.51.71.91.111.131.141.161.171.251.271.311.321.331.371.38第2章 数学预备知识2.102.16第3章 数据...
  • 算法设计与分析复习大纲

    千次阅读 多人点赞 2020-06-09 11:40:49
    算法设计与分析复习大纲
  • 《计算机算法设计与分析(第3版)》为普通高等教育“十一五”国家级规划教材,是计算机专业核心课程“算法设计与分析”教材。全书以算法设计策略为知识单元,系统介绍计算机算法的设计方法与分析技巧。主要内容包括:...
  • 算法设计技巧

    千次阅读 2012-12-26 18:21:55
    一种局部最优算法设计思路,思想是保证每一步选择在当前达到最优。一个很常见的贪心算法案例是零钱找取问题。 调度问题:书上的调度问题比较简单,其目标是所有作业的平均持续时间(调度+运行)最短,无论是但...
  • 算法设计经典算法

    千次阅读 2018-12-04 10:35:37
    一、贪婪算法 1、概述 贪婪法又称贪心算法,是当追求的目标是一个问题的最优解时,设法把对整个问题的求解工作分成若干步骤来完成,是寻找最优解问题的常用方法。 贪婪法的特点是一般可以快速得到满意的解,因为...
  • 衔接上一篇文章:【算法设计与分析】13 分治策略的设计思想 文章目录1 分治算法的一般性描述1.1 分支算法的时间分析1.2 两类常见的递推方程与求解方法2 总结 1 分治算法的一般性描述 设分治算法为:Divide-and-...
  • 《算法之道》精华 算法设计部分

    千次阅读 2014-08-09 11:09:32
    《算法之道》精华 算法设计部分 本书作者绉恒明,作者另有一本书《数据结构之弦》,以及《操作系统之哲学原理》都是很好的书这本书可以算得上是深入浅出,文笔很好,作者添加了很多自己的思考本文仅包括算法设计...
  • 我正在实习,要独立做一个关于激光雷达的MATLAB算法设计,也看了一些资料和论文,但是没有工程文件和代码,有代码的又不清楚设计思路,陷入了非常困难得境地。目前再看《雷达系统设计MATLAB》仿真,但是还是一团糊涂...
  • 算法设计与分析学习总结

    千次阅读 2019-12-11 01:27:04
    算法设计与分析学习总结 通过对《算法设计与分析》这门课的学习,似乎对算法有了一定的了解,之前对算法并没有太多的接触,只是一些普通的编程。选课的时候,觉得特别有意思,就选了这门课,通过学习各类算法,有了...
  • 算法设计与分析(三)之贪心算法

    千次阅读 2017-11-19 00:00:00
    
 
 
 
 
 
 
 前面两篇:算法设计与分析之分治思想算法设计与分析(二)之动态规划贪心算法的特点设计要素:贪心法适用于...
  • 分类目录:《算法设计与分析》总目录 分析算法的结果意味着预测算法需要的资源。虽然有时我们主要关心像内存、通信带宽或计算机硬件这类资源,但是通常我们想度量的是计算时间。一般来说,通过分析求解某个问题的几...
  • 算法设计技巧 贪婪算法 顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体...
  • 常见的算法设计方法

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

    千次阅读 2020-03-19 19:08:23
    算法设计的四个要求 1. 正确性 2. 可读性:便于他人理解交流 3. 健壮性:当输入数据不合法,算法也能做出相应处理。 4. 时间效率高和存储量低
  • 算法设计与分析课程总结

    千次阅读 2017-11-04 18:04:11
     算法设计与分析是面向设计的核心课程,主要通过介绍常见的算法设计策略及复杂性分析方法,培养学生分析问题和解决问题的能力,为开发高效的软件系统及参加相关领域的研究工作奠定坚实的基础。该课程理论与实践并重...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 148,449
精华内容 59,379
关键字:

算法设计