循序渐进才能学好算法

在上一篇《设计方法（自然求解）》中讲到第二点设计算法论，那就是大化小，他的本意是指把一个大的问题转换成小问题的算法设计思想，当然除了大化小之外，还存在最优解的问题。下面我们一一来介绍设计方法中大化小设计思想所涉及到的方法。

递推

递推指的是在已知条件的情况下，求解未知结果的一个过程，也就是通过初始值来反复进行某一个运算得到所需结果。

递推的运用其实相当的广泛，比如Fibonacci数列、汉诺塔、骨牌铺方格问题等都可以使用递推来完成（上面的问题也可以使用递归来完成）。

实战中会详细讲解其应用细节，请关注

递归

递归指的是从结果出发，来求解符合条件的最终解。在计算机程序中，也就是函数调用自身来求解符合条件的结果。所以此处的条件必须是一个可以结束的条件，否则导致无线循环->栈溢出。

上述递推的应用场景同样适合递归算法，著名的递归应用是在树、图等操作上，所有这些都是将一个大的问题转化成小问题，然后局部求解的一个过程。

递归的栈溢出，为什么递归会有栈溢出？而递推没有呢？这是一个最常见到的问题了，首先要从函数讲起，函数在调用的过程中，不管是编译器还是解释器或是操作系统，会分出一部分栈空间给变量和函数结果使用，这个过程叫做压栈，而等函数调用完成返回时，会产生出栈操作。所以在每次调用都会和栈进行沟通，会消耗一定的空间和时间，如果频繁的进行沟通，在频繁上加个期限，你自己想想会产生什么，因为操作系统或是分配的栈空间也是有限的。

递归算法在程序研发中经常会使用到，根据实际情况使用，适可而止，不可滥用。因为它很容易产生问题，著名的NASA工程师给火星探测器编程时，有一条不成文的规定，禁止使用递归，你品。

实战中会详细讲解其应用细节，请关注

贪心

贪心算法顾名思义就是一个非常贪婪的算法，想要每个过程都是最好的，从算法的本质上来讲，贪心算法是将一个大问题化解成小的问题，然后对每一个小的问题求最优解，也就是我们常说的局部最优解，最后将所得的局部最优解合成原问题解的过程。

贪心算法的基本思路大概如下：

首先用数学模型来描述问题，也就是对问题建模把问题分成若干个小的问题对每个小问题求最优解把小问题的最优解合并为原问题的解

贪心算法的应用场景参考如下：

背包问题找零钱活动安排均分纸牌

贪心存在的问题，当我们对每一个小问题求最优解的时候，可能忽视了一点，所有最优解合并的时候不一定是最优。其实跟求解最大值和最小值问题正好相反，如果把问题分成小段，求解每一段的最小值和最大值，然后最终获取全局最大或是最小，这个结果是正确的，因为局部最优和全局最优的关系很紧密，并且局部完全能说明全局。所以在正确使用贪心算法的时候，一定要考虑分解出来的小问题是否能覆盖或完全说明全局问题，如果是那使用贪心算法就能完全解决问题。

以上所述思想和下面要讲的动态规划有类似的地方，在现今的机器学习和深度学习领域有广泛的应用，尤其是神经网络算法中，经常会遇到贪心对于局部最优解如何能诠释全局最优的问题（后面讲述机器学习算法时会详细讲解）。

实战中会详细讲解其应用细节，请关注

分支界限法

分支界限法和回溯法都是针对解空间树问题产生的思想，其实应该放在一块去讲解，单独放在大化小，其实有些许勉强，因为所有的设计方法基本思想都存在大化小的问题。

分支界限法是以广度优先搜索或是最小消耗来搜索问题的解空间树方法。听到这里我突然就：

懵逼

什么是解空间树？首先他是一棵树，其次是解空间，解空间就是一个问题所有可能解构成的集合。在日常中我们能看到的数据结构（数组、链表），基本上就是某一个问题的解空间结构。

接下来我们聊聊广度优先，说到广度优先不得不谈及深度优先，这里只是简单的和大家讨论一下，并不准备涉足深度。广度顾名思义就是摊开了来计算，而深度那就是一根筋往里钻的算法

广度：

广度

在顶点A除外，进入二层后，广度会搜索A附近没有被访问过的节点，那应该是B/E，继续来查找B/E周围没有被访问的，以B为主节点，查找到C/D，然后以E为主节点，查找到F。

深度：

深度

在顶点A除外，深度就是搜索A外没有被访问的B，以B为主节点，搜索B周围没有被访问的节点为C，以C为主节点，接下来没有访问元素，回溯到上一级，再查找到D，以D为主节点，没有访问元素，回溯到上一级，再继续回溯到A，查找到E，然后以E为主节点查找到F。

从上面可以看出，广度就是从上至下搜索的一个过程，而深度就是从左到右的一个过程。

回到正题，分支界限法就是通过广度优先方式，首先获取到扩展节点，然后产生所有的儿子节点，在儿子节点中，导致不可行解或者非最优解的儿子节点会被抛弃，其他剩余的儿子节点会放入活节点表中，然后再继续从活节点表中获取扩展节点，依次上面的过程，直到找出所需的解或是活结点表为空为止。这样一想就是一个从上至下查找树的一个过程。

在上述部分涉及到扩展节点，大家就有疑问，扩展节点怎么来的，这里面会涉及队列问题，在后面实战讲解中在和大家共同探讨，请期待。

实战中会详细讲解其应用细节，请关注

回溯

回溯法和分支界限法放在一起来讲，是因为两个有一定相关性，从上面的图上可以看到，回溯法是使用了深度优先搜索来完成解空间树的。

回溯法又称为试探法，他是一个系统的搜索问题解的方法，从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活节点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展节点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点，直至找到所要求的解或解空间中已没有活结点时为止。

回溯经常会用在例如八皇后问题、背包问题，尤其是在搜索相关的问题上经常会遇到（DFS深度搜索）。

实战中会详细讲解其应用细节，请关注

分治

分治顾名思义分而治之，就是把一个问题分解为两个或是多个相同的子问题，然后求解子问题，最终把子问题的解合并获得原问题解的过程，和贪心有些相似。

分治的基本策略在于分解这些子问题，子问题需要和原问题形式相同，然后递归求解子问题，最终合并子问题的解。这些子问题具有最优子结构性质（最优子结构即可用来寻找整个问题最优解的子问题结构），并且相互独立，即子问题不包含公共的子子问题。

分治法的应用场景就比较多，比如我们常见的排序算法（快速排序、归并排序）、二分查找算法、平面点对、大数乘法、傅里叶变换等方面。

实战中会详细讲解其应用细节，请关注

动态规划

动态规划是一个非常著名的算法思想，在很多问题中得到广泛应用，尤其在机器学习中。

动态规划其实是求解一个决策过程的最优化问题，其基本思想是将问题分解成若干小的问题，对小问题进行求最优解，然后从小问题得到原问题的解，和分治法有些类似，不过不同的是动态规划中的小问题不是互相独立的。因为在解决这类问题时，如果使用分治法，那么由于小问题的重复会产生大量的重复计算，而动态规划会将小问题的解进行存储，在必要时取出进行应用。

动态规划中要考虑的几个关键点：

阶段

就是把一个大的问题分解为若干相互联系的小问题，这些小问题就成为阶段。描述这些小问题的变量称为阶段变量，阶段变量一般是离散的（可认为是无序的）

状态

描述各个子问题客观条件或是自然状况，根据实际情况来定，比如最优路径问题，那么状态可以是起点。

无后效性

未来的状态不以过去的状态变化而变化，各阶段每一个状态都是独立的，当所有状态确定后才真正确定整个状态，这也就是动态规划为什么是多变的，并且可以根据问题的不同而出现不同解法的原因。

决策

一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策，描述决策的变量称为决策变量。在制定决策或是调整决策变量时，只考虑当前情况，无需考虑历史，因状态满足无后效性（是不是有点像局部最优呢）

策略

由每个阶段的决策组成的序列称为策略。

以上的概念会比较生硬，没办法算法就是这样，下面举一个简单的例子来说明动态规划的几个关键点，在强化学习中，让机器人走迷宫问题，机器人要走出迷宫，那可以分为很多方向或是走法来完成，动态规划的目的就是找出最短距离或是用时最短。机器人走的每一个步就是一个阶段，那每个阶段中会有特征，比如前后左右、或者是否有障碍物、下一步向哪个方向走，这些都属于状态信息。那机器人要向哪个方向走，肯定不能碰到障碍物吧，在这里就是决策，需要改变上面状态的过程，等机器人走出迷宫后，所有决策的集合就是策略，如果这个策略是我们上面所说的最短距离或是用时最短，那就称为最优策略。

其实动态规划应用及其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果，后面慢慢来说。

实战中会详细讲解其应用细节，请关注

今天先和大家介绍到这里，后面还有最后一个设计方法：迭代法，请关注。