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

《关于解题思维的杂感三则(思维、类比、启发法)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、关于解题思维的杂感三则（思维、类比、启发法）TopLanguage上关于解题的讨论已经进行了一段时候了，有很多收获。我们的讨论目的不是将题目解出来，而是在于反思解题过程中的一般性的，跨问题的思维法则。简单的将题目解出来（或者解不出来看答案，然后“恍然大悟”），只能得到最少的东西，解出来固然能够强化导致解出来的那个思维过程和方法，但缺少反思的话便不能抽取出一般性的东西供更多的问题所用。而解不出来，看答案然后“哦”的一声更是等同于没有收获，因为“理解”和“运用”相差何止十万八千里。每个人都有过这样的经历：一道题目苦思冥想不得要领，经某个人一指点其中的关键

2、一步，顿时恍然大悟。——这是理解。但这个理解是因为别人已经将新的知识（那个关键的一步）放到你脑子里了，故而你才能理解。而要运用的话，则需要自己去想出那关键的一步。因此，去揣测和总结别人的思维是如何触及那关键的一步，而你自己的思维又为什么触及不到它，是很有意义的。我们很多时候会发现，一道题目，解不出来，最终在提示下面解出来之后，发现其中并没有用到任何自己不知道的知识，那么不仅就要问，既然那个知识是在脑子里的，为什么我们当时愣是提取不出来呢？而为什么别人又能够提取出来呢？我怎么才能像别人那样也提取出相应的知识呢？实际上这涉及到关于记忆的最深刻的原理。（我

3、个人对此有一点总结和猜测，但并不成熟。有兴趣自己考察的建议参考以下几本书：《追寻记忆的痕迹》，《找寻逝去的自我》，《SynapticSelf》，《PsychologyofProblemSolving》）一般性的思维法则除了对于辅助联想（起关键的知识）之外，另一个作用就是辅助演绎/归纳（助探），一开始学解题的时候，我们基本上是先读懂题目条件，做可能的一些显然的演绎。如果还没推到答案的话，基本就只能愣在那里等着那个关键的步骤从脑子里冒出来了。而所谓的启发式思维方法，就是在这个时候可以运用一些一般性的，所有题目都适用的探索手法，进一步去探索问题中蕴含的知识

4、，从而增大成功解题的可能性。启发式的思维方法有很多，从一般到特殊，最具一般性的，在波利亚的《HowtoSolveIt》中已经基本全部都介绍了。一些更为特殊性的（譬如下文最后一个例子中关于分割搜索空间的法则），则需要自己在练习中总结，抽象，整理。以下是两篇发在讨论组上的杂记（不是总有时间写像《跟波利亚学解题》这样的长文的:P）。[一]两道经典算法题的几种思维方法分析题目各有各的不同，但背后的思维方式大抵都是一样的。如何在每一道题目中总结出最多一般性的思维法则，就决定了练习的效率。下面是非常经典，且广为流传的两道题目，知道答案的也许会认为再分析这样的题目

5、没有任何价值，但是题目的价值不在于新旧，而在于到底能从中总结出多少东西。这两道题目的价值就在于，他们的求解过程中涉及到的思维法则都非常典型，而且并不是太难。问题1描述：名人问题一个名人就是指这样一个人：所有其他人都认识他，并且他不认识任何其他人。现在有一个N个人的集合，以及他们之间的认识关系。求一个算法找出其中的名人（如果有的话）或者判断出没有名人（如果没有的话）。思维方法一：特例法。考虑两个人。发现，如果A、B如果互相认识，或互相不认识，则他们都不可能是名人。如果其中之一认识另一个（不失一般性我们令A认识B），则A被淘汰。思维方法二：倒推法。假设名

6、人已经出现，考虑名人的定义，一个名人P是指满足如下两个条件的人：任取一个人Q，Q认识P。任取一个人Q，P不认识Q。接着，出于对“哪些人不符合名人的标准从而可以在我们搜索解空间的时候直接淘汰掉呢？”这个问题的询问。我们考察以上条件的反面。即“如果__则P不是名人”这个填空：存在一个人Q，Q不认识P。或存在一个人Q，P认识Q。根据这两个条件，我们实际上就可以优化穷举式的搜索，因为当比较两个人P1和P2的关系的时候，我们发现利用上面两个规则，其中最多只能有一个人具有“名人潜质”，因为根据以上规则，不管这两人之间出现认识还是不认识关系，总有一个人要被刷掉。思

7、维方法三：联想法。联想的可能性有这是一个涉及n的问题，尝试用归纳法，即考虑其子问题。如何定义子问题？两个明显的办法：1，二分为两个n/2规模的子问题。一个名人必然是这两个子问题里面的名人，所以问题归约为求解两个子问题，并在最后一个环节合并这两个子问题的解。2，考虑n-1阶的子问题。一个名人必然是n-1阶子问题中的名人，问题被归约为求解n-1阶子问题，然后其结果——n-1阶名人与最后一个人的关系进行比较。最后，不管采用两种归纳法中的哪一个，最后一步优化都是一样的，即将递归方案转化为迭代方案。这是一个涉及n的问题，直接联想到递归算法，于是试图去凑一个递归

8、的程序，结果同上面的第2种方案一样。由于是在n个人中“争”出一个名人，因此联想到竞赛，试着往传统竞赛算法上凑