关于解题思维的杂感三则（思维、类比、启发法）

关于解题思维的杂感三则（思维、类比、启发法）

By 刘未鹏(pongba)

C++的罗浮宫(http://blog.csdn.net/pongba)

TopLanguage(http://groups.google.com/group/pongba)

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是不能被启发探索出来的。至少是不能被“直接命中目标”地探索出来的。一个问题有可能跟三角函数有关，也许你只能带着问题去探索三角函数的所有性质，从而最终发现那个关键的性质。费马大定理与椭圆方程有关，也许只能去探索椭圆方程的所有性质，这个过程一定程度上是盲目的，试错的，遍历的。而不是直接面向目标的。再聪明的人也无法从费马大定理直接反推到谷山志村猜想。在这些时候，启发式方法最多只能提供一个探索的大致方向：譬如，探索三角函数的性质，并随时注意其中哪个可能对我这个问题有帮助。譬如，探索模运算的性质，看看哪些性质可能会有用。譬如，探索椭圆曲线的性质...等等。启发式方法并不能使我们的探索精准地命中目标。而只能划定一个大致的范围。也难怪有人说数学是盲目的。

但话说回来，启发式方法的局限性并不能否认在大量场合启发式方法的巨大帮助，许多时候，单靠启发式方法就能带来突破。而且，一旦知识性的东西掌握的是一样多的，能否运用更优秀的思维方法就决定了能力的高下。有很多介绍思维方法的书。

P.S.

1. 对《跟波利亚学解题》一文作了两次增添(rev#2)，主要在最后一部分增添了三个小节（关于练习的作用，以及上文提到的启发法的局限性）。移步这里。

2. 这里是目前我们已经进行了的讨论：