算法引论 笔记2
17 Jul 2013 by LelouchHe
说明
本篇主要讲解算法引论第二章内容
归纳法
归纳法是比较常用的数学工具了,其最大的特点是只适用于自然数度量的问题,即问题的规模或者结构是以自然数为量纲的.常见的问题绝大多数都是如此,毕竟计算机处理的问题大部分还是实际问题,实际问题的规模一般都是整数形式的
归纳法的形式有许多变形,但是有两个关键点:
- 归纳基础: 即归纳的起点,对于自然数度量的问题,一个常见的归纳基础是度量为0或1的情况(设n为问题的规模),也就是n=0或1时的基础情况.当然,归纳基础并不只是0/1,对于一些复杂问题,其归纳基础可能有k种,那么就需要一一考察k种基础情况.归纳基础是归纳的出发点,必须严格考察
- 归纳步骤: 即归纳扩展的途径,一个常见的情况是当假设规模为n时为真,通过归纳步骤得到n+1的情况.这一步通常是归纳的难点所在,有的时候很难构造类似的步骤从小规模扩展到大规模,从而完成问题的解决.后面会看到很多有用的技巧
必须注意的是,归纳的两个关键是缺一不可的,很多错误归纳就是单单依赖于某一点而忽视另一点导致的错误(会有举例说明)
归纳有以下几种变形:
普通归纳法
- 对于带有参数n的命题P,当n=1是P成立,并且如果对于每一个n(n > 1),若n-1时P成立可以推导出n时P也成立;那么对于任意自然数,P均成立
- 归纳基础: n=1时P成立
- 归纳步骤: $n - 1 \Rightarrow n$
可以看到,归纳基础是简单可验证的,而归纳步骤是抽象的,这也正反映了归纳法的难点所在
加强归纳法
- 对于带有参数n的命题P,当n=1是P成立,并且如果对于每一个n(n > 1),若任意小于n时P成立可以推导出n时P也成立;那么对于任意自然数,P均成立
- 归纳基础: n=1时P成立
- 归纳步骤: $k < n \Rightarrow n$
加强归纳法的”加强”在于,不仅仅利用n之前的一个命题成立,而是利用n之前的所有命题的成立,来作为归纳步骤的前提.当 遇到某些问题,无法仅依靠一个成立来进行推导时,可以参考加强的归纳法
多路归纳法
- 对于带有参数n的命题P,当n=Bi是P成立,并且如果对于每一个n(n > 1),若任意小于n时P成立可以推导出n时P也成立;那么对于任意自然数,P均成立
- 归纳基础: n=Bi时P成立
- 归纳步骤: $k < n => n$
这个其实类似于普通归纳法,只不过对归纳基础做了延伸,此处的归纳基础可以从大于1的地方出发,同时,也可以有多个归纳基础,比如命题P有不同的情景,针对不同n,那么这些不同的基础情况就需要一一判断.最为关键的是,如果归纳步骤成立,只能证明由归纳基础经过归纳步骤得到的n的情况下,P成立.
比如归纳基础是n=1,归纳步骤利用的是$n => 2 n$,那么最后只能证明n为2的幂次方时P成立,其他情况无法证明.
这种时候,很容易冲动的认为问题解决了,所以需要慎之又慎
有趣的问题
书中举的一些例子非常有趣,虽然有的可能trival,但提供的思路都非常值得深思
平面内区域计数
问题
平面内直线,任意两条不平行,任意三条不共点,就称这些直线处于一般位置.
求n条位于一般位置的直线,能将平面划分为多少个区域
解决
非常自然的第一步肯定是随手画画(这个应该是非常自然的),实验的结果如下(直线数量为n,区域数量为t):
- n = 1: t = 2
- n = 2: t = 4
- n = 3: t = 7
- n = 4: t = 11
一个比较显眼的可能的规律是$T(n) = T(n - 1) + n$,至少前4个是成立的,这些就是归纳基础(当然,n=1才是基础,$T(1) = 2$,不需要证明),接下来需要利用归纳步骤尝试证明这一假设(尝试而已,有可能失败的),用文字说明即为:
- 平面上n-1条一般位置的直线,添加一条类似直线后,区域增加了n个
可以看到,此处的假设已经和原先的问题(求具体多少个区域)不一样了,这是因为猜想的假设和问题本来就不同.这也可以看出,假设和问题不一定要完全一致,所谓殊途同归即可
归纳步骤
首先是让假设成立,n-1的时候假设是成立的,即n-2条直线,添加1条之后,区域增加了n-1个.
然后,对于目前的n-1条直线,添加第n条直线,由于一般位置的限制,第n条直线肯定与剩余的直线相交于n-1点(不平行,不共点),将第n条直线划分成了n段,每段都会将所在区域分割成两部分,所以会增加n个区域
最后得证
当然,这是我的证明方法,非常的普通和自然,但是这样的证明固然正确,但是比较难想(我也是看了其他书才知道这样证明的),比如怎么去想第n条直线的交点和分割呢?不是求区域的分割么?直线分割真的会增加区域么?那么多直线,怎么明白的判断呢?
针对这个问题,是比较好解决的,因为问题比较简单,但也可以看到,这个方法并不很适用于其他复杂的问题(n条直线本来就有点乱,要是问题本身再乱点,岂不是更没头绪)
不过其实观察整个证明过程,我们并没有使用到归纳的方式,而是忽略了n-1的情况,直接来证明n的时候的命题.自然.归纳法中不排斥这种做法,但是就归纳本身而言,此处并不是很合适.
所以书上的证明才是非常精妙的归纳证明
精妙的证明
首先第1步是相同的,让假设成立
然后,添加第n条直线,情况复杂了,怎么能回到原来的情况呢?显然,去掉一条即可.去掉第n条,额,有病啊.所以要去掉原来n-1条中的某条,假设是第n-1条.这样,就剩下了n-1条直线,假设是成立的,那么最后添加的这第n条相当于是第n-1条,于是增加了n-1个区域(这是假设的前提).此刻,再把删掉的第n-1条直线加回来.一减一加对于原来的n-2条直线没有变化,变化的只有第n-1条和第n条的关系.二者必然交于单独的一点,这点有两个可能,一个可能是位于一条射线上(在边缘),另一个则是在线段中,但不论哪个,都会把原来直线划分的区域增加1个,所以添加第n条直线共增加n个区域
最后得证
比较神奇的是第二个步骤,不同于第一种证明方法中的直接证明,此处的着眼点在于回归原始假设,通过去掉一条直线,回到原来的情况(即相当于在n-2条直线时,添加1条直线),然后再补全原来去掉的直线.一减一加对于其他直线没有影响(因为它们面对的情况完全没变),唯一的不同在于第n条直线(因为一开始假设的是第n条直线和第n-1条直线没有关系,现在就有了).
这样做的好处是什么呢?自然是减小问题的复杂度.原先需要考虑的是第n条直线和原先n-1条直线的关系,现在只需要考虑2条直线关系即可,大大简化了归纳步骤
最终结论
此处的归纳只得到了递归式$T(n) = T(n - 1) + n, T(1) = 2$,还需要将其转化为具体的数量值.这个就比较简单了,此处不赘述了(递归公式求解而已)
总结
有两点需要深思:
- 归纳的不是问题结论,而是适合归纳的,而且可以推导出问题结论的间接假设.选取的这个假设常见的是递归式,但不绝对
- 重复利用归纳假设,不仅仅在证明的第一步使用假设,在归纳步骤的所有阶段都可以使用,只要可以简化归纳步骤即可.如何转化为假设情况,和如何从这里再次回来,都是需要考量的地方
简单着色问题
问题
平面上任意条直线构成的区域可以仅使用两种颜色进行着色
解决
自然还是利用归纳法来处理这个问题
归纳法的前期步骤肯定还是试错,手动的画一些直线来判断一下结论(n为直线数量,t为需要的颜色数量):
- n = 1: t = 2
- n = 2: t = 2
- n = 3: t = 2
其实可以看到,由直线划分的区域最多是两两相邻,这个可以很容易的从图上看出来,由于边界是直线,而直线最多只能分割两个区域,所以”着色问题”的结论是显而易见的.不过我们这里来使用归纳法来处理问题
首先,假设对于$k < n$条直线划分的区域,可以由两种颜色着色
然后,添加第n条直线,由于n-1条直线时命题成立,此处只要证明着色仍然有效即可.考虑第n条直线的穿越情况:
- 第n条直线穿过的是直线间交点,那么不会带来额外的区域,因此只要原有区域着色有效,现在还是有效的
- 第n条直线分割了原有的区域.对于原先是一个区域的两个新区域,原先肯定是一个颜色,那么此时只要反转其中一个区域颜色即可;对于原先本来就相邻的区域,它们的颜色本来就是不同的两种颜色,那么现在可能:1. 保持原色,还是不同, 2. 同时被反转了,还是不同.
最后得证
要点
可以看到,本问题的关键在于第二步中的反转操作,如何可以保证2.2的情况呢?自然,如果随意的反转的话,肯定是不可能的,那么我们规定特定的反转顺序,比如直线某侧的区域反转即可.这样就保证了2的情况,要不保持原色,要不同时反转
这个归纳的要点在于,依赖归纳假设,在归纳假设的基础上进行结论的调整,不是直接的证明命题,而是说第n条的时候,原来结论不变,从而间接的证明命题.这个思路和上一个问题的思路有着明显的不同.”划分区域”问题重在回归,本题重在保持,但二者都是在原有归纳假设的基础上,巧妙的利用一些手段,将问题推导至假设上来解决问题的,所谓殊途同归
三角加法问题
问题
考虑下面的三角加法
\[1 = 1 3 + 5 = 8 7 + 9 + 11 = 27 13 + 15 + 17 + 19 = 64 21 + 23 + 25 + 27 + 29 = 125\]试求第n行的和的表达式
解决
首先尝试还是看一些简单的例子,从问题给出的一些例子来看,结果应该是立方数列,即第n行的和为$n ^ 3$
我们尝试来证明这一点,还是利用归纳法,归纳假设是第n行的和为$n ^ 3$
归纳基础是成立的,甚至,$n \le 5$时都是成立的(从题图可知)
首先,假设其成立,即$k < n$时,第k行的和为$k ^ 3$,设其和表达式为$S(k)$
然后,可以看到,$S(n - 1) = (n - 1) ^ 3$,而要证明的是$S(n) = n ^ 3$.归纳的法的核心时利用以前成立的假设推导未知,我们如何将两行联系起来呢?自然,如果我们证明了$S(n) = S(n - 1) + [n ^ 3 - (n - 1) ^ 3]$,那么根据归纳假设,证明就完成了(看到如何利用归纳假设了么?)
所以问题转化为证明$S(n) = S(n - 1) + [n ^ 3 - (n - 1) ^ 3]$,这样既利用了原有的归纳假设,同时也简化了问题考量(单纯看第n行能有何结论呢?)
问题转化
目前的归纳假设为$S(n) = S(n - 1) + [n ^ 3 - (n - 1) ^ 3]$,归纳基础显然成立(考察n=2的情况即可)
首先,假设其成立
然后,考虑第n行的情况,计算两行之间的差值,一个自然的想法是从每个数的差来入手,遵循对应关系,观察下每行对应的数之间的差值.第n-1行有n-1个数,那么第n行的每个数都比上一行对应的数大$2 (n - 1)$(都是奇数,间隔n-1个),那前n-1个数的总差值为$(n - 1) \cdot 2 (n - 1) = 2 (n - 1) ^ 2$,那么两行差值还剩下$[n ^ 3 - (n - 1) ^ 3] - 2 (n - 1) ^ 2 = n ^ 2 + n - 1$,如果第n行的最后一个数(即多出的那个数)等于这个的话,假设就成立了
所以,问题又转化为证明第n行最后的数(设为$L(n)$)等于$n ^ 2 + n - 1$
问题转化2
目前的归纳假设为$L(n) = n ^ 2 + n - 1$.归纳基础显然成立(考察n=1的情况即可)
首先,假设其成立
然后,考虑第n行,目前知道的情况是$L(n - 1) = (n - 1) ^ 2 + (n - 1) - 1$,$L(n)$与$L(n - 1)$间隔了n个数(一一对应的是间隔n-1个数,最后一个数还要多1),相差为$2n$,那么$L(n) = L(n - 1) + 2 n = n ^ 2 + n - 1$,假设成立
最后问题得证
问题回溯
由原始问题转化的最后一个问题得证,向前回溯,既可以得到原始问题的证明.所以原问题亦得证
总结
可以看到,本问题的解决,使用了三次问题转化与归纳法,从原始的求值问题,到求差值问题,再到求某一特殊值,每一步都利用归纳进行推导.问题当然很naive,不过这表达了一个道理,求解问题时不能总试图一蹴而就,求解过程很有可能有波折,通过转化,一步一步得到问题的解
以前遇到类似波折的时候,我的第一个想法是”我又做错了”,然后就放弃求解努力了.这样不好,很容易错过真正的解决之道
一点思考
这个问题让我重新思考”归纳基础”问题,例如本题的一个归纳基础为$S(n) = S(n - 1) + [n ^ 3 - (n - 1) ^ 3]$,这个归纳基础是什么?n=2?还是n=1?自然,n=2是最小的使假设成立的case(n=1不在定义域),但我们要牢记一点:
- 归纳假设不是假设的一部分,而是归纳的前提和成立的第一步
这个和归纳假设的验证不一样.有了归纳假设,第一步肯定是验证其是否成立,自然要举几个naive的例子看看,比如此处的n=2/3/4/5等,这些是验证归纳假设的case,而不是其基础.
上文有些谬误,此处就不加修正了,因为正确的想法就是从这些错误的结论得来的,所以尽量原汁原味吧.
还有一个问题,即问题转化时,归纳假设可能会变,但是归纳基础不能变.不能一次从1开始,另一次从2开始,这样会导致归纳的出错(前提在变,谁知道这些前提之间有无错误之处呢?).切记切记.
不等式证明
问题
证明以下不等式成立:
\[\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots + \frac{1}{2 ^ n} < 1\]解决
还是老方法,考察一些例子(随手画画),基本可以确定命令应该是成立的
下面就利用归纳法来证明.归纳的基础是n=1,此时显然成立.
首先,假设其成立,即$k < n时,\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots + \frac{1}{2 ^ k} < 1$
然后,考虑n的情况.此时,如果对n-1的式子直接加上新增的项($\frac{1}{2 ^ n}$),是显然不成立的,因为从原式我们并不知道整个和式多接近1,随便的加上一项,很有可能是违反命题了.那怎么给第n-1项添加一项呢?
不能添加最后一项,那可以试试第一项,即$\frac{1}{2}$
“是不是疯啦??1/2大好多诶,岂不是越来越大了么?”
自然,我们没有疯,添加第一项的前提是可以构造出余项,即从$\frac{1}{4}$开始,怎么得到呢?
\[\frac{1}{4} + \frac{1}{8} + \cdots + \cdots + \frac{1}{2 ^ n} = \frac{1}{2} (\frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2 ^ (n - 1)}) < \frac{1}{2}\]自然,在这个基础上加上$\frac{1}{2}$肯定是满足条件的,对不?
最后问题得证
总结
从这个问题能看到什么呢?
- 不要想当然的把归纳法只用于最后一项,虽然是在处理n的情况,但不代表在利用归纳假设的时候只能把n当做最后一项来处理,也可以试试第一项,或者其他特殊项(这里涉及到归纳顺序问题了,以后会详谈)
- 如何利用归纳假设,是个很微妙的问题,比如此例中,第n-1个不等式可以看做第n个不等式的前n-1项(这个也是普遍常见的看法),也可以看做后n项的1/2.不论那样,都是利用归纳假设.解决问题需要open,不要拘泥于自认为的规则
欧拉公式
问题
欧拉公式是关于平面上的连通图的.连通图表示图上任意两点之间有路径,或者直观意义上的”一整个图,没有单独部分”.
节点和边比较好理解,面的概念比常识中多一点,即整个图形外部的区域也算一个面.
欧拉公式如下:
任意一张连通平面图的节点数(V),边数(E)和面数(F)的关系是$V + F = E + 2$
分析
这个问题比较怪.以往的问题都是最多两个变量(n和待求值),待求值可以看做单变量n的函数,在进行归纳的时候也比较直接,使用唯一的变量n即可.
但这个问题不同,本身存在三个变量,即使我们认为其中之一为待求量,还有两个变量需要处理.现在,我们就不能确定究竟使用哪个来作为归纳变量了.
怎么办?
其实这个困难和上一个题目类似,都是归纳中有了”波折”,但此时不能放弃,就像上一题一样,虽然经过三次转换,但最后解决了问题.本题也是,有两个变量的话,那我们就选一个作为开始,看看能否解决
解决
可以先绑定一个变量,然后通过归纳考察另外两个变量的关系,但绑定哪个变量呢?
可以首先绑定最为不常见的变量,把不常见的变量固定,可以一定程度上简化问题的解决.这就好像对于不了解的东西,先不管它,当它是已知的.
节点,边,面,三个之中,显然面更为不常见(在图论中,经常碰到节点和边,而面很少见),我们可以先尝试绑定面.
先假设F=1,这样待证的欧拉公式简化为$V + 1 = E + 2 \Rightarrow E = V - 1$,即当面为1时,边的数目比节点数少1.这个性质就比较眼熟了,连通图只有1个面,就退化成了树(1个面表示无回路,无回路就是树),而树的性质有$E = V - 1$
第一步
这样,问题分解为了几部分,而第一部分是证明对于树有$E = V - 1$.归纳基础显然成立(设想n=1的情况),继续使用归纳法求解
首先,假设其成立,对于$k < n$个节点的树,边数$E = k - 1$
然后,当树有n个节点时,如果归纳假设成立,那么这个节点需要仅增加1条边.假设其增加了至少2条边,那么该节点必然同原来树的至少2个节点相连,而原来树是连通的,那么这三个点就形成了回路,就不是树了,违反假设性质.所以归纳假设是成立的
最后,本步骤得证
第二步
第一步绑定了F=1,显而易见,下一步就是将F当做变量来进行第二步的归纳,而第一步的结论,就是第二步的归纳基础.
第二步要证明的是就是当F=n时,满足$V + n = E + 2$
首先,假设其成立,即$k < n$时,满足$V + k = E + 2$
然后,考虑F = n时,如何把情况回归到n - 1的时候.自然的想法是减少1个面,根据假设,此时还需要减少1条边.所有的面都是一个回路(最外头的面的回路就是图的外围),所以切断一条边,并不影响其连通性.但切断1条边后,2个面(以该边为边的相邻面)就合二为一了.这样,通过切断1条边(边数少1),面数也少1,完成了回归归纳假设的步骤,所以归纳假设成立
最后,问题得证.
总结
面对多个变量共存时,首先的一点是不能慌,或者放弃,这是必须克服的心理障碍,不要怕.其次,要选择合适的归纳顺序,先固定较难的变量,然后以此为归纳基础,讨论整体.有可能这个过程会迭代多次,面对困难问题时,不要试图一蹴而就
这个问题和三角加法的问题不太相同.那个问题本身在于问题的转化,转换后的问题都是独立可处理的,而本题的转化更类似于问题的分布,几个问题之间有着起承的联系.两种不同的处理方式也是要注意的