..页眉.. 页脚.. 算法: 1. 分治算法: (最常见的就是二分法) 分治算法的基本思想是将一个规模为 N 的问题分解为 K 个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂, 使得直接求解法在时间上相当长, 或者根本无法直接求出。对于这类问题, 我们往往先把它分解成几个子问题,找到求出这几个子问题的解法后,再找到合适的方法,把它们组合成求整个问题的解法。如果这些子问题还较大, 难以解决, 可以再把它们分成几个更小的子问题, 以此类推, 直至可以直接求出解为止。这就是分治策略的基本思想。 2. 贪心法(求最小二叉树,) 贪心算法(又称贪婪算法)是指:在对问题求解时,总是做出在当前看来是最好的选择。也就是说, 不从整体最优上加以考虑, 他所做出的仅在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体的最优解, 但对范围相当广泛的许多问题他能产生整体最优解或者整体最优解的近似解。 3. 动态规划算法基本思想与分治法类似, 也是将待求解的问题分解为若干个子问题( 阶段), 按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解, 通过决策保留那些有可能达到最优的局部解, 丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。与分治法最大的差别是: 适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上, 进行进一步的求解)。适用的情况能采用动态规划求解的问题的一般要具有 3 个性质: (1) 最优化原理: 如果问题的最优解所包含的子问题的解也是最优的, 就称该问题具有最优子结构,即满足最优化原理。(2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。(3 )有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。( 该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势) 4. 回溯算法(迷宫) 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是: 从一条路往前走, 能进则进, 不能进则退回来, 换一条路再试。..页眉.. 页脚.. 5. 分支定界法(背包问题) 分支定界(branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同, 分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树, 并且, 在分支定界算法中,每一个活结点只有一次机会成为扩展结点。利用分支定界算法对问题的解空间树进行搜索,它的搜索策略是: 1 .产生当前扩展结点的所有子结点; 2 .在产生的子结点中,抛弃那些不可能产生可行解(或最优解)的结点; 3 .将其余的子结点加入活结点表; 4 .从活结点表中选择下一个活结点作为新的扩展结点。如此循环,直到找到问题的可行解(最优解)或活结点
软件设计师部分要点总结 来自淘豆网m.daumloan.com转载请标明出处.
