「札记」算法的乐趣

《算法的乐趣》

如果要计算机解决问题，就必须用计算机能理解的方式描述问题。建立问题的数学模型实际上是对问题的一种抽象的表达，通常也需要伴随着一些合理的假设，其目的就是对问题进行简化，抓住主要因素，舍弃次要因素，逐步用更精确的语言描述问题，最终过渡到用计算机语言能够描述问题为止

贪婪法（ greedy algorithm），又称贪心算法，是寻找最优解问题的常用方法。这种方法模式一般将求解过程分成若干个步骤，在每个步骤都应用贪心原则，选取当前状态下最好的或最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好或最优的解。贪婪法的每次决策都以当前情况为基础并根据某个最优原则进行选择，不从整体上考虑其他各种可能的情况。一般来说，这种贪心原则在各种算法模式中都会体现，单独作为一种方法来说明，是因为贪婪法对于特定的问题是非常有效的方法。贪婪法和动态规划法以及分治法一样，都需要对问题进行分解，定义最优解的子结构。但是，贪婪法与其他方法最大的不同在于，贪婪法每一步选择完之后，局部最优解就确定了，不再进行回溯处理，也就是说，每一个步骤的局部最优解确定以后，就不再修改，直到算法结束。因为不进行回溯处理，贪婪法只在很少的情况下可以得到真正的最优解，比如最短路径问题、图的最小生成树问题。大多数情况下，由于选择策略的“短视”，贪婪法会错过真正的最优解，得不到问题的真正答案。但是贪婪法简单高效，省去了为找最优解可能需要的穷举操作，可以得到与最优解比较接近的近似最优解，通常作为其他算法的辅助算法使用。

分治法（ divide and conquer）也是一种解决问题的常用模式，分治法的设计思想是将无法着手解决的大问题分解成一系列规模较小的相同问题，然后逐个解决小问题，即所谓的分而治之。分治法产生的子问题与原始问题相同，只是规模减小，反复使用分治方法，可以使得子问题的规模不断减小，直到能够被直接求解为止。

应用分治法，一般出于两个目的：一是通过分解问题，使无法着手解决的大问题变成容易解决的小问题；二是通过减小问题的规模，降低解决问题的复杂度（或计算量）。给 1000个数排序，可能会因为问题的规模太大而无从下手，但是如果减小这个问题的规模，将问题一分为二，变成分别对两个拥有500个数的序列排序，然后再将两个排序后的序列合并成一个就得到了1000个数的排序结果。对500个数排序仍然无法下手，需要继续分解，直到最后问题的规模变成2个数排序的时候，只需要一次比较就可以确定顺序。这正是快速排序的实现思想，通过减小问题的规模使问题由难以解决变得容易解决。计算N 个采样点的离散傅里叶变换，需要做N 2 次复数乘法，但是将其分解成两个N /2个采样点的离散傅里叶变换，则只需要做(N /2)2 +(N /2)2 = N 2 /2次复数乘法，做一次分解就使得计算量减少了一半，这正是快速傅里叶变换的实现思想，通过减小问题的规模减少计算量，降低问题的复杂度。

分治法的难点是如何将子问题分解，并且将子问题的解合并出原始问题的解。针对不同的问题，通常有不同的分解与合并的方式。快速排序算法的分解思想是选择一个标兵数，将待排序的序列分成两个子序列，其中一个子序列中的数都小于标兵数，另一个子序列中的数都大于标兵数，然后分别对这两个子序列排序，其合并思想就是将两个已经排序的子序列一前一后拼接在标兵数前后，组成一个完整的有序序列。快速傅里叶变换的分解思想是将一个 N 点离散傅里叶变换，按照奇偶关系分成两个N /2点离散傅里叶变换，其合并思想就是将两个N /2点离散傅里叶变换的结果按照蝶形运算的位置关系重新排列成一个N 点序列。 Karatsuba乘法算法的分解思想是将n 位大数分成两部分：a +b ，其中a 是整数幂，然后利用乘法的分解公式：(a +b )(c +d )=ac +ad +bc +bd ，将其分解为四次小规模大数的乘法计算，然后利用一个小技巧将其化解成三次乘法和少量移位操作。最终结果的合并思想就是用几次加法对小规模乘法的结果进行求和，得到原始问题的解。

动态规划方法的原理就是把多阶段决策过程转化为一系列的单阶段决策问题，利用各个阶段之间的递推关系，逐个确定每个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果。

动态规划适合求解多阶段（状态转换）决策问题的最优解，也可用于含有线性或非线性递推关系的最优解问题，但是这些问题都必须满足最优化原理和子问题的 “无后向性”。最优化原理：最优化原理其实就是问题的最优子结构的性质，如果一个问题的最优子结构是不论过去状态和决策如何，对前面的决策所形成的状态而言，其后的决策必须构成最优策略。也就是说，不管之前决策是否是最优决策，都必须保证从现在开始的决策是在之前决策基础上的最优决策，则这样的最优子结构就符合最优化原理。无后向性（无后效性）：所谓“无后向性”，就是当各个阶段的子问题确定以后，对于某个特定阶段的子问题来说，它之前的各个阶段的子问题的决策只影响该阶段的决策，对该阶段之后的决策不产生影响，也就是说，每个阶段的决策仅受之前决策的影响，但是不影响之后各阶段的决策。

曲线拟合（ curve fitting）的数学定义是指用连续曲线近似地刻画或比拟平面上一组离散点所表示的坐标之间的函数关系，是一种用解析表达式逼近离散数据的方法。

遗传算法将问题的解定义为进化对象的个体，对若干个体组成的种群进行选择、交叉（杂交）和变异处理，每处理一次种群就 “进化”一代。只要评估和选择策略合适，经过若干次“进化”之后，种群中就会出现比较接近最优解的个体，对应的就是问题的近似优化解。这就是遗传算法的原理。

基因的编码规则必须满足以下三个条件。完备性：问题空间的所有解在遗传算法中都有编码值与之对应。健全性：遗传算法中的每一个编码值在问题空间中也有对应的值。非冗余性：遗传算法中的编码值与问题空间中的解满足一一对应关系。遗传算法常用的基因编码方式有二进制编码、格雷编码、符号编码、属性序列编码等方式，对于多参数的最优化问题，可用上述方式对每个参数进行编码，然后用级联或交叉的方式组合成最终的基因编码。

在信息论中，汉明距离（ Hamming）是描述两条信息之间相似程度的一个属性。两个长度相等的字符串对应位置上的不同字符的个数就是两个字符串的汉明距离。换句话说，如果将一个字符串通过替换字符的方式变换成另一个字符串，需要做替换的次数就是汉明距离。汉明悬崖是二进制编码的一个缺点，就是相邻整数的二进制代码之间有很大的汉明距离，使得遗传算法的交叉和变异变得难以跨越。

遗传算法中对适应度函数的处理有两种方式，一种是在算法的执行过程中始终使用固定的适应度函数，另一种是在算法的不同阶段使用不同的适应度函数。第一种方法的算法处理简单，但是存在运算初期的早熟问题（也称未成熟收敛问题）和运算后期的竞争区分度不高的问题。所谓早熟问题，就是在遗传运算的初期，少数个体的适应度非常高（可能是局部最优解），这样在遗传过程中，这些个体在下一代中所占的比例很高，使得交叉和变异对种群多样性的作用被严重降低，种群多样性无法保证，最终因为局部最优解的存在而错过全局最优解。所谓竞争区分度不高的问题，是在遗传算法运算的后期，此时种群中多数个体的值都已经非常接近最优解，它们之间的适应度非常接近，互相之间的竞争力几乎相同，随机选择时因为适应度几乎一样导致根据概率选择的过程变成等概率的平均选择。一旦出现这种情况，遗传算法的搜索机制实际上就没有重点搜索区域了，变成了随机的平均搜索，即便算法再第二种方法采用自适应适应度函数或可变适应度函数，在遗传算法的不同阶段使用不同的规则计算个体的适应度，规避使用固定适应度函数可能面临的两个问题。在遗传算法中，这种方式称为适应度尺度变换（ fitness scaling），常见的适应度尺度变换方式有线性尺度变换、乘方（幂）尺度变换和指数尺度变换。对于简单的问题（或没有局部最优解的情况），使用固定的适应度函数即可。

根据 “优胜劣汰”的原理，遗传算法的选择算子都是非均匀选择的，常见的选择策略有以下几种。比例选择（proportional selection）：又称“轮盘赌选择”（roulette wheel selection），是一种回放式随机采样方法，每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值总和的比例。随机竞争选择（stochastic tournament）：又称“随机锦标赛选择”，每次用比例选择方式从群体中选择两个或多个个体进行适应度竞争，适应度高的个体被选中。重复这个过程，直到下一代个体选满为止。最佳保留选择：确切地说，这是和交叉算子与变异算子结合在一起的一种选择策略。首先用比例选择方式选择下一代个体，但是每次都找出上一代中适应度最高的个体，直接替换到适应度最差的个体，并且这个个体不参与交叉和变异运算，确保它能遗传到下一代。排序选择：对群体中的所有个体按期适应度大小进行排序，根据排序结果，按照某种规则计算出每个个体被选中的概率。确定式采样选择（deterministic sampling）：该策略能确保适应度高的个体100%被遗传到下一代。具体的方法是：根据个体的适应度计算群体中每个个体在下一代中期望的生存数目，计算方法是。用Ni 的整数部分确定对应的个体在下一代种群中的生求和得到。按照Ni 的小数部分对个体进行排序，按照从大到小的顺序依次取前M -M' 个个体加入到下一代种群（每个个体的数量是Ni ），最终得到M 个下一代种群。

交叉算子的设计一般由基因的编码方式决定，基本过程就是随机从群体中选择两个个体配对，然后按照一定的交叉规则交换对应位置上的基因片段。基因交叉规则大致可分为以下几类。单点交叉（ one-point crossover）：在配对个体的基因中只随机选择一个点，以随机概率交换这个点对应的基因片段，从而形成两个新个体。两点交叉（two-point crossover）与多点交叉（multi-point crossover）：在配对个体的基因中只随机选择两个或多个点，以随机概率交换每个点对应的基因片段，从而形成两个新个体。均匀交叉（uniform crossover）：又称为一致交叉，对配对个体的基因上的每个点都按照相同的交叉概率交换其对应的基因片段，从而形成两个新个体。算术交叉（arithmetic crossover）：由两个配对个体的线性组合而产生出两个新的个体，该操作对象一般是由浮点数编码表示的基因。

变异算子主要解决两个问题，一个是如何确定变异的位置，另一个是如何进行基因变异。常用的变异算子类型如下。单点变异（ One-point Mutation）：对个体的基因编码随机选择一个点，以随机概率进行变异运算。固定位置变异：对个体基因上的一个或几个固定位置上的基因片段，以随机概率进行变异运算。均匀变异（一致性变异）：对个体基因上的每个片段，都使用均匀分布的随机数，以较小的随机概率进行变异运算。边界变异（Boundary Mutation）：做变异操作时，使用基因编码规则定义的编码边界值（如果有多个边界值，比如同时有最大值和最小值的情况，则根据实现定好的规则选一个或随机选一个）替换原来的基因片段。高斯变异：基因变异的随机概率不是平均分布随机数或普通正态分布随机数，而是采用符合高斯分布的随机数生成器生成随机概率。

除了遗传算子和适应度函数，遗传算法的四个重要参数也会影响结果的求解，这四个参数分别是种群大小 M 、交叉概率Pc 、变异概率Pm 和进化代数T 。种群大小M 表示种群中个体的数量，种群的个体数量决定了遗传算法的多样性。M 值越大，种群的多样性越好，但是会增加算法的计算量，降低运行效率。但是如果M 值太小，会因为遗传多样性降低而导致比较容易出现早熟现象。一般建议M 的取值最小为20。交叉概率Pc 决定了产生新个体的频度，这是保证种群多样性的关键参数之一。交叉概率太小，会导致新个体产生速度慢，影响种群多样性，但是交叉概率也不能太大，过高的交叉概率会使基因的遗传变得不稳定，优良基因比较容易被破坏。一般建议交叉概率取0.4～0.9之间的值，0.8是比较常用的值。变异概率Pm 也是影响群体多样性的参数之一。变异概率太小不利于产生新个体，对种群多样性有影响，但是变异概率太大也会使基因的遗传变得不稳定，优良基因比较容易被破坏。根据遗传学原理，基因突变是一个小概率的事件，在遗传算法中，变异算子对种群的影响也应该远远小于交叉算子。一般建议变异概率取值小于0.2。进化代数T 是遗传算法的退出条件，如果T 太小，会使得遗传算法在种群还没有进化成熟就退出了，自然会影响结果的准确性。当然，T 也不是越大越好，当种群已经接近最优结果的时候，每次进化所产生的变化非常小了，在这种情况下仍然继续进化不仅影响算法的效率，对结果精度的提高也没有太大的帮助。一般建议T 最小进化100代。

遗传算法是一种带启发性的随机搜索算法，它不像传统的搜索算法那样，从单个值开始迭代搜索，按照特定的搜索顺序对整个解空间进行遍历。遗传算法的优点就是一开始就从一大群解中开始搜索，覆盖区域大，有利于找到全局最优解。遗传算法通过基因的变化隐含地对解空间的一部分重点区域进行搜索，从问题的多个解开始并行搜索，对重点区域的选择是通过适应度函数和选择算子的运算来实现的，这也是启发性的体现。所以，不要对遗传算法过分崇拜，这只是一种搜索算法而已，只是比漫无目的的穷举搜索算法 “聪明”那么一点而已，通过较小的计算量获得较大的收益。也不要以为遗传算法是高效算法，只要能用解析的方法直接得到最优解的问题，都不要试图用遗传算法，因为它比穷举搜索高明不了多少。轮盘赌算法是各种随机化算法中常用的随机选择算法，原理简单，实现也简单，但是也存在致命的问题。假如一些选择概率非常小的个体连续出现，就会导致它们集中在一起在“赌轮”上占据一块很大的扇区，那么这块扇区就比较容易被选中，但实际上选择的都是选择概率非常小的个体，这也是轮盘赌算法选择误差比较大的原因，在设计算法的时候需要注意这一点。

RSA算法（Rivest-Shamir-Adleman）是非对称公钥加密体系的开山鼻祖，经过几十年的发展，RSA算法在银行、军事、通信等领域得到了广泛的应用。RSA算法的核心是大整数的模幂运算（Modular Power），模幂运算又称为模乘方运算。用数学表达式表示模幂运算就是： C = A ^ B (mod n )

传统的加密模式一般是信息发送者用特定的密钥对信息加密（加密和解密算法都是公开的），然后将密文传递给接收者，同时还要将密钥告诉接收者，这样接收者就可以用密钥对密文进行解密。这种方式的隐患在于密钥的传递，密钥在传递过程中有可能被截取，此外，密钥分发出去以后就很难控制分发的范围，一旦失控，发出去的加密信息就等于是明文了。

1976年，维特菲尔德·迪菲（Whitfield Diffie）和马丁·赫尔曼（Martin Hellman）在一篇革命性文章“密码学的新方向”（New Directions in Cryptography）一文中提出了一种使用非对称密钥的密码学新方法，可以在不用传递密钥的情况下完成信息的加密和解密。这就是现代非对称公钥体系的基础，在这种体系中，发送者要给接收者传递密文，首先要得到接收者对外发布的公钥，然后用该公钥加密信息，并将加密的信息发送给接受者。接收者受到密文后用自己的私钥对信息解密，在这个过程中，不需要密钥传递，接受者的私钥自己保管，不对外公开。

RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥的一部分。由此可知，密钥的生成是RSA算法的核心，先来看看RSA密钥对的生成过程。 1. 任意选择两个大素数，p 和q ，计算出n =p ×q ，n 又被称为RSA算法的公共模数。 2. 计算n 的欧拉数φ (n )=(p -1)(q -1)。 3. 随机选择加密密钥指数，从[0,φ (n ) -1]中选择一个与φ (n )互质的数e 作为公开的加密指数。 4. 求解与e 对应的解密指数d ，d 和e 满足条件：(d × e )≡1 mod φ (n )。因为e 和φ (n )互素，因此可以利用扩展欧几里得算法求解同余方程，得到唯一整数解d 。 5. 销毁p 和q ，妥善保存私有密钥SK=(d , n )，将公开密钥PK=(e , n )分发给希望给你发送信息的人。由以上过程可知，在p 和q 不可知的情况下，要得到私有密钥的解密指数d ，必须知道φ (n )，而φ (n )必须通过第2步给出的方法计算，也就是说，必须要分解公共模数n ，重新得到p 和q 。对n 的分解是个数学难题，目前没有有效的方法可以快速分解n ，n 越大越难分解，这就是RSA算法的数学原理。以目前计算机的处理能力，当n 大到一定的程度，可以认为是不可分解的，这也是RSA算法安全性的基本保证。

RSA算法的加密和解密其实就是模幂运算，如加密和解密的算法实现代码ModularPower() 函数。假设M 是明文，C 是密文，加密的过程就是： C = Me (mod n ) 解密的过程就是： M = Cd (mod n ) 现在举个经典的密码学示例来解释一下RSA加密和解密的过程。爱丽丝希望鲍勃给她发送的信息进行加密，她首先选择两个素数p =11和q =13，计算它们的乘积，得到公共模数n =143，同时计算出n 的欧拉数φ (n )=120。接下来爱丽丝需要选择一个小于119（φ (n )-1=119），且与φ (n )互素的数作为加密指数e ，爱丽丝选择e =7。然后爱丽丝需要求解同余方程7d ≡1 mod 120，得到d =103。最后，爱丽丝销毁p 和q ，将(7,143)作为公开密钥发送给鲍勃，将(103,143)作为私钥自己保存。鲍勃需要发送信息M =85给爱丽丝，他先用爱丽丝的公钥对M 进行加密，得到密文C = 857 (mod 143) = 123，然后将密文C =123发送给爱丽丝，爱丽丝得到C 后，用私钥对C 进行解密，得到明文M =123103 (mod 143)=85。以上就是整个RSA加密和解密的过程，其核心就是模幂运算，使用的过程很简单，但是简单并不意味着不安全。

人们在提到 RSA加密的时候，都会附带一个很重要的参数，就是RSA密钥长度，比如1024比特的RSA密钥，2048比特的RSA密钥等。这里的1024和2048实际上是RSA密钥中公共模数n 的二进制位长度，n 越大就越难分解，这就是通常人们会认为1024比特的RSA密钥要比512比特的RSA密钥更安全的原因。但是从数学上看这个问题，对n 的分解并没有被证明是NP问题，也就是说，增加n 的长度就能提高安全性还没有被用数学的方法证明（当然，也没有被证伪）。当然，RSA加密的安全性是由很多因素决定的，比如组成n 的两个随机素数p 和q 的选择就很有讲究。p 和q 必须是随机生成的强素数，绝对不能用别人用过的素数，或者从某个素数表中选择p 和q 。p 和q 的差值应该尽量大，增加分解n 计算的难度。加密指数e 的选择也很重要，e 越大计算量就越大，为了加快加密计算的速度，RSA算法对公钥e 选择通常是3、5、17、257或65537。X.509证书体系建议使用65537，PEM建议使用3，PKCS#1建议使用3或65537。但是使用太小的e 会引入小指数攻击问题，在原始数据中填充随机数值，使得me (mod n ) ≠ me ，可以有效地抵抗小指数攻击。因此使用RSA加密数据通常都会指定随机值填充模式，单纯的直接用模幂算法加密数据是不安全的。

签名的验证就是利用发送者的公钥对加密信息解密，然后比较解密后的信息是否是原始信息。数字签名的一般过程是：用户 A用选择的哈希算法计算出文件M的HASH值，然后用自己的私钥对这个HASH值进行加密，这个过程就是“签名”。现在A把文件M（不加密）和加密后的HASH值发给B，B于是用A的公钥对HASH值解密，然后再计算文件M的HASH值，比较文件的HASH值是否和A发来的HASH值一样，如果一样则说明文件确实是A发来的，并且文件没有被修改。否则就说明文件不是A发出的，或者文件在传递过程中被篡改了。由此可知，数字签名除了证明文件M是A发出的，还可以验证文件M是否被其他人（包括接受者）篡改或伪造。身份验证的过程和签名的过程类似，当B需要验证A的身份时，就将一段信息发给A，请A对其进行签名（加密）。得到A的签名后，B使用A的公钥对签名解密，验证是否和自己发给A的信息一致，以此验证A身份。其他人没有A的私钥，无法伪造A的签名。和RSA的加密一样，使用RSA签名一样需要面对各种攻击，因此，不要随便对某一个人发过来的东西进行签名（有潜在危险）。如果必须要这么做（比如为了验证身份），最好先用哈希算法计算出信息的HASH值，然后对HASH值进行签名。

Dijkstra算法是典型的单源最短路径算法。Dijkstra算法适用于求解没有负权边的带权有向图的单源最短路径问题，所谓的单源可以理解为一个出发点，Dijkstra算法可以求得从这个出发点到图中其他顶点的最短路径。由于Dijkstra算法使用广度优先搜索策略，它可以一次得到所有点的最短路径。Dijkstra算法在各种地图软件中得到了广泛的应用，假如我们把一个地区的交通网用带权有向图表示，其中城市就是图的顶点，边就是连接城市之间的道路，边的权就是城市之间的距离，就可以用Dijkstra算法求解从一个城市到另一个城市的最短路径。由此可见，地图软件中的这个实用功能背后就是简单的Dijkstra算法在支撑。

A算法兼有Dijkstra算法和BFS算法的特点，在速度和准确性之间具有很大的灵活性。除了调整G (n )和H (n )获得不同效果，A算法还有很多提高效率的改进算法。比如在地图很大的情况下，可以使用二叉堆来维护OPEN表以获得更好的效率。对于环境和权重都不断发生变化的动态网络，还有动态A算法（又称D算法）。 Dijkstra算法在地图和导航软件中得到了广泛的应用，A*算法在游戏软件中也得到了广泛的应用，它们都是很简单的算法，但是却得到了广泛的应用，这也是小算法解决大问题的现实例子。

编写一个自动玩俄罗斯方块游戏的 AI算法就是要做两件事情：一是穷举板块的所有摆放形态和摆放位置，二是用评估函数对每种摆放方法进行评估，根据评估结果选择一个最佳摆放位置。

博弈树搜索是各种棋类游戏 AI算法的基础，极大极小值（Min-Max）搜索算法是各种博弈树搜索算法中最基础的搜索算法。假如MAX和MIN两个人在下棋，MAX会对所有自己可能的落子后产生的局面进行评估，选择评估值最大的局面作为自己落子的选择。这时候就该MIN落子，MIN当然也会选择对自己最有利的局面，这就是双方的博弈，即总是选择最小化对手的最大利益（令对手的最大利益最小化）的落子方法。作为一种博弈搜索算法，极大极小值搜索算法的名字就由此而来。

估值函数的作用是把一个棋局量化成一个可直接比较的数字，这个数字在一定程度上能反映取胜的概率。棋局的量化需要考虑很多因素，量化结果是这些因素按照各种权重组合的结果。这些因素通常包括棋子的战力（棋力）、双方棋子占领的空间、落子的机动性、威胁性（能吃掉对方的棋子）、形和势等。不同的棋类游戏会根据规则选择合适的参考因素与权重关系，组合出一个量化的评估结果。权重关系组合在很大程度上决定了估值函数的价值，为了获得一个更好的组合关系，研究者通常会收集成千上万的棋局对自己的估值函数进行 “训练”，通过反馈调整权重组合关系。