[科普中国]-算法分类

简介

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。目前国内外有关的研究和科学文献中对于算法分类这个术语还没有明确定义，算法分类简单可以根据算法设计原理、算法的具体应用和其他一些特性进行分类。可分为基本算法或根据具体应用领域进行分类，在机器学习中，按照学习方式，常把算法分为监督学习算法、非监督学习算法及半监督学习算法。按照图论的算法进行分类，算法可以分为哈夫曼编码、树的遍历、最短路径算法、最小生成树算法、最小树形图、网络流算法、匹配算法。

算法算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

一个算法应该具有以下五个重要的特征：

算法有穷性（Finiteness）

算法的有穷性是指算法必须能在执行有限个步骤之后终止；

算法确切性(Definiteness)

算法的每一步骤必须有确切的定义；

算法输入项(Input)

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

算法输出项(Output)

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

算法可行性(Effectiveness)

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。2

基本算法枚举在数学和计算机科学理论中，一个集的枚举是列出某些有穷序列集的所有成员的程序，或者是一种特定类型对象的计数。这两种类型经常（但不总是）重叠。

枚举是一个被命名的整型常数的集合，枚举在日常生活中很常见，例如表示星期的SUNDAY、MONDAY、TUESDAY、WEDNESDAY、THURSDAY、FRIDAY、SATURDAY就是一个枚举。 枚举的说明与结构和联合相似，其形式为：

enum 枚举名{ 标识符①[=整型常数], 标识符②[=整型常数], ... 标识符N[=整型常数], }枚举变量;如果枚举没有初始化，即省掉"=整型常数"时，则从第一个标识符开始，顺次赋给标识符0, 1, 2, ...。但当枚举中的某个成员赋值后，其后的成员按依次加1的规则确定其值。

搜索宽度优先搜索

宽度优先搜索算法是沿着树的宽度遍历树的节点，如果发现目标，则算法中止。属于盲目搜索。

深度优先搜索

深度优先搜索沿着树的最大深度方向生成节点并与目标节点进行比较，只有当上次访问的节点不是目标节点，而且没有其他节点可以生成的时候，才转到上次访问节点的父节点，然后搜索该节点的其他子节点。因此深度优先搜索也称为回溯搜索。它既不是完备的，也不是最优的。有时候，某些特定的问题会产生大量重复的节点。例如“八数码”问题就是这样的，当每次运用向上、向下、向左、向右移动空格的算符时，可能产生与已经产生的节点重复的节点。当再次搜索到这个重复节点时，由于应用的算符基本一致，还会产生重复，所以为了节约时间和存储空间，往往在深度优先算法中设立一个机制，用来删除这些重复的节点，以提高效率。

迭代加深搜索（ID搜索）

对深度优先搜索进行了一定改进，对搜索树的深度进行控制，即有界深度优先搜索。

在程序找到目标之前，通过迭代不断增大d以保证完备性和最优性。虽然会有不少重复搜索，但是鉴于每增加一次d，则搜索的时间复杂度会以指数级别增加，所以重复搜索的时间可以忽略，亦可以与A*算法结合（即IDA*搜索算法）来剪枝。

迭代加深搜索通常用于那种搜索树又深又宽、但是解并不是很深的情况，这时广度优先搜索会超空间，而深度优先搜索会超时。这时迭代加深搜索很有用，可是说是在用递归方法在实现广度优先搜索。

启发式OR图搜索算法

爬山算法

模拟退火算法

最好优先

通用图

A*

约束满足搜索

搜索策略还可以指在使用搜索引擎中所使用的策略，它通常是搜索之母，一个好的搜索过程必定有一个好的搜索策略来支持。

根据学习方式的分类监督学习：输入的数据为训练数据，并且每一个数据都会带有标签，比如“广告/非广告”，或者当时的股票的价格。通过训练过程建模，模型需要作出预测，如果预测出错会被修正。直到模型输出准确的训练结果，训练过程会一直持续。常用于解决问题有分类和回归。常用的算法包括逻辑回归和BP神经网络。

无监督学习：输入的标签没有数据，输出没有标准答案，就是一系列的样本。无监督学习通过推断输入数据中的结构建模。这可能是提取一般规律，可以是通过数学处理系统系统的减少冗杂，或者根据相似性组织数据。常用于解决的问题有聚类，降维和关联规则的学习。常用的算法包括了Apriori算法和K均值算法。

半监督学习：半监督学习的输入数据包含标签和不带标签的样本。半监督学习的情况是有一个预期中的预测，但是模型必须通过学习结构整理数据从而做出预测。常用于解决的问题是分类和回归。常用的算法是对所有的无标签的数据建模进行的预测算法（可以看做无监督学习的延伸）。