精华内容
参与话题
问答
  • 算法设计经典算法

    千次阅读 2018-12-04 10:35:37
    一、贪婪算法 1、概述 贪婪法又称贪心算法,是当追求的目标是一个问题的最优解时,设法把对整个问题的求解工作分成若干步骤来完成,是寻找最优解问题的常用方法。 贪婪法的特点是一般可以快速得到满意的解,因为...

    一、贪婪算法

    1、概述

    贪婪法又称贪心算法,是当追求的目标是一个问题的最优解时,设法把对整个问题的求解工作分成若干步骤来完成,是寻找最优解问题的常用方法。

    贪婪法的特点是一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。如装箱问题和和着色问题都可以采用贪婪法来求解。

    2、问题实例

    现在根据实际问题来说明贪婪法的算法思想。

    装箱问题

    问题描述:装箱问题可简述如下:设有编号为0、1、…、n-1的n种物品,体积分别为v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V,即对于0≤i<n,有0<vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。 
       若考察将n种物品的集合分划成n个或小于n个物品的所有子集,最优解就可以找到。但所有可能划分的总数太大。对适当大的n,找出所有可能的划分要花费的时间是无法承受的。为此,对装箱问题采用非常简单的近似算法,即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中,该算法虽不能保证找到最优解,但还是能找到非常好的解。不失一般性,设n件物品的体积是按从大到小排好序的,即有v0≥v1≥…≥vn-1。如不满足上述要求,只要先对这n件物品按它们的体积从大到小排序,然后按排序结果对物品重新编号即可。装箱算法简单描述如下: 
    {   输入箱子的容积; 
       输入物品种数n; 
       按体积从大到小顺序,输入各物品的体积; 
       预置已用箱子链为空; 
       预置已用箱子计数器box_count为0; 
       for (i=0;i<n;i++) 
       {   从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j; 
          if (已用箱子都不能再放物品i) 
          {   另用一个箱子,并将物品i放入该箱子; 
             box_count++; 
          } 
          else 
             将物品i放入箱子j; 
       } 

       上述算法能求出需要的箱子数box_count,并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解,设有6种物品,它们的体积分别为:60、45、35、20、20和20单位体积,箱子的容积为100个单位体积。按上述算法计算,需三只箱子,各箱子所装物品分别为:第一只箱子装物品1、3;第二只箱子装物品2、4、5;第三只箱子装物品6。而最优解为两只箱子,分别装物品1、4、5和2、3、6。 
     二、分治法

    1、概述

    分治法的基本思想是把一个规模较大的问题分成两个或者多个较小的和原问题相似的子问题,首先对子问题进行求解,然后再把各个子问题的解合并起来,得出整个问题的解。

    2、问题实例

    分治法的三个步骤:

    step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
    step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
    step3 合并:将各个子问题的解合并为原问题的解。

    实例:

    在一个未排序的数组中找到第k大元素,即排序后的第k大的数。

    分析:

    总是将要划界的数组段末尾的元素为划界元,将比其小的数交换至前,比其大的数交换至后,最后将划界元放在“中间位置”(左边小,右边大)。划界将数组分解成两个子数组(可能为空)。

    设数组下表从low开始,至high结束。
    1、 总是取要划界的数组末尾元素为划界元x,开始划界:

    a) 用j从low遍历到high-1(最后一个暂不处理),i=low-1,如果nums[j]比x小就将nums[++i]与nums[j]交换位置

    b) 遍历完后再次将nums[i+1]与nums[high]交换位置(处理最后一个元素);

    c) 返回划界元的位置i+1,下文称其为midpos

    这时的midpos位置的元素,此时就是整个数组中第N-midpos大的元素,我们所要做的就像二分法一样找到K=N-midpos的“中间位置”,即midpos=N-K

    2、 如果midpos==n-k,那么返回该值,这就是第k大的数。
    3、 如果midpos>n-k,那么第k大的数在左半数组
    4、 如果midpos<n-k,那么第k大的数在右半数组

    三、回溯法

    1、概念

    回溯法也称试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按照某种顺序之一枚举和检验。回溯法的基本思想是采用深度优先策略,一步一步向前试探的方法,当某一步有多种选择时,可以先任意选择一种,继续向前试探。一旦发现到达某步后无法再前进,说明上一步做的选择有问题,就后退到上一步重新选择(这就称为回溯)。回溯法的特点是可以避免穷举式的盲目搜索,从而可能减少问题求解的搜索时间。如迷宫问题和八皇后问题都可以采用回溯方法来设计求解算法。
    2、问题实例

    回溯法的一般步骤:

    (1)针对所给问题,确定问题的解空间:首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。

    (2)确定结点的扩展搜索规则

    (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

    八皇后问题
    问题描述:八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。

    转化规则:其实八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。令一个一维数组a[n]保存所得解,其中a[i] 表示把第i个皇后放在第i行的列数(注意i的值都是从0开始计算的),下面就八皇后问题的约束条件。
    (1)因为所有的皇后都不能放在同一列,因此任意两个a[0].....a[7]的值不能存在相同的两个值。
    (2)所有的皇后都不能在对角线上,那么该如何检测两个皇后是否在同一个对角线上?我们将棋盘的方格成一个二维数组,如下:


    假设有两个皇后被放置在(i,j)和(k,l)的位置上,明显,当且仅当|i-k|=|j-l| 时,两个皇后才在同一条对角线上。

    四、动态规划法

    1、概述

    动态规划与分治法相似,都是把一个大问题分解为若干较小的子问题,通过求解子问题而得到原问题的解.不同的是分治法每次分解的子问题数目较少,子问题之间界限清楚,处理的过程通常是自顶向下进行;而动态规划法分解子问题可能较多,而且子问题相互包含,为了重用已经计算的结果,要把计算的中间结果保存起来,动态规划法通常是自底向上进行。

     2、问题实例

    动态规划的思路是通过寻找最优子结构同时记录最优结构,从而将复杂的大问题转化为小问题的求解过程。解决动态规划类问题,分为两步:1.确定状态,2.根据状态列状态转移方程

    例题:背包问题1

    在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]。

    首先寻找状态,确定将什么作为状态,记录状态,有背包和物品,物品有放和不放两种状态,放置的时候可能会对应各种容量,当前的容量下可以放置进的最多的物品取决于上一个物品放置时在该状态下所能够达到的最大状态和当前物品的的大小,这样我们在最后,就可以得到每种容量下,所能放置的物品的最大数量。

    背包问题2:

    给出n个物品的体积A[i]和其价值V[i],将他们装入一个大小为m的背包,最多能装入的总价值有多大?

    考虑到价值问题,状态不发生变化,只是对于状态我们所记录的内容方式变化,我们现在记录的是其价值,而不是其放置的物品的大小。

     五、分支限界法

    1、概述

    分枝界限法(Branch and Bound)与回溯法相似,也是一种在全部问题解的空间中进行系统搜索的方法。所不同的是,回溯法使用深度优先策略,而分支界限法可以采用广度优先策略。与此同时,分支界限法在搜索过程中,还利用最优解属性的上下界来控制搜索的分支,剪去不必再花时间搜索的部分,从而提高搜索的效率。
    2、算法

    算法基本思想如下:

    1)以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树
    2)分支限界法中,每一个活结点只有一次机会成为扩展结点,活结点一旦成为扩展结点,就一次性产生其所有儿子结点,其中导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中
    3)然后从活结点表中取下一结点成为当前扩展结点
    4)重复上述结点扩展过程,直至到找到所需的解或活结点表为空时为止

    分支限界法与回溯法的区别:

    1)求解目标不同 
            回溯法的求解目标是找出解空间树中满足约束条件的所有解
            分支限界法的求解目标则是尽快找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解
            分支限界法通常用于解决离散值的最优化问题
    2)搜索方式不同 
            回溯法以深度优先的方式(遍历结点)搜索解空间树
            分支限界法以广度优先或最小耗费优先的方式搜索解空间树
    3)对扩展结点的扩展方式不同 
            分支限界法中,每一个活结点只有一次机会成为扩展结点
            活结点一旦成为扩展结点,就一次性产生其所有儿子结点
    4)存储空间的要求不同 
            分支限界法的存储空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大

    参考:

    https://blog.csdn.net/K346K346/article/details/50774803

    https://blog.csdn.net/jia_xiaoxin/article/details/2750880

    https://blog.csdn.net/EbowTang/article/details/51218500

    https://segmentfault.com/a/1190000004498566

    https://blog.csdn.net/u010089444/article/details/74331907

    展开全文
  • 算法设计之五大常用算法设计方法总结

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

    算法设计之五大常用算法设计方法总结

    一、【分治法】
     在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……等。任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。
    分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之
    分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法
    如果原问题可分割成k(1<k≤n)个子问题, 且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用"递归技术"提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解,这自然导致递归过程的产生。"分治"与"递归"像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法
    分治法所能解决的问题一般具有以下几个特征:
    1) 该问题的规模缩小到一定的程度就可以容易地解决
    2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。(前提)
    3) 利用该问题分解出的子问题的解可以合并为该问题的解;(最关键的一点)
    4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题
    上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。
    分治法的基本步骤
    分治法在每一层递归上都有三个步骤:
    1)分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
    2)解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
    3)合并:将各个子问题的解合并为原问题的解。
    它的一般的算法设计模式如下:
    Divide-and-Conquer(P)
    if |P|≤n0 {
           then return(ADHOC(P))
    }else{
             将P继续分解为较小的子问题 P1 ,P2 ,...,Pk
         for i←1 to k
         do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
         T ← MERGE(y1,y2,...,yk) △ 合并子问题
    }
    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的解。
    分治法的应用:1.递归与HANOI塔问题; 2.二分法求方程近似解    3. 用C++实现合并排序   4.求最大值和最小值的分治算法
    分治法的复杂性分析
    一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有: 
        
    通过迭代法求得方程的解: 
    
    
    递归方程及其解只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的,从而当mi≤n<mi+1时,T(mi)≤T(n)<T(mi+1)。
    二、【动态规划法】
    最优化原理
    1951年美国数学家R.Bellman等人,根据一类多阶段问题的特点,把“多阶段决策”问题变换为一系列互相联系的“单阶段问题然后逐个加以解决。而且一些静态模型,只要人为地引进“时间”因素,分成时段,就可以转化成多阶段的动态模型,用动态规划方法去处理。与此同时,他提出了解决这类问题的“最优化原理”(Principle of optimality):“一个过程的最优决策具有这样的性质:即无论其初始状态和初始决策如何,其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言,必须构成最优策略”。简言之,一个最优策略的子策略,对于它的初态和终态而言也必是最优的。这个“最优化原理”如果用数学化一点的语言来描述的话,就是:假设为了解决某一优化问题,需要依次作出n个决策D1,D2,…,Dn,如若这个决策序列是最优的,对于任何一个整数k,1 < k < n,不论前面k个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策Dk+1,Dk+2,…,Dn也是最优的。
    最优化原理是动态规划的基础,任何一个问题,如果失去了这个最优化原理的支持,就不可能用动态规划方法计算。能采用动态规划求解的问题都需要满足一定的条件:
    (1) 问题中的状态必须满足最优化原理;
    (2) 问题中的状态必须满足无后效性。
    所谓的无后效性是指:“下一时刻的状态只与当前状态有关,而和当前状态之前的状态无关,当前的状态是对以往决策的总结”。
    问题求解模式
    动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。
    初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
    图1 动态规划决策过程示意图
    (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。
    (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
    (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两段各状态之间的关系来确定决策。
    (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。
    动态规划法的应用:1.动态规划求0/1背包问题      2.最长公共子串问题的实现 3. 用动态规划实现导弹拦截      4.最大化投资回报问题的实现
    算法实现
    动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦设计完成,实现部分就会非常简单。使用动态规划求解问题,最重要的就是确定动态规划三要素:问题的阶段,每个阶段的状态以及从前一个阶段转化到后一个阶段之间的递推关系。递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处。确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。下面分别以求解最大化投资回报问题和最长公共子序列问题为例阐述用动态规划算法求解问题的一般思路。
    三、【贪心算法】
    所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
    贪心算法的基本思路如下:
    1.建立数学模型来描述问题。
    2.把求解的问题分成若干个子问题。
    3.对每一子问题求解,得到子问题的局部最优解。
    4.把子问题的解局部最优解合成原来解问题的一个解。
    实现该算法的过程:
    从问题的某一初始解出发;
    while 能朝给定总目标前进一步 do
    求出可行解的一个解元素;
    由所有解元素组合成问题的一个可行解;
    下面是一个可以使用贪心算法解的题目,贪心解的确不错,可惜不是最优解:
    例题分析:
    [背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。
    要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
    物品:  A   B   C   D   E    F   G
    重量: 35  30  60  50  40  10  25
    价值: 10  40  30  50  35  40  30
    分析:
    目标函数: ∑pi最大
    约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)
    (1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?
    (2)每次挑选所占重量最小的物品装入是否能得到最优解?
    (3)每次选取单位重量价值最大的物品,成为解本题的策略。
    值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。可惜的是,它需要证明后才能真正运用到题目的算法中。
    一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
    对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:
        (1)贪心策略:选取价值最大者。反例:
        W=30
        物品:A B C
        重量:28 12 12
        价值:30 20 20
        根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。
        (2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。
        (3)贪心策略:选取单位重量价值最大的物品。反例:
        W=30
        物品:A B C
        重量:28 20 10
        价值:28 20 10
    根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。
    贪心算法应用:1.最小生成树之Prim算法  2. 最小生成树之kruskal算法
    3. 贪心算法在背包中的应用 4.汽车加油问题之贪心算法
    四、【回溯法】
    回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
    1、回溯法的一般描述
    可用回溯法求解的问题P,通常要能表达为:对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)∣xi∈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的一个约束,n≥i>j。因此,对于约束集D具有完备性的问题P,一旦检测断定某个j元组(x1,x2,…,xj)违反D中仅涉及x1,x2,…,xj的一个约束,就可以肯定,以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都不会是问题P的解,因而就不必去搜索它们、检测它们。回溯法正是针对这类问题,利用这类问题的上述性质而提出来的比枚举法效率更高的算法。
    回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T,把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树,它可以这样构造:设Si中的元素可排成xi(1) ,xi(2) ,…,xi(mi-1) ,|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≤i≤n-1,E中n元组(x1,x2,…,xn)的一个前缀I元组(x1,x2,…,xi)对应于T中的一个非叶子结点,T的根到这个非叶子结点的路径上依次的I条边的权分别为x1,x2,…,xi,反之亦然。特别,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的一个解.
    用回溯法解题的一般步骤:
    (1)针对所给问题,定义问题的解空间;
    (2)确定易于搜索的解空间结构;
    (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。
    回溯法应用:1.回溯法之数的划分               2.回溯法求解 运动员最佳配对问题 
    3.回溯法解决汽车加油次数最少问题 4. 用回溯法找出n个自然数中取r个数的全排列
    五、【分支限界法】
    基本思想 :分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。 
    在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。 此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
    常见的两种分支限界法:
    (1)队列式(FIFO)分支限界法
    按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。 
    (2)优先队列式分支限界法
    按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
    分支限界法与回溯法的不同:
    (1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。 
    (2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
    解空间树的动态搜索
    (1)回溯求解0/1背包问题,虽剪枝减少了搜索空间,但整个搜索按深度优先机械进行,是盲目搜索(不可预测本结点以下的结点进行的如何)。
    (2)回溯求解TSP也是盲目的(虽有目标函数,也只有找到一个可行解后才有意义)
    (3)分支限界法首先确定一个合理的限界函数,并根据限界函数确定目标函数的界[down, up];然后按照广度优先策略遍历问题的解空间树,在某一分支上,依次搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值(对最小化问题,估算结点的down,对最大化问题,估算结点的up)。如果某孩子结点的目标函数值超出目标函数的界,则将其丢弃(从此结点生成的解不会比目前已得的更好),否则入待处理表。
    分支限界法的设计思路
    设求解最大化问题,解向量为X=(x1,…,xn),xi的取值范围为Si,|Si|=ri。在使用分支限界搜索问题的解空间树时,先根据限界函数估算目标函数的界[down, up],然后从根结点出发,扩展根结点的r1个孩子结点,从而构成分量x1的r1种可能的取值方式。
    对这r1个孩子结点分别估算可能的目标函数bound(x1),其含义:以该结点为根的子树所有可能的取值不大于bound(x1),即:
    bound(x1)≥bound(x1,x2)≥…≥ bound(x1,…,xn)
    若某孩子结点的目标函数值超出目标函数的下界,则将该孩子结点丢弃;否则,将该孩子结点保存在待处理结点表PT中。
    再取PT表中目标函数极大值结点作为扩展的根结点,重复上述。
    直到一个叶子结点时的可行解X=(x1,…,xn),及目标函数值bound(x1,…,xn)。
    分支限界法应用:1.分支限界法之装载问题       2. 分支限界法之布线问题 
    3. 分支限界法之0 1背包问题 4. 分支限界法之旅行售货员问题
    整理参考:http://c.chinaitlab.com/special/algorithm/Index.html 
    展开全文
  • 算法设计[中文版].pdf

    2019-02-06 08:28:04
    jon Kleinberg,Eva Tardos著;张立昂,屈婉玲译的算法设计算法设计中文入门版。我们上课时用的这本,,很不错
  • 五大算法设计思想

    万次阅读 多人点赞 2018-05-12 10:18:38
    分治法 概念: 将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 思想策略: 对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解...

    分治法

    概念:

    将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

    思想策略:

    对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。

    特征:

    1) 该问题的规模缩小到一定的程度就可以容易地解决
    2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
    3) 利用该问题分解出的子问题的解可以合并为该问题的解;
    4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

    第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;
    第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;、
    第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。
    第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

    基本步骤:

    1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
    2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
    3 合并:将各个子问题的解合并为原问题的解。

    适用分治法求解的经典问题:

    • 1)二分搜索
    • 2)大整数乘法
    • 3)Strassen矩阵乘法
    • 4)棋盘覆盖
    • 5)合并排序
    • 6)快速排序
    • 7)线性时间选择
    • 8)最接近点对问题
    • 9)循环赛日程表
    • 10)汉诺塔

    动态规划

    概念:

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

    思想策略:

    将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

    特征:

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

    基本步骤:

    (1)分析最优解的性质,并刻画其结构特征。
    (2)递归的定义最优解。
    (3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值
    (4)根据计算最优值时得到的信息,构造问题的最优解

    适用动态规划求解的经典问题:

    • 矩阵连乘,
    • 走金字塔
    • 最长公共子序列(LCS) ,
    • 最长递增子序列(LIS) ,
    • 凸多边形最优三角剖分 ,
    • 背包问题 ,
    • 双调欧几里得旅行商问题

    贪心法

    概念:

    在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。

    思想策略:

    贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

    基本步骤:

    1.建立数学模型来描述问题。
    2.把求解的问题分成若干个子问题。
    3.对每一子问题求解,得到子问题的局部最优解。
    4.把子问题的解局部最优解合成原来解问题的一个解。

    适用贪心法求解的经典问题:

    • 活动选择问题,
    • 钱币找零问题,
    • 再论背包问题,
    • 小船过河问题,
    • 区间覆盖问题,
    • 销售比赛,
    • Huffman编码,
    • Dijkstra算法(求解最短路径),
    • 最小生成树算法

    回溯法

    概念:

    回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。
    回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
    许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

    思想策略:

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

    特征:

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

    适用回溯法求解的经典问题:

    • 八皇后问题,
    • 图的着色问题,
    • 装载问题,
    • 批处理作业调度问题,
    • 再再论背包问题,
    • 最大团问题,
    • 连续邮资问题,
    • 符号三角形问题,

    分支限界法

    概述:

    类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。

    策略:

    在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。

    与回溯法的区别:

    回溯法:【方式不同】深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解【目标不同】。

    分支限界法:【方式不同】广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解【目标不同】。

    展开全文
  • 算法设计与分析期末复习

    万次阅读 多人点赞 2019-06-01 14:18:07
    1.递归的概念:直接或间接地调用自身的算法称为递归算法,用函数自身给出定义的函数称为递归函数。每个递归函数都要有非递归定义的初始值,如阶乘函数,斐波那契,汉诺塔。 递归函数二要素:边界条件、递归方程 2....

    1.递归的概念:直接或间接地调用自身的算法称为递归算法,用函数自身给出定义的函数称为递归函数。每个递归函数都要有非递归定义的初始值,如阶乘函数,斐波那契,汉诺塔。

    递归函数二要素:边界条件、递归方程

    2.分治法的概念:基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。递归的解这些子问题,然后将各个子问题的解合并得到原问题的解。

    (1)如二分法:

    函数参数:(a[],x,n)

    int left=0,right=n-1;

    while(left<=right){

    Int middle=(left+right)/2;

    if(x==a[middle])return middle;

    if(x>a[middle])left=middle+1;

    else right=middle-1;

    }

    return -1;//未找到下标

    (2)大整数乘法:无程序,就是减少乘法次数,时间复杂度降低了一点。

    (3)strassen矩阵乘法:两个n*n的矩阵,Cij=

    每计算出一个C的元素,需要做n次乘法和n-1次加法,n^2个元素时间为O(n^3);

    使用分治法:

    假设n是2的幂,把矩阵A,B,C都划分成四等份,然后再进行相乘。这样我们只乘了2^2*2=8次乘法,2^2*(2-1)=4次加法。

    如果n=2,则可以直接得到最后结果矩阵;如果n>2,则可以继续将子块划分,知道n降到2。——分治降阶的递归算法

    然而这样并没有减少乘法次数,时间复杂度木有降低。所以有Strassen改进:

     

    即用7次乘法和若干次加减法就能得到矩阵乘积:

     

     

    (4)棋盘覆盖:将整个棋盘等分成4份,其中一个特殊方格必在这四个子棋盘中的一个里,其他三个则无特殊方格。所以我们可以用一个L覆盖这三个子棋盘的会合处,这样4个子棋盘就全带有一个特殊方格,化成了同样的问题。递归的将子棋盘都分割,直到棋盘化成了1*1。我们用一个二维数组代表棋盘,设一个全局的整型变量来表示不同的L的编号。

    (5)合并排序:将待排序的n个元素分成大小大致相同的两个子集合,分别对两个子集合排序,最终将排好序的子集合合并。

    void MergeSort(a[],int left,int right){

    if(left<right){//至少有2个元素

    int i=(left+right)/2;

    MergeSort(a,left,i);//前半段排序

    MergeSort(a,i+1,right);//后半段排序

    Merge(a,b,left,i,right);//把前后两次排好的合并到数组b

    Copy(a,b,left,right);//复制回数组a

    }

    时间复杂度O(nlogn)

    (6)快速排序

    void Qsort(T a[],int p,int r){
    if(p<r){
    int q=part(a,p,r);
    Qsort(a,p,q-1);//对左边排序
    Qsort(a,q,r);//对右边排序
    }
    
    }
    int part(T a[],int p,int r){
    int i=p;//左边的游标,自左向右找比轴大的元素
    int j=r;//右边的游标,自右向左找比轴小的元素
    T x=a[p];//用最左边的元素作为轴
    while(1){
      while(a[++i]<x&&i<r);
      while(a[--j]>x);
      if(i>j)break;
      swap(a[i],a[j]);
      
    }
    a[p]=a[j];
    a[j]=x;
    return j;
    
    }

    俩游标分别从子数组的首尾元素开始向中间移动,i的作用是寻找比轴大的元素,然后让其与j替换,j的作用是寻找比轴小的元素,让其与i替换。

    3.动态规划

    和分治法类似,都是将待求问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。而动态规划的子问题往往是相互不独立的,所以可以用一个表来记录所有子问题的解,以免再之后重复计算。

    动态规划基本要素:

    「1」最优子结构性质:

    当问题的最优解包含了其子问题的最优解时,则称该问题具有最优子结构性质。这个性质是动态规划算法求解的重要线索。

    「2」子问题重叠性质

    在运用递归算法自顶向下解题时,每次产生的子问题并不总是新问题,动态规划将计算过的子问题保存在一个表格中,当再次使用时直接搜索到它拿过来用就行了。

    一般步骤如下:

    ·找出最优解的性质,刻画其结构特征

    ·递归的定义最优值

    ·自底向上,计算出最优值

    ·根据计算最优值时得到的信息,得出最优解

    (1)大矩阵乘法

    找出一种最优的乘法次序

    普通算法是,A矩阵的第i行各个元素与B矩阵的第i列的各个元素相乘求和,用动态规划,我们可以先假设在第k位置上将矩阵链断开,找到最优解,则问题变成了两个子问题:(AiAi+1……Ak),(Ak+1……Aj)

    用m[i][j]表示矩阵i到矩阵j连乘的最优值,那么两个子问题对应的最优值变成m[i][k],m[k+1][j],把这两个加起来,再加上这两大块矩阵(A[i,k]和A[k+1,j])相乘的计算量,即为A[i,j]的最优次序。

    设矩阵Am的行数为pm,列数为qm,矩阵是可连乘的,即相邻矩阵qm=pm,所以(AiAi+1……Ak)可表示为pi * qk,

    (Ak+1……Aj)可表示为pk* qj,qk = pk.则两个矩阵连乘的乘法次数为Pi * Pk*  qj。

    得到最优值的递推定义:

    m[i][j]=0,i==j

    m[i][j]=min(k从i到j-1){m[i][k]+m[k+1][j]+pi-1pkpj}

    时间复杂度O(n^3)

    (2)最长公共子序列

    X{x1,x2...,xm},Y{y1,y2...,yn},设最长子序列为Z={z1,z2,....,zk}

    这个问题分三种情况解决,一,当用动态规划解决,若xm=yn,则zk=xm=yn,zk-1是Xm-1和Yn-1的最长子序列;二,当xm!=yn且

    xm!=zk,则Z是Xm-1和Yn的最长子序列,三,同二,当xm!=yn且ym!=zk,则Z是Xm和Yn-1的最长子序列。这样就满足了最优子结构性质。

    用C[i][j]来记录Xi,Yj的最优子序列的长度,根据上面三种情况,递推公式很容易出来了,不再赘述。

    (3)流水作业调度

    找出n个作业在2个机器上的最优调度顺序,这和之前的双击调度不同,每个作业需要先后由2台机器合作完成。

    流水作业调度的johnson算法:

    ·令N1={i|ai<bi},N2={i|ai>=bi}

    ·将N1中作业按ai的非递减顺序排列,N2的非递增序列排序。

    ·N1中作业接N2中作业构成满足johnson法则的最优调度方案。

    (4)0-1背包

    m(i,j)为背包容量为j,可选物品为i,i+1,i+2,...n时的最优值。对于每一个都有装和不装两种,取两者最大。

    m(i,j)=max{m(i+1,j),m(i+1,j-wi)+vi} ,j>=wi

    m(i,j)=m(i+1,j), 0<=j<wi 

    这个问题很典型,不想写了

    (5)最优二叉搜索树,时间复杂度O(n^2)

    (6)用动态规划算法解决最大字段和问题,其时间复杂性为n

    4.贪心算法

    贪心算法并不从整体的最优解考虑,而是做出当前的局部最优的选择。两个要素是组优子结构和贪心选择性质,贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选 择)来达到。

    (1)活动安排问题

    给出了每个活动的起止时间,在所有的活动中找出最大的相容活动子集。

     

    (2)哈夫曼编码

        基本思想是,首先所有字符对应n 棵树构成的森林,每棵树只有一个结点,根权为对应字符的频率。然后,重复下列过程n-1 次:

        将森林中的根权最小的两棵树进行合并产生一个新树,该新树根的两个子树分别是参与合并的两棵子树,根权为两个子树根权之和。

    时间复杂度:O(nlogn)

    (3)Prim算法(保证连通,加n-1条边):时间复杂度O(n^2)

    (4)Kruskal算法(保证无回路,加n-1条边):时间复杂度:O(nlogn)

    动态规划算法与贪心算法的异同:

    共同点:

    都需要最优子结构性质,

                 都用来求有优化问题。

    不同点:

    动态规划:每一步作一个选择——依赖于子问题的解。

                贪心方法:每一步作一个选择——不依赖于子问题的解。

                动态规划方法的条件:最优子结构性质;子问题的重叠性质。

                可用贪心方法的条件:最优子结构性质;贪心选择性质。

    动态规划:自底向上求解(动态规划方法是自底向上计算各个子问题的最优解,即先计算子问题的最优解,然后再利用子问题的最优解构造大问题的最优解,因此需要最优子结构)

                 贪心方法: 自顶向下求解。

     可用贪心法时,动态规划方法可能不适用;

                  可用动态规划方法时,贪心法可能不适用。

    5.回溯:

    回溯法的基本思想是:为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数来处死那些实际上不可能产生所需解的活结点,以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。

    回溯法的两种解空间树:子集树和排列树;

    剪枝函数:用约束函数在扩展结点处剪去不满足约束的子树;用限界函数剪去得不到最优解的子树。

    如背包是子集树,售货商是排列树(O(n!))

    6.分支限界法:

    常见的两种分支限界法:队列式(FIFO)分支限界法--将活结点表组织成一个队列,按照先 进先出(FIFO)原则选取下一个结点为扩展结点;优先队列式分支限界法--将活结点表组织 成一个优先队列,按照规定的优先级选取优先级最高的结点成为当前扩展结点

     

     

     

     

     

     

    展开全文
  • 算法设计》是近年来关于算法设计和分析的不可多得的优秀教材。《算法设计》围绕算法设计技术组织素材,对每种算法技术选择了多个典型范例进行分析。《算法设计》将直观性与严谨性完美地结合起来。每章从实际问题...
  • 算法设计与分析 注:笔记摘自《计算机算法设计与分析》王晓东 第五版 第二章 递归与分治策略 2.1 递归的概念 递归算法:一个直接或间接地调用自身的算法 递归函数:使用函数自身给出定义的函数 递归方程:对于...
  • 常见的算法设计方法

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

    千次阅读 热门讨论 2015-10-11 14:17:56
    最近让我很头疼的一件事,就是做算法题。早就听师哥师姐们说算法特别难,这会儿终于体会到了。不过,我们不能被他打到,不能被他可怕的外表吓到。   【为什么难】我仔细想了想,为什么我们觉得他很难?原因有三:...
  • 《计算机算法设计与分析第三版课后答案》 王晓东编著 里面有很详细的课后答案讲解 加上图形 算法分析各章节都有详细的讲解! 加上图形 算法分析各章节都有详细的讲解!加上图形 算法分析各章节都有详细的讲解!加上...
  • 算法设计与分析(陈慧南)答案

    热门讨论 2009-09-28 12:00:36
    算法设计与分析(陈慧南)课后习题部分答案 算法设计与分析(陈慧南)课后习题部分答案 算法设计与分析(陈慧南)课后习题部分答案
  • 算法设计与分析学习总结

    千次阅读 2019-12-11 01:27:04
    算法设计与分析学习总结 通过对《算法设计与分析》这门课的学习,似乎对算法有了一定的了解,之前对算法并没有太多的接触,只是一些普通的编程。选课的时候,觉得特别有意思,就选了这门课,通过学习各类算法,有了...
  • 《计算机算法设计与分析》王晓东 经典算法教材,ACM必备书之一。 资源包:(1)计算机算法设计与分析 第二版 pdf; (2)计算机算法设计与分析 第三版 习题答案;(3)计算机算法设计与分析 ppt
  • 王晓东老师的计算机算法分析与设计是国内的最权威的教材,这是最新版PPT,2012年的王晓东老师《计算机算法设计与分析》第四版PPT
  • 这套方法站在通用问题求解策略的高度,能对现有的大多数算法都能进行准确分类,从而使本书的读者能够沿着一条清晰的、一致的、连贯的思路来探索算法设计与分析这一迷人领域。本书作为第2版,相对第1版增加了新的习题...
  • 算法设计与分析基础(第3版)

    万次阅读 多人点赞 2018-08-20 18:42:40
    - 算法设计与分析基础 - Anany Levitin 著 (第三版) 序言 设计技术作为问题求解的一般性策略 分析算法效率(算法经验分析、算法可视化) 各种方法加习题练习 目录 1. 绪论 2. 算法效率分析基础 3. 蛮...
  • 计算机算法设计与分析课后答案 王晓东 编 第二版
  • 算法设计与分析基础 习题参考答案

    千次下载 热门讨论 2007-10-17 19:04:21
    算法设计与分析基础 习题参考答案
  • 需要算法设计与分析屈婉玲课后习题答案,希望哪位大神帮帮忙!大恩不言谢
  • 算法设计与分析课程总结

    千次阅读 2017-11-04 18:04:11
    算法分析与设计课程总结  算法设计与分析是面向设计的核心课程,主要通过介绍常见的算法设计策略及复杂性分析方法,培养学生分析问题和解决问题的能力,为开发高效的软件系统及参加相关领域的研究工作奠定坚实的...
  • 算法设计与分析专栏的目录
  • 本资源已更新至http://download.csdn.net/source/1791589 计算机算法设计与分析答案 (第三版) 完整版 王晓东 含每道题答案及解析
  • 3.加强对数据结构和算法的应用; 4.锻炼自己以科学理论和工程上能力的技术,规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用; 5.通过课程设计的实践,我们可以在程序设计方法、上机操作等基本技能...
  • 《计算机算法设计与分析(第3版)》为普通高等教育“十一五”国家级规划教材,是计算机专业核心课程“算法设计与分析”教材。全书以算法设计策略为知识单元,系统介绍计算机算法的设计方法与分析技巧。主要内容包括:...
  • 算法设计与分析 ppt

    千次阅读 2008-06-17 22:18:00
    导读: 【PPT】算法设计与分析文件格式:PPT/Microsoft Powerpoint - HTML版算法概述 一,算法程序 算法的概念(性质) 算法程序 算法的描述方法 二,算法复杂性分析 算法复杂性的意义 渐进...概率算法 了解概率算法...
  • 【算法】算法设计与分析试题(含答案)

    千次阅读 多人点赞 2013-11-25 00:34:00
    算法设计与分析试题 (中国科学院大学-陈玉福-2011秋) 一. 回答下列问题: (每小题5分) 1.陈述算法在最坏情况下的时间复杂度和平均时间复杂度;这两种评估算法复杂性的方法各自有什么实际意义? 最坏情况下的...
  • 算法设计与分析 实验报告

    千次阅读 2017-04-10 10:24:17
    算法设计与分析实验报告题目一:矩阵相乘题目二:最长公共子序列题目一:矩阵相乘一.问题描述给定n个矩阵{A1,A2,... ,An},其中这n个矩阵是可相乘的,i=1,2,...,n-1。算出这n个矩阵的相乘积A1A2 。。。An...

空空如也

1 2 3 4 5 ... 20
收藏数 1,001,139
精华内容 400,455
关键字:

算法设计