发散思维在计算机算法教学中的重要性

杜立智

（武汉科技大学 计算机科学与技术学院，湖北 武汉 430081）

0 引 言

在计算机算法领域，要想取得显著的原创成果，必须具备如下3种能力：①想象力，在千头万绪的各种可能性中，若没有丰富的想象力，就不可能找到有效的甚至奇妙的方法；②敏锐的逻辑领悟力，能敏锐地把握某种想法与所要解决问题之间的内在逻辑联系；③深入的思路能力，也就是沿一条长长的思维脉络深入思考下去的能力。这3种能力缺一不可。如何取得？天分在这里有很大的作用，但在平时思考算法问题、在读懂他人算法的过程中有意识地加以培训，也是有效途径。

计算机科学专业与其他专业有显著的不同点，这些不同点导致了在教与学方面的某些根本不同。其他专业大都由这两点主导，一是着重于对概念原理的理解和掌握，二是长年知识经验的积累非常重要。这两点在计算机科学专业当然也具有意义，但不拥有主导意义。计算机科学专业最核心的方面，一是思维方式和观念的更新，二是思维能力的强大。一般说来，侧重于概念和原理理解的教学较容易把握，而在思维方式思维能力上，要想取得显著的教学效果则有难度，尤其是在国内高校课程多课时紧的情况下[1]。

例如，计算机算法课程的核心就是思维能力的培训，缺少思维能力，概念原理再怎么掌握都没有实质价值。同时，计算机算法课程也是计算机科学的最核心课程。人工智能的发展依赖于思维方式和观念的更新，而无论什么样的思维方式和观念，都必须以思维能力为基础，故人工智能的发展也必须建立在强大的算法功力上。

计算机算法有一个不同于其他课程的重要特点——需要一连串的思维，这一连串的思维由许多关键点构成，这些关键点彼此依序而行又动态关联。思路运行的任一时刻，所有关键点都必须同时印在脑海里，且必须同时都有透彻的理解，并在需要的时候可以将此时的思路与前面的任何关键点关联起来[2]。任何疏忽遗漏或一知半解都会导致整个思路的失败。这正是复杂算法难以理解掌握的根本原因。相较于其他课程，计算机算法课要想取得显著的教学效果，其难度要大得多。

1 发散思维和计算机算法简述

心理学研究认为发散思维（又称辐射思维或扩散思维）是指大脑在思维时呈现的一种扩散状态的思维模式，它表现为思维视野广阔，思维呈现出多维发散状。如“一题多解”“一事多写”“一物多用”等方式。不少心理学家认为，发散思维是创造性思维的最主要特点，是测定创造力的主要标志之一。

具体到计算机算法中，发散思维需要具备两点，一是想象力，二是多角度。按通常的思路难以想到的方法和解决问题的途径，若能有效运用发散思维，就可能迎刃而解。

发散思维有三大特性：流畅性、变通性、独特性。流畅性反映的是发散思维的速度和数量特征，具体到计算机算法中，就是掌控一连串长的思路的能力，这个能力的取得相当有难度，需要长时间培训。变通性就是克服人们头脑中某种僵化的思维框架，按照某一新的方向来思索问题的过程，表现出多面性和多样性。在计算机算法中，变通性天分在这方面具有重要作用，后天的刻苦训练也有显著效果，二者必须结合。独特性是指人们在发散思维中做出不同寻常的异于他人的新奇反应的能力。独特性是发散思维的最高目标。在计算机算法中，独特性是指独立解决前人所不能解决超难问题的能力，这当然也是算法的最高境界。笔者主要着重于前两点。

事实上，计算机算法并无具体的定律规则可循，针对不同的问题，各种可能的算法千差万别，因而算法课程教学要想取得成效也是相当的不易。先驱们创造了许多算法（针对具体问题）和算法思维方式（通用性不具体针对），但遇到新问题根本不可能照搬照套，教师只是将一些概念方法灌输给学生是没有用的，必须使学生能运用这些概念方法解决问题，其中想象力和思维能力的培养尤为重要。这些不仅需要教师在教学中通过实例培训学生这方面的能力，还要有意识地引导、点拨学生，使他们能在自己的学习过程中有意识地训练这种能力。作为学生，要想得到强大的算法功力，仅靠教师和课堂远远不够，还需要自学。

集多年开发和教学的双重经验，笔者在长年对计算机算法进行精心研究的基础上，揭示了算法教与学中的一些关键技巧，遵循这些技巧，不仅能大大提高算法的教学效果，同时也为提高软件开发人员复杂思路的构思能力提供了切实有效的途径。此外，注意从趣味性吸引和多种不同的方法思路的角度，来讲解计算机算法问题，也可以达到消除算法枯燥乏味的目的。

2 史上重大的发散思维成果剖析

发散思维就是创新，就是创造性想象力，就是想别人想不到、想别人所不敢想。当然，发散思维必须以坚实的知识基础和逻辑思维基础做后盾，方法要切实可行，而不是漫无边际的遐想。

1）人工智能围棋。

众所周知，人工智能早就能战胜国际象棋特级大师，但围棋由于变化超大，人工智能围棋进展一直不大，多年一直停留在业余棋手的水平。近两年才获得了根本的突破，不仅接连战胜顶尖世界冠军，而且很快将人类顶尖棋手甩开了很长的距离。能做到这些，正是由于思维方式的根本性改变，也就是发散思维的成果。如在蒙特卡罗树搜索算法上思维方式的改变，将机器的学习过程从学习人类棋谱开始的框框中解脱出来，摒弃了人类棋谱的影响，通过机器人从零水平开始的对弈来实现自我提高。

2）伽罗华群论。

在科学史上在运用发散思维尤其是独特性的发散思维方面，最经典的例子，当属法国伽罗华发明群伦，这是独特性发散思维的光辉顶点。在高次方程的根式解上，前人一直将途经放在如何直接开发出高次方程的求根公式上，经过较长历史时期的探索，二次、三次乃至四次方程的求根公式先后被攻克，但到了五次方程，一直未有进展。伽罗华另辟蹊径，他不是着眼于如何去找到求根公式，而是运用对称性和排列组合原理发明了一套全新的理论，即群论，用这套理论去间接判断方程是否可能具有根式解，取得了前所未有的成功。

3）质数判定。

在很长的时期，判断一个数是否是质数，一直被认为是困难的，就是因为没有多项式时间算法。直到2002年，印度3位科学家M. Agrawal、N.Kayal以及N. Saxena发明了AKS质数测试算法，可以绝对准确地快速判断一个数是否质数。检查一个正整数N是否为质数，最简单的方法就是试除法，将该数N用小于等于根号N的所有素数去试除，若均无法整除，N则为素数。印度科学家从根本上突破了这种思维限制。他们的算法最终得到了学界的认可，它是正确和完整的多项式时间算法。他们的成功表明，在算法领域，发散思维能导致无限的可能性。

4）张益唐陈景润。

发散思维的多角度性有两个方面，一是在同一个方法上深挖下去，另一个是发掘出一个全新的完全不同的方法。一个是灵感，一个是思维的深度和广度。计算机算法实力需要的也是这方面的功力。许多高难度数学问题的解决，与计算机算法的思维方式是一致的，甚至就是一种算法的设计开发过程。例如，陈景润完成哥德巴赫猜想的1+2，运用的一直是前人所用到的筛法，但陈景润在深度和广度上进行了发掘，取得了前人所未能取得的成就。据部分数学家认为，陈景润已经将筛法的深度和广度开发到了极致，再无可能更进一步了。这个例子说明了发散思维所能带来的无限可能性。

3 发散思维算法实例研究

1）Hamilton环算法。

Hamilton环为著名的NP完全问题，因而在计算机算法研究中占据重要地位。学界对该算法的研究主要是基于Posa提出的旋转—延展法。长期以来，对该问题算法的大量研究，都是以Posa的旋转—延展法为基础。该方法的基本要点是：对于n个节点的无向图，每次选取1个节点，试图构成Hamilton环。比如首先选取节点a，再选取节点b，b与a有一条边相连。然后在剩余节点中找到1个与b相连的节点……以此类推，可以得到1个节点串abcd...efghij，该节点串中相邻两节点均有1条边相连。再在剩余节点中找到1个与节点j相连的节点；若找不到这样的节点，但剩余节点中有节点k与节点c相连，而节点j与b相连。此时将节点串的一部分旋转一下，得到abjihgfe...dc，然后加上k得到abjihgfe...dck，称此方法为旋转。若是k与c相连，但j与a相连，可将原节点串ja相连，断开bc，得到bajihgfe...dc，然后加上k，得到bajihgfe...dck，称此方法为延展。

不难发现，这个旋转—延展法很死板，只能在1个固定点上进行旋转和延展，当图形边数稀少时，旋转和延展的条件很难满足。尽管多年来对此问题算法的研究有很大进展，但对于稀疏图形，成功率一直不理想。

笔者在长年研究的基础上，运用发散思维，从根本上改变了Posa的方法。鉴于Posa的方法是每次加进1个节点，旋转和延展都在固定的端点进行，从而使运算受到了极大的限制。笔者的方法是，一次性全部加入n个节点，构成1个环，相邻节点可能没有边相连，也就是该环有断点，称这样的环为虚环。每次操作从某断点切掉一截，插入到环的另一个地方。切和插的原则是，尽可能使断点数变小，且在切和插之前就可以进行旋转和延展。大量实验表明，本方法大大提高了计算效率[3]。

根据算法编制了程序，计算图形是随机产生的，笔者尽可能产生难算的稀疏图形，实验数据见表1（computer: HP PC, CPU: Intel 1G, Memory:1G）。

表1 随机图形Hamilton环计算结果表

同样，成功计算国际著名网站上的图形[4]，计算时间与表格中数据相当。得到的结果与给出的答案不同，因为每个图形有多个不同的Hamilton环。

2）经典的二叉树数据结构和算法题。

国内外计算机专业数据结构和算法的经典教材，几乎都要讲到这样一个算法题，或作为习题，或作为例题[5]：对于任何一棵二叉树T，如果其叶子节点数为n0，度数为2的节点数为n2，则n0=n2+ 1。

这是一个典型的数据结构和算法类的问题，尽管属于基础简单类别，但相当具有代表性，大量本专业的学生甚至老师，都不能清晰透彻地解决该问题。

下面是教科书上关于此题的经典证法。

证明：设n为二叉树T中的节点总数，n1为度数为1的节点数，因为二叉树中所有节点的度数均小于或等于2，故n=n0+n1+n2。

另一方面，除了根节点外，其余节点都有1个分支进入，而分支都是由度数为1或度数为2的节点射出的，则n=n1+ 2n2+ 1，故n0+n1+n2=n1+ 2n2+ 1，解得n0=n2+ 1。

当笔者讲到这个问题时，总是首先让学生自己看，争取自己能看懂。这也是讲解较有深度和难度的算法问题的基本方法：学生首先必须自己预习，才可能有收获。然而，此题虽然简单，但学生往往普遍反映看不懂。

于是，笔者将本题目进行了如下修改：

假设孔子的所有男性后代，包括孔子本人，要么有1个儿子，要么2个儿子，要么1个儿子也没有。假设有1个儿子的人数为10万，2个儿子的人数为20万，求1个儿子也没有的孔子男性后代的人数。

不用说，没学生能做出。

于是笔者进一步讲解道：这相当于由孔子开始的1棵二叉树，根节点是孔子。在这棵树上，只有孔子一人不做儿子，因为孔子的父亲不在这棵树上，其他每个人都要做儿子。于是所有人的总数等于儿子的总数加1，即n0+n1+n2=n1+2n2+ 1。此等式左边是所有人的总数，右边是儿子的总数加1，解后得n0=n2+1。

学生终于明白了。

请注意此时并不意味学生就真的透彻搞懂了该问题，稍微变换一下此题目，学生还是不会。这也是算法这门课的根本特点，稍有难度的算法很难让学生顺畅接受。此题非常有趣，深入挖掘此题极其有利于学生数据结构和算法功力的提高和加深理解。

笔者总结了该问题4种完全不同的解法，每种解法都能以不同方式加强学生对数据结构和算法的理解。

解法1：儿子总数加1法。也就是上面所述的方法。

解法2：满树法。任何1个二叉树，都是通过切掉一些满二叉树的后代所得到。分两种情况：①切掉的满二叉树的根节点是独子，②切掉的满二叉树的根有1个亲兄弟。我们很容易得到，对于1个满二叉树，n0=n2+ 1。 对第1种情况，由于切掉的满二叉树是独子，故切掉后，它的父节点由原来的度数1变为度数0，也就是叶节点的个数增加了1个。切掉的满二叉树的叶节点的个数比度数为2的节点的个数多1个，正好抵消，也就是相当于：每切掉1个满二叉树，叶节点与度数为2的节点减少的数目正好一样，也就是说他不影响两者之间的大小差关系。对第2种情况，由于切掉的满二叉树有一兄弟，故切掉后，他们的父节点由原来的度数2变为度数1，也就是度数为2的节点的个数减少了1个。切掉的满二叉树的叶节点的个数比度数为2的节点的个数多1个，正好抵消，同样也就是相当于：每切掉1个满二叉树，叶节点与度数为2的节点减少的数目正好一样，同样不影响两者之间的大小差关系。由于最初的满二叉树n0=n2+ 1，故最后剩下的那棵树亦满足n0=n2+ 1，得证。

解法3：头胎二胎法。我们用一步一步增加节点的方法形成二叉树，每次增加1个节点。最初只有1个根节点。因为这个根节点的度数为0，显然，此时n0=n2+ 1。以后每加1个节点，相当于某个节点添了个儿子。有2种类型的儿子：头胎和二胎。若是头胎，相当于父节点的度数由0变为1，也就是减少了1个度数为0的节点，但新添的儿子正好度数为0，故n0和n2都没有改变。若是二胎，相当于度数为2的节点增加了1个，而度数为0的节点也增加了1个，就是新添的儿子度数为0，故两者的大小差依然不变。从而n0=n2+ 1 一直保持。

解法4：借儿子法。请注意借儿子法，首先必须证明，只要存在有节点拥有2个儿子，那就总可以将儿子借出去。因为，这是一棵树，无论如何，它总有叶子节点，从而总有能借儿子的节点。将有2个儿子的节点的儿子借1个给某叶节点，注意这时候可能会连同该儿子的后代也就是那个子树一起借出。每借出1个，相当于度数为2的节点（借出者）减少了1个，而度数为0的节点（借入者）也减少了1个。从而两者之差没有改变。到最后，因为只剩下度数为1的节点和叶节点，很容易得到此时n0=1，而n2=0，于是n0=n2+ 1。因为两者之差一直没有改变，故最初的关系也是n0=n2+ 1。

毫无疑问，对于此问题，若是学生自己能想出或透彻理解这4种解法，对于计算机算法所必需的想象力和缜密的思维力，都是极大的锻炼和提高。

4 结 语

计算机软件专业的核心是复杂思路的构思能力。这一能力从根本上体现在对算法的理解和设计上，因此，算法教学在计算机软件专业中起着举足轻重的作用，同时具备强大的算法功力亦是软件开发人员最重要的素质。然而，算法课难讲难学，无论是教学和学习，都难有固定的规则可循。笔者在多年实践研究的基础上，从发散思维的角度论述了如何锻炼和培训这方面的实力，既可供教学时参考，亦可为软件开发人员培训提供借鉴。