2018年度五年级 第二讲：减而治之

第一讲我们由人工智能的应用，引出对算法的探讨，主要讨论了较为经典的“欧几里得算法”、“N皇后问题和回溯算法”、“排序算法”。这次课我们将讨论算法和解题中比较重要的思想 - 减而治之。

[01]减而治之 - 减小迷面

我们上次课讨论了AlphaGo Zero、人脸识别、欧几里得算法、回溯算法，其实这些问题在求解过程中都存在一个共性，就是用算法策略减小谜面。在AlphaGo Zero的例子中，围棋的所有情况数大到让计算机也难以枚举，因此AlphaGoZero必须要通过神经网络帮助判断哪些路线要及时停止搜索，在有限的几种选择中判断出对当前情形最有利的方案。在人脸识别中，计算机通过提取特征点进行匹配，而不是每个像素点分别匹配，解决了不同光照、角度拍摄，或是图像变换所造成的难以比对的情况。这是从连续、无限的数量比较，转变为了有限的特征点匹配，因此也进行了谜面的减小。欧几里得算法，通过递归操作，让每一次残留的长方形逐渐变小，过程中保证长方形长和宽的最大公约数不变，从而逐步降低求最大公约数的难度。N皇后问题中，回溯算法本身就是一种及时剪枝，减小搜索数据量的方法。

“减而治之”(decrease - and - conquer)策略，就是要从给定问题的解及其较小规模谜面的解之中找到某种关系。一旦找到，这种关系就可以自然导向某种递归算法(recursive algorithm)，从而将问题减小为一系列的、规模越来越小的谜面，直到可以一下子解决。

......

[03]经典问题 - 猜数字

问题是二分法的一个经典例子。B提的问题可以是“你想的数是**吗？”，然后逐一排除，直到猜出答案。这种方法就是穷举法。显然我们要尽量避免穷举法，因为效率太低。

我们能否通过一次提问排除更多的数呢？当然可以，只需要将是否“=”，改为是否“>”或"

那我们第一个问题确定多大范围才合适呢？或者说，我们确定多大范围才能够确保用剩下19个问题能够猜出这个数。上面的问题可以转变为，19个问题最大可以猜出多大范围的数？这就要涉及到，怎么猜，才是最有效的方法。为了找出最快的算法，我们可以先假定一个范围，例如0~100. 那我们第一次应该问的问题是“选择的整数小于50吗？”，这样就能够一次排除一半的范围。接下来，再在剩余一半的区间，继续问相似的问题，让问题每次的范围都减半。这种方法就是二分法。

那使用二分法，19次提问能够确定多大范围的数呢？我们可以从最后往前推，1个问题可以确定2个数，2个问题能确定2^2=4个数，……，19个问题能确定2^19=524288个数。也就是说，如果A心中所想的数大于524288，B通过问19个问题就无法确保能猜出该数（第一个问题得用于确保在524288以内）。

上面的探索过程在2个层面体现了“减而治之”：

1.二分法每一次使用，都会将问题的规模减

半，一直减小到能直接解决问题；

2.我们在探索19次能够猜出多少数字使，从最

小规模往回推，这是减而治之的逆向使用，有时又被称为“增量法”（incremental approach）。

......

课程地点：

上午：世纪城时雨园7号楼2E

下午：五道口九方学校

时间安排：

2018年1月22日下午14:00-15:45

2018年1月28日上午09:30-11:15

主讲老师：

陈硕（孙维刚教育研究院，清华大学）