《算法图解》之动态规划与K最近邻算法

说明：以下内容均参考：[美]Aditya Bhargava所著的《算法图解》

动态规划

动态规划：将大问题分解为子问题，利用子问题的解逐步解决大问题。

动态规划可以帮助在给定约束条件下找到最优解

每个动态规划算法都从一个网格开始；

单元格中的值通常就是要优化的值；

每个单元格都是一个子问题。

动态规划问题的难点：

（1）网格的行和列都代表什么？

（2）在动态规划中，我们需要将某个指标最大化。面对一个具体的问题，这个需要最大化的指标是什么？

在这一步，还需要考虑的是：行与行之间的单元格、列与列之间的单元格及对角线上的单元格之间是如何影响的，这个影响关系是需要根据具体的问题自己去挖掘出来的；

（3）根据（1）（2）两步，推导出单元格之间的计算公式。每个动态规划问题的单元格计算公式可能都是不一样的。

如，背包问题中的计算公式为：

# 当前单元格的值等于上方单元格的值与(当前商品的价值 + 剩余空间的价值)中的最大值
cell[i][j] = max(cell[i-1][j], value + cell[i-1][j-k])

寻找最长公共子串的计算公式为：

if word_row[i] == word_column[j]:
    cell[i][j] = cell[i-1][j-1] + 1 # 如果行与列的字母相同，就让当前单元格的值等于左上方单元格的值加1
else:
    cell[i][j] = 0 # 否则，将当前单元格的值置零

寻找最长公共子序列的计算公式为：

if word_row[i] == word_column[j]:
    cell[i][j] = cell[i-1][j-1] + 1 # 如果行与列的字母相同，就让当前单元格的值等于左上方单元格的值加1
else:
    cell[i][j] = max(cell[i-1][j], cell[i][j-1]) # 否则，就取左方或上方单元格的最大值

其中，、分别表示行索引和列索引。注意问题的最终答案并不总是出现在表格的右下角，要根据具体问题具体分析。

动态规划不能解决的问题：

（1）动态规划无法处理相互依赖的情况。仅当每个子问题都是离散的，即不依赖于其他子问题时（即相互独立），动态规划才管用；

动态规划当前问题的解至多只可能涉及两个子问题的解，只是这两个子问题的解又可能嵌套包含其他至多两个更低一级的子问题的解。

费曼算法的三个步骤：

（1）将问题写下来；

（2）好好思考；

（3）将答案写下来。

K最近邻算法

K最近邻（k-nearest neighbours，KNN）算法主要用于分类和回归。

分类就是编组，回归就是预测结果。

一、KNN算法用于分类

原理：找出里目标最近的k个邻居，根据这k个邻居中出现最多的类别来讲目标进行分类。但如何衡量两个对象的相似程度？这就要用到特征提取。

特征提取意味着将目标转换为一系列可比较的数字，能否挑选合适的特征事关KNN算法的成败。

两点之间的距离可以有两种度量方法：

（1）欧氏距离：

（2）余弦距离：

不计算两个矢量的距离，而比较它们的角度。

利用KNN可以进行分类的原理，可以创建简单的推荐系统。

二、KNN算法用于回归

原理：和分类一样，首先要先找到离目标最近的k个邻居，然后计算着k个邻居的平均值，以此作为当前目标的回归（预测）值。

KNN算法必须要挑选合适的特征，这些特征没有固定的形式，必须考虑到各种需要考虑的因素，具体问题具体分析。

三、OCR（Optical Character Recognition，光学字符识别）的一种实现方法——KNN

原理及步骤：

（1）首先浏览大量的数字图像，将这些数字的特征提取出来（这一过程称为训练）；

（2）然后，遇到新图像时，提取该图像的特征，再找出它最近的邻居都是谁。

一般而言，OCR算法提取线段、点和曲线等特征。遇到新字符时，可从中提取同样的特征。

四、创建垃圾邮件过滤器——朴素贝叶斯分类器（Naive Bayes classifier）

原理及步骤：

（1）首先需要使用一些数据对分类器进行训练；

（2）然后，由朴素贝叶斯分类器计算出邮件为垃圾邮件的概率。

字典的优势是处理时间非常快（时间），缺点是当存储的内容过多时会消耗大量的空间。