正文

一些方法(2)

暗时间 作者:刘未鹏


3.反过来推导。反过来推导是一种极其重要的启发法,正如前面提到的,Pappus在他的宏篇巨著中将这种手法总结为解题的最重要手法。实际上,反向解题隐含了解题中至为深刻的思想:归约。归约是一种极为重要的手法,一个著名的关于归约的笑话这样说:有一位数学家失业了,去当消防员。经过了一些培训之后,正式上任之前,训练的人考他:如果房子失火了怎么办?数学家答出了所有的正确步骤。训练人又问他:如果房子没失火呢?数学家答:那我就把房子点燃,这样我就把它归约为了一个已知问题。人类思维本质上善于“顺着”推导,从一组条件出发,运用必然的逻辑关系,得出推论。然而,如果要求的未知量与已知量看上去相隔甚远,这个时候顺着推实际上就是运用另一个启发式方法 — 试错 — 了。虽然试错是最常用,也是最有效的启发法,然而试错却并不是最高效的。对于许多题目而言,其要求的结论本身就隐藏了推论,不管这个推论是充分的还是必要的,都很可能对解题有帮助。如果从结论能够推导出一个充要推论,那么实际上我们就将问题进行了一次“双向”归约,如果原问题不容易解决,那么归约后的问题也许就容易解决了,通过一层层地归约,让逻辑的枝蔓从结论上一节节地生长,我们往往会发现,离已知量越来越近。此外,即便是从结论推导出的必要非充分推论(“单向”归约),对问题也是有帮助的 — 任何不满足这个推论的方案都不是问题的解。譬如通过驻点来求函数的最值,我们通过考察函数的最值(除了函数边界点外),发现它必然有一个性质,即在这个点上函数的一阶导数为0,虽然一阶导数为0的点未必是最值点,但我们可以肯定的是,任何一阶导数不为0的点都可以排除,这就将解空间缩小到了有穷多个点,剩下的只要做做简单的排除法,答案就出现了。再譬如线性规划中经典的单纯形算法(又见《Algorithms》⑥),也是通过对结论的考察揭示出只需遍历有限个顶点便必然可以到达最值的。此外很多我们熟知的经典题目也都是这种思路的典范,譬如《How To Solve It》上面举的例子:通过一个9升水的桶和一个4升水的桶在河里取6升水。这个题目通过正向试错,很快也能发现答案,然而通过反向归约,则能够不偏不倚的命中答案。另一些我们耳熟能详的题目也是如此,譬如:100根火柴,两个人轮流取,每个人每次只能取1~7根,谁拿到最后一根火柴谁赢;问有必胜策略吗,有的话是先手还是后手必胜?这个问题通过试错就不是那么容易发现答案了。同样,这个问题的推广被收录在《编程之美》⑦里面:两堆橘子,各为m和n个,两人轮流拿,拿的时候你只能选择某一堆在里面拿(即不能跨堆拿),你可以拿1~这堆里面所有剩下的橘子,谁拿到最后一个橘子谁赢;问题同上。算法上面很多聪明的算法也都是通过考察所求结论隐藏的性质来减小复杂度的,譬如刚才提到的单纯形问题,譬如经典面试题“名人问题”、“和最小(大)的连续子序列”,等等。倒推法之所以是一种极为深刻的思维方法,本质上是因为它充分利用了题目中一个最不易被觉察到的信息 — 结论。结论往往蕴含着丰富的条件,譬如对什么样的解才是满足题意的解的约束。一般来说,借助结论中蕴含的知识,我们便可以更为“智能地”搜索解空间。举一个直白的例子,有人要你在地球上寻找一栋满足如下条件的建筑:__层高(填空自己填),__风格,__年代始建,…… (省略若干约束条件)。对于这样一个问题,最平凡的解法是穷举地球上每一栋建筑,直到遇到一个满足条件的为止。而更“智能”的(或者说更“启发”的)方法则是充分利用题目里面的约束信息,譬如假若条件里面说要60层楼房,你就不会去非洲找,如果要拜占庭风格的,你估计也不会到中国来找,如果要始建于很早的年代的,你也不会去非常新建的城市里面去找,等等。倒推法是如此的重要,以至于笛卡尔当时认为可以把一切问题归结为求解代数方程组,笛卡尔的万能解题法就是首先将问题转化为代数问题,然后设出未知数,列出方程,最后解这组(个)方程。其中设未知数本质上就是一种倒推:通过设出一个假想的结论x,来将题目对x的需求表达出来,然后顺势而下推导出x。仔细想想设未知数这种手法所蕴含的深刻思想,也就难怪笛卡尔会认为它是那个解决所有问题的一般性钥匙了。


上一章目录下一章

Copyright © 读书网 www.dushu.com 2005-2020, All Rights Reserved.
鄂ICP备15019699号 鄂公网安备 42010302001612号