婴儿感冒流涕怎么办

关于解题思维的杂感三则 （思维、类比、启发法） TopLanguage上关于解题的讨论已经进行了一 段时候了，有很多收获。我们的讨论目的不是 将题目解出来，而是在于反思解题过程中的一 般性的，跨问题的思维法则。简单的将题目解 出来（或者解不出来看答案，然后“恍然大 悟”），只能得到最少的东西，解出来固然能 够强化导致解出来的那个思维过程和方法，但 缺少反思的话便不能抽取出一般性的东西供 更多的问题所用。而解不出来，看答案然后 “哦”的一声更是等同于没有收获，因为“理解” 和“运用”相差何止十万八千里。每个人都有过 这样的经历：一道题目苦思冥想不得要领，经 某个人一指点其中的关键一步，顿时恍然大 悟。——这是理解。但这个理解是因为别人已 经将新的知识（那个关键的一步）放到你脑子 里了，故而你才能理解。而要运用的话，则需 要自己去想出那关键的一步。因此，去揣测和 总结别人的思维是如何触及那关键的一步，而 你自己的思维又为什么触及不到它，是很有意 义的。我们很多时候会发现，一道题目，解不 出来，最终在提示下面解出来之后，发现其中 并没有用到任何自己不知道的知识，那么不仅 就要问，既然那个知识是在脑子里的，为什么 我们当时愣是提取不出来呢？而为什么别人 又能够提取出来呢？我怎么才能像别人那样 也提取出相应的知识呢？实际上这涉及到关 于记忆的最深刻的原理。（我个人对此有一点 总结和猜测，但并不成熟。有兴趣自己考察的 建议参考以下几本书：《追寻记忆的痕迹》， 《找寻逝去的自我》，《Synaptic Self》， 《Psychology of Problem Solving》）一般性的 思维法则除了对于辅助联想（起关键的知识） 之外，另一个作用就是辅助演绎/归纳（助探）， 一开始学解题的时候，我们基本上是先读懂题 目条件，做可能的一些显然的演绎。如果还没 推到答案的话，基本就只能愣在那里等着那个 关键的步骤从脑子里冒出来了。而所谓的启发 式思维方法，就是在这个时候可以运用一些一 般性的，所有题目都适用的探索手法，进一步 去探索问题中蕴含的知识，从而增大成功解题 的可能性。启发式的思维方法有很多，从一般 到特殊，最具一般性的，在波利亚的《How to Solve It》中已经基本全部都介绍了。一些更为 特殊性的（譬如下文最后一个例子中关于分割 搜索空间的法则），则需要自己在练习中总结， 抽象，整理。 以下是两篇发在讨论组上的杂记（不是总 有时间写像《跟波利亚学解题》这样的长文 的:P）。 [一] 两道经典算法题的几种思维方法分 析 题目各有各的不同，但背后的思维方式大 抵都是一样的。如何在每一道题目中总结出最 多一般性的思维法则，就决定了练习的效率。 下面是非常经典，且广为流传的两道题 目，知道答案的也许会认为再这样的题目 没有任何价值，但是题目的价值不在于新旧， 而在于到底能从中总结出多少东西。这两道题 目的价值就在于，他们的求解过程中涉及到的 思维法则都非常典型，而且并不是太难。 问题 1描述：名人问题 一个名人就是指这样一个人：所有其他人 都认识他，并且他不认识任何其他人。现在有 一个 N个人的集合，以及他们之间的认识关 系。求一个算法找出其中的名人（如果有的话） 或者判断出没有名人（如果没有的话）。 思维方法一：特例法。考虑两个人。发现， 如果 A、B如果互相认识，或互相不认识，则 他们都不可能是名人。如果其中之一认识另一 个（不失一般性我们令 A认识 B），则 A被淘 汰。 思维方法二：倒推法。假设名人已经出现， 考虑名人的定义，一个名人 P是指满足如下两 个条件的人： 任取一个人 Q，Q认识 P。 任取一个人 Q，P不认识 Q。 接着，出于对“哪些人不符合名人的标准 从而可以在我们搜索解空间的时候直接淘汰 掉呢？”这个问题的询问。我们考察以上条件 的反面。即“如果__则 P不是名人”这个填空： 存在一个人 Q，Q不认识 P。 或 存在一个人 Q，P认识 Q。 根据这两个条件，我们实际上就可以优化 穷举式的搜索，因为当比较两个人 P1和 P2的 关系的时候，我们发现利用上面两个规则，其 中最多只能有一个人具有“名人潜质”，因为根 据以上规则，不管这两人之间出现认识还是不 认识关系，总有一个人要被刷掉。 思维方法三：联想法。联想的可能性有 这是一个涉及 n的问题，尝试用归纳法， 即考虑其子问题。如何定义子问题？两个明显 的办法：1，二分为两个 n/2规模的子问题。一 个名人必然是这两个子问题里面的名人，所以 问题归约为求解两个子问题，并在最后一个环 节合并这两个子问题的解。2，考虑 n-1阶的子 问题。一个名人必然是 n-1阶子问题中的名人， 问题被归约为求解 n-1阶子问题，然后其结果 ——n-1阶名人与最后一个人的关系进行比 较。最后，不管采用两种归纳法中的哪一个， 最后一步优化都是一样的，即将递归转化 为迭代方案。 这是一个涉及 n的问题，直接联想到递归 算法，于是试图去凑一个递归的程序，结果同 上面的第 2种方案一样。 由于是在 n个人中“争”出一个名人，因此 联想到竞赛，试着往传统竞赛算法上凑，即一 个个的比并淘汰的方案，并因此发现内中的淘 汰规则。 etc. （有人补充吗？） 问题 2描述：和最小连续子序列问题 有 N个数，其中有正有负，求出其中和最 小的连续子序列。（连续子序列就是 a[i]~a[j] 所有连续元素形成的序列，其中 i，j任取） 思维方法一：倒推。假设最小和子序列已 经找到，我们试着去尽量挖掘这个最小和子序 列的性质，每个性质都有助于我们更“智能地” 在解空间中进行搜索。我们不难发现，这个假 想的最小和子序列的两端元素必然是负的，否 则我们可以削掉它们求得一个更小和的子序 列。再进一步我们会发现，事实上这个最小和 子序列从任意一段算起的一个前缀/后缀的和 必然也是负的，否则我们也可以将其削掉来求 得一个更小和的子序列。此外，与这个最小和 子序列两端紧邻着的任意一段区间的和必然 是正的，否则我们必然可以将其添加到我们假 设的最小和序列上，以求得一个更小和的子序 列。一旦挖掘出了以上三个被蕴含在结论中的 条件，我们就可以更为智能地搜索解空间了。 思维方法二：这是一个涉及 n的问题，试 着考察其子问题。我们能将问题降到 n-1阶 吗？n阶问题里面的最小和子序列与 n-1阶里 面的最小和子序列有什么关联吗？如果 n阶问 题里面的最小和子序列不含有最后一个元素， 那么它肯定同样也是 n-1阶问题中的最小和子 序列。这种情况下我们就完全将问题降到了 n-1阶。但如果它包含最后一个元素，那么一 个自然的问题就是，n-1阶问题中的最小和子 序列含在 n阶最小子序列切掉最后一个元素之 后剩下的那个序列内吗？如果是的话，这种情 况下问题也可以归约为 n-1阶，也就是说只有 n-1阶中的最小和序列才具有潜质成长为 n阶 的最小和序列。然而，第二种情况下的答案却 是否定的（试着找一个反例）。所以看上去这 条路行不通。一般来说，一条路行不通之后， 首先要做的就是反省一下思路，看看到底什么 地方出了什么问题，也许有可能修修补补之后 就能够得到正确答案——想一想，我们刚才是 在试着将问题降到 n-1阶。那么，为什么一定 要是 n-1阶呢？譬如二分法就是试图将问题降 到两个 n/2阶子问题。为什么这里将问题降到 n-1阶是不奏效的？因为这样的降阶无法保证 我们 solve 了 n-1阶的子问题之后能够根据它 的解来构造 n阶问题的解。再仔细看看我们的 方法，我们也许会发现，问题实质上出在最小 和子序列可能会从 n-1阶跨越到 n阶，换句话 来说，问题的可能解会跨越两个子问题，这样 的子问题分解得到的是不完全的子问题，我们 除了需要 solve 两个子问题之外，还需要考虑 跨越这两个子问题的潜在解，这可是个麻烦事 儿。最好的子问题分解是只需要直接 solve掉 子问题就结了，举个例子，我们熟悉的快速排 序，快速排序将一个区间根据一个中轴元素分 解为两个区间之后，就将问题分解为了两个子 问题，然后就只需要 solve这两个子问题（将 这两个区间排序），就直接了结了。它的两个 子问题是完全分离的，我们不必担心任何左区 间内的元素和右区间内的元素会出现乱序的 情况。那么，我们的这个问题，关键就在于应 该也将它分解为两个完全子问题，我们设想有 某种手法，能够将我们 n个数分解为两段，其 中要想求全局的最小和子序列，我们只需要对 这两段分别求其中的最小和子序列，然后看看 哪个小即可。我们无需考察跨越这两个区间的 子序列。这样一来我们就可以非常省心的将问 题一步步分解为完全的子问题了。然而，到底 怎样才能分解出这样的两个区段来呢？看看 我们的未知数是什么。我们的未知数是要寻找 这样的切分。但我们现在很茫然，n-1后面切 一刀不行，二分法也不行，到底怎么切呢？看 来这样盲目尝试是不行的。试试倒推吧。我们 假设这样的切割已经出现了，它满足“最小和 序列肯定不会跨越其切割边界”这个条件，即 任取一个跨越其切割边界的子序列，都必然不 是最小和序列。那么要怎样才能让一个序列不 是最小和序列呢？想想上面思维方法一里面 推导出的结果，最小和序列的任意前缀后缀序 列必然和为负；且两端向外扩展的序列和必然 为正。所以，要想让一个序列和不是最小，我 们只要让情况不满足这两个条件即可。基于这 个条件，细心耐心一点很快就会推导出这个切 割所需满足的性质了。 思维方法三：直接联想到动态规划。然后 往动态规划上硬套。硬套的过程中必然会受挫 （看了下面的做法你就知道为什么不是简单 的动态规划了），也许经过一定的试错，会联 想到 Introduction to Algorithms里面那个关于 排课的问题，从而想到将区间按照结尾元素的 不同来分类：（这个思路是网上抄来的，关键 是“考虑以某个 a[x]终止的所有子序列”这一步 很是摸不着头绪。有谁能够提供这个做法背后 的思维过程吗？） 设 f[x]为以 a[x]终止且包含 a[x]的最小序 列的和，有： f[1] = a[1]; f[x+1] = f[x] < 0 ? f[x] + a[x+1] : a[x+1] 那么最小子序列的和就是 f[1] .. f[n] 中最 小的一个。 Update:邓鋆在讨论组里面提到一个很好 的 point： 关于动态规划，我提醒部分习惯于看到动 态规划就以直接写出函数为目标的同学们：部 分动态规划题目不适合直接将最终答案当作 函数值来设计递推函数，往往用一些中间的结 果。比如我们要找整个解空间的最优解，但整 个解空间的最优解不存在直接的递推关系，那 么可否考虑设计比如"以该位置结尾"的解空 间，其最优解很大可能存在递推关系。随后将 解空间综合比较，可得到整体的最优解。（当 然，在算法中，可以一边求一边解）用这种方 法，在思考算法的时候，一定要确保你的递推 过程遍历到了整个解空间。 显然，如果我在之前脑子里就有以上的原 则的话，应该是能想到根据区间结尾来划分搜 索空间的。但事后总结不代就是事前真正发 生的事情。对于这道题目，事后总结固然得到 一条非常重要的原则（即上面这段），但难道 最初解出题目的人由于还不知道这个原则，就 没法解出来吗？鸡和蛋的问题。显然，最初想 到这个法子的人也许使用了更一般的思维方 法。而我们在知道了一道题目的答案之后，除 了总结这道题目提供的领域知识性的原则之 外，更重要的还要总结更一般层面上的，跨问 题的，思维性质的法则。 [二]抽象在类比联想中的作用一例 《Psychology of Problem Solving》里面举 了一个例子，了对问题本质的抽象能够增 加后来遇到本质类似（但表面不类似）的题目 的时候联想到前一道题目的可能性。我在这里 提到了这个例子，摘录如下： 《Psychology of Problem Solving》的第 11 章举了这样一个例子：先让被试（皆为大学生） 阅读一段军事材料，这个材料是说一小撮军队 如何通过同时从几个不同方向小规模攻击来 击溃一个防守严实的军事堡垒的。事实上这个 例子的本质是对一个点的同时的弱攻击能够 集聚成强大的力量。然后被试被解决一个 问题：一个医生想要用 X射线杀死一个恶性肿 瘤，这个肿瘤只可以通过高强度的 X射线杀 死，然而那样的话就会伤及周围的良好组织。 医生应该怎么办呢？在没有给出先前的军队 的例子的被试中只有 10%想到答案，这是控制 基线。然后，在先前学习了军队例子的被试中， 这个比例也仅仅只增加到 30%，也就是说只有 额外 20%的人"自动"地将知识进行了转移。最 后一组是在提醒之下做的，达到了 75%，即比 "自动"转移组增加了 45%之多。这个例子说明， 知识的表象细节会迷惑我们的眼睛，阻碍我们 对知识的运用，在这个例子中是阻碍问题之间 的类比。 不过这个例子稍微有点人为的味道。下面 则是一个更为“现实”的例子： 问题：求 N个数中最大的 K个数。 分析：首先很多人都能够联想到一个类似 的问题：求 N个数中的最大数。不过，关于后 者的表面知识（譬如算法的详细过程和细节） 是不能直接借用的。这很大程度上会阻止利用 既有问题的解来解决新的问题。对算法的非本 质（表面）细节了解的越多越细，就越是可能 妨碍类比联想。 然而，如果在当时吸收第一道题目的知识 的时候就进行了抽象，提取出了其中的本质： 只要有一个数小于任何另一个数，它就肯定不 是最大的了，从而可以淘汰。就不难将其运用 到就求最大 K数上：只要有一个数小于任何 K 个数，它就肯定不属于最大 K个数之列了，从 而可以淘汰。这里的抽象元素有两个，分别是： "淘汰法"，以及"一个淘汰的准则"。（抽象越 是含糊越好（只要不过于含糊），因为基本上， 越含糊的抽象，越是接近本质，联想空间也越 大。也许这里可以套用爱因斯坦的一句话：抽 象应该尽量含糊，只要不过于含糊。） （当然，这个题目还有其它思考方法。譬 如运用上文提到的倒推法，我们假设一个属于 最大 K数的数已经找到，令为 X，我们来考察 它具有什么性质：至多有 K-1个数大于它。将 这个性质“反”一下，我们便得到一条能更为智 能搜索解空间的性质：只要出现任何 K个数大 于 X，X即可被淘汰出搜索空间。此外还可以 从“N”这个变量联想到分治（基本上凡是涉及 到 N的问题都可以考虑分治——动态规划和 贪婪等方法是分治的特例），即考虑问题的子 问题：N-1个数中的最大 K个数是怎样的？与 全局最大K数有什么关系？除了分解为N-1阶 子问题，还有其他分解方法吗？N/2？或者根 据某种规则进行划分？等等。） 这样的例子还有很多。（注：这道题目被 收录在《编程之美》中） [三]启发法的局限性 （注：不太清楚什么是启发法的，欢迎参 考波利亚的《How to Solve It》或 wikipedia（搜 索 heuristics），以及这篇。） 首先肯定的是，启发法一定（也许很大） 程度上是可以代偿知识的不足的（这里的知识 主要是指大脑中的“联系”，下面还会提到另一 种知识，即 hard knowledge）。譬如，一道题 目，别人直接就能通过类比联想到某道解过的 题目，并直接使用了其中的一个关键的性质把 题目给解出来了。你并没有做过那道题目，这 导致两种可能的结果：一，你就是不知道那个 性质。二，你虽然“知道”那个性质，但并没有 在以前的解题经历中将那个性质跟你手头的 这个问题中的“线索”联系起来，所以你还是“想 不到”。后一种可以称为 soft knowledge，即你 “知道”，但就是联想（联系）不起来。所谓不 能活学活用，某些时候就是这种情况，即书本 上提供什么样的知识联系，脑子里也记住什 么，而没有事后更广泛地去探索知识之间的本 质联系（总结的作用）。前一种则可以称为 hard knowledge，即你就是不知道，它不在你的脑 子里。 而启发式方法在两个层面上起作用： 辅助联想起 soft knowledge：譬如，特例 法是一种启发式思考方法，它通过引入一个简 单的特例，特例中往往蕴含有更多的“线索”， 通过这些线索，有可能就会激发起对既有的知 识的联想。另外一种强大的辅助联想办法就是 对题目进行变形，变形之后就产生了新的视觉 和语意线索，比如式子的对称性、从直角坐标 到极坐标从而引发对后者的知识的联想等等。 大量的启发式方法实际上的作用就是辅助联 想，通过对题目中的线索的发掘，激起大脑中 已知相关知识的浮现。在这个意义上，相对于 那些能够直接联想到某个性质的人，那些不知 道但可以通过启发式思维联想到的，启发式思 维就提供了一种“曲径通幽”的策略性联想。还 是以经典的例子来说：砖头的用途。有人立即 能够直接联想到“敲人”。有人也许不能。然而 启发式联想策略“抽象”就能够帮助后者也能 够联想到“敲人”，因为“抽象”策略启发人去考 虑砖头的各个性质维度，如“质地”，“形状”， 当你考察到“质地坚硬”，“棱角”，离“敲人”的 功能还会远么？本质上，能够直接联想到“敲 人”功能的人是因为大脑中从砖头到敲人这两 个概念之间的神经通路被走过了很多遍（譬如 由于经常拿砖头敲人），神经元之间的联系相 当“粗”（形象的说法，严格的事实请参考《追 寻记忆的痕迹》），而不经常拿砖头敲人的人 呢，这个联系就非常的弱，乃至于根本激不起 一次神经冲动。那么为什么通过启发式方法又 能联想到呢？因为启发式方法相当于带入了 一种新的神经调控回路，首先它增加你联系到 砖头的属性维度上的可能性，使得“质地坚 硬”、“棱角”这两个语意概念被激活起来（注意， 如果没有启发式方法的参与，这是不会发生 的），一旦后者被激活起来，从后者到“敲人” 的联系就被激活起来了。从本质上，解题中的 启发联想方法做的也就是这个工作。而越是一 般性的启发式方法就越是能对广泛的问题有 帮助（譬如《How to Solve It》中介绍的那些， 譬如分类讨论、分治、乃至我认为很重要的一 个——写下自己的思维过程，详细分解各个环 节，考察思维路径中有无其它可能性（我们很 容易拿到一道题目便被一种冲动带入到某一 条特定的思路当中，并且遵循着“最可能的”推 导路径往下走，往往不自觉的忽略其它可能 性，于是那些可能性上的联想就被我们的注意 力“抑制”了。））。 辅助探索出 hard knowledge：倒推法是一 种启发式思考方法，它将你的注意力集中到问 题的结论中蕴含的知识上，一旦你开始关注可 能从结论中演绎出来的知识，你就可能得到 hard knowledge，即并不是早先就存在你脑子 里，但是可以通过演绎获得的。上文中的最小 和子序列中的倒推方法就是一个例子。 而启发式方法的局限性也存在于这两个 方面： 有些联系是不管怎样“启发”也想不起来 的。譬如“当布被刺破了，干草堆就重要了”， 你怎么解释这句话？如果有人提示一下“降落 伞”，每个人都会恍然大悟。这是因为从“布” 到“降落伞”之间的单向联系是近乎不存在的。 而且就算运用启发法，譬如，考虑所有布做的 东西，也基本绝无可能想到降落伞，因为同样， 从“布做的东西”到“降落伞”之间的关联也是极 其微弱的。我们脑子里只能保留那些最最重要 的联系。（如果一提到布，“降落伞”和“衣服”、 “被单”、“窗帘”等日常物品以同等重要级别闪 现，就乱套了。）那为什么从降落伞我们能想 到布呢？我们实际上不能，我们为什么有些时 候能，是因为譬如有人叫你“考虑降落伞的材 料”，后者就激发了“降落伞之材料”这个语意， 后者又指导了我们去考察降落伞的材料构成， 于是我们想到是布。否则“布”是不会直接被激 发起来的。那为什么在我们的这个问题中，一 旦有人提到降落伞，我们就能建立从布到降落 伞的关联呢？这是因为“降落伞”和“布”这两个 语意单元的同时兴奋增大了它们之间关联的 可能性，就好比是加大另一端的电压从而发生 了“击穿”一样。从本质上，解数学题也是如此， 费马大定理的求解过程是一个很好的例子，谷 山志村猜想，就相当于那个“降落伞”的提示。 我们还听到很多这样的故事（或者自己经历）： 苦思冥想一个问题不得要领，某一天在路上 走，看到某个东西或听到某句话，然后忽然， 一道闪电划破长空，那个问题解开了（阿基米 德是因为躺在浴缸里从而想到浮力原理的 吗？）。我敢保证，如果一个人早就把那个问 题从脑海里扔到九霄云外去了（不再处于兴奋 状态了），那么就算线索出现，也是不可能发 生顿悟的。我们都知道，带着一个问题（使其 在大脑中处于兴奋状态）去寻找答案更可能找 到，即便不是有意去寻找，只要问题还在脑子 里，任何周围的有可能与它相关的线索都不会 被大脑漏掉，因为“问题”和“周围的其他线索” 同时的兴奋增大了关联的可能性。如果问题早 就被从大脑（意识或者潜意识）中撤下了，即 便周围出现提示也不会被捕捉到。 许多 hard knowledge是不能被启发探索出 来的。至少是不能被“直接命中目标”地探索出 来的。一个问题有可能跟三角函数有关，也许 你只能带着问题去探索三角函数的所有性质， 从而最终发现那个关键的性质。费马大定理与 椭圆方程有关，也许只能去探索椭圆方程的所 有性质，这个过程一定程度上是盲目的，试错 的，遍历的。而不是直接面向目标的。再聪明 的人也无法从费马大定理直接反推到谷山志 村猜想。在这些时候，启发式方法最多只能提 供一个探索的大致方向：譬如，探索三角函数 的性质，并随时注意其中哪个可能对我这个问 题有帮助。譬如，探索模运算的性质，看看哪 些性质可能会有用。譬如，探索椭圆曲线的性 质...等等。启发式方法并不能使我们的探索精 准地命中目标。而只能划定一个大致的范围。 也难怪有人说数学是盲目的。 但话说回来，启发式方法的局限性并不能 否认在大量场合启发式方法的巨大帮助，许多 时候，单靠启发式方法就能带来突破。而且， 一旦知识性的东西掌握的是一样多的，能否运 用更优秀的思维方法就决定了能力的高下。有 很多介绍思维方法的书。