iOS梦工厂

iCocos——不战胜自己,何以改变未来!

修行篇-五大常用算法

| Comments

分治算法

概念:分而治之
把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并

排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……

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

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

这自然导致递归过程的产生。分治与递归像一对孪生兄弟
特征:

分治法所能解决的问题一般具有以下几个特征:

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解;

4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

综上:

  • 第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;

  • 第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;、

  • 第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。

  • 第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

性能:

一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:

T(n)= k T(n/m)+f(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)。 
经典问题
  • (1)二分搜索
  • (2)大整数乘法
  • (3)Strassen矩阵乘法
  • (4)棋盘覆盖
  • (5)合并排序
  • (6)快速排序
  • (7)线性时间选择
  • (8)最接近点对问题
  • (9)循环赛日程表
  • (10)汉诺塔
思维过程
实际上就是类似于数学归纳法,找到解决本问题的求解方程公式,然后根据方程公式设计递归程序。
  1. 一定是先找到最小问题规模时的求解方法
  2. 然后考虑随着问题规模增大时的求解方法
  3. 找到求解的递归函数式后(各种规模或因子),设计递归程序即可。

动态规划

概念
每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划
思想
基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解
特点:
叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中
与分治法最大的差别是:
适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。
使用
  • (1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

  • (2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

  • (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势) 实际应用

三要素:

使用动态规划求解问题,最重要的就是确定动态规划三要素:

(1)问题的阶段 

(2)每个阶段的状态

(3)从前一个阶段转化到后一个阶段之间的递推关系。
总结

递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处。

确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

      f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

贪心算法

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

贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。

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

局部最优策略能导致产生全局最优解。

实际上,贪心算法适用的情况很少。一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。

实际应用

实现框架 从问题的某一初始解出发; while (能朝给定总目标前进一步) { 利用可行的决策,求出可行解的一个解元素; } 由所有解元素组合成问题的一个可行解;

    因为用贪心算法只能通过解局部最优解的策略来达到全局最优解,因此,一定要注意判断问题是否适合采用贪心算法策略,找到的解是否一定是问题的最优解。
总结

贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。

  • 需要证明: 贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

回溯算法

概念
一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径

回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

特点:有“通用解题方法”的美称。

思想

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

   若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。

   而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。
使用
(1)针对所给问题,确定问题的解空间:首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。

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

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

分支限界法

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

回溯法和分支限界法的一些区别

有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决,但是另外一些则不然。也许我们需要具体一些的分析——到底何时使用分支限界而何时使用回溯呢?
搜索算法
所谓“分支”就是采用广度优先的策略,依次搜索E-结点的所有分支,也就是所有相邻结点,抛弃不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,继续搜索。

 选择下一个E-结点的方式不同,则会有几种不同的分支搜索方式。

1)FIFO搜索

2)LIFO搜索

3)优先队列式搜索

回溯法和分支限界法的区别:
  • 方法对解空间树的搜索方式 存储结点的常用数据结构 结点存储特性常用应用

  • 回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解

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


总结

多理解,多理解,多理解。。。。



微信号:

clpaial10201119(Q Q:2211523682)

微博WB:

http://weibo.com/u/3288975567?is_hot=1

gitHub:

https://github.com/al1020119

博客

http://al1020119.github.io/


Comments