發(fā)散思維在計算機(jī)算法教學(xué)中的重要性

杜立智

（武漢科技大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430081）

0 引 言

在計算機(jī)算法領(lǐng)域，要想取得顯著的原創(chuàng)成果，必須具備如下3種能力：①想象力，在千頭萬緒的各種可能性中，若沒有豐富的想象力，就不可能找到有效的甚至奇妙的方法；②敏銳的邏輯領(lǐng)悟力，能敏銳地把握某種想法與所要解決問題之間的內(nèi)在邏輯聯(lián)系；③深入的思路能力，也就是沿一條長長的思維脈絡(luò)深入思考下去的能力。這3種能力缺一不可。如何取得？天分在這里有很大的作用，但在平時思考算法問題、在讀懂他人算法的過程中有意識地加以培訓(xùn)，也是有效途徑。

計算機(jī)科學(xué)專業(yè)與其他專業(yè)有顯著的不同點，這些不同點導(dǎo)致了在教與學(xué)方面的某些根本不同。其他專業(yè)大都由這兩點主導(dǎo)，一是著重于對概念原理的理解和掌握，二是長年知識經(jīng)驗的積累非常重要。這兩點在計算機(jī)科學(xué)專業(yè)當(dāng)然也具有意義，但不擁有主導(dǎo)意義。計算機(jī)科學(xué)專業(yè)最核心的方面，一是思維方式和觀念的更新，二是思維能力的強(qiáng)大。一般說來，側(cè)重于概念和原理理解的教學(xué)較容易把握，而在思維方式思維能力上，要想取得顯著的教學(xué)效果則有難度，尤其是在國內(nèi)高校課程多課時緊的情況下[1]。

例如，計算機(jī)算法課程的核心就是思維能力的培訓(xùn)，缺少思維能力，概念原理再怎么掌握都沒有實質(zhì)價值。同時，計算機(jī)算法課程也是計算機(jī)科學(xué)的最核心課程。人工智能的發(fā)展依賴于思維方式和觀念的更新，而無論什么樣的思維方式和觀念，都必須以思維能力為基礎(chǔ)，故人工智能的發(fā)展也必須建立在強(qiáng)大的算法功力上。

計算機(jī)算法有一個不同于其他課程的重要特點——需要一連串的思維，這一連串的思維由許多關(guān)鍵點構(gòu)成，這些關(guān)鍵點彼此依序而行又動態(tài)關(guān)聯(lián)。思路運(yùn)行的任一時刻，所有關(guān)鍵點都必須同時印在腦海里，且必須同時都有透徹的理解，并在需要的時候可以將此時的思路與前面的任何關(guān)鍵點關(guān)聯(lián)起來[2]。任何疏忽遺漏或一知半解都會導(dǎo)致整個思路的失敗。這正是復(fù)雜算法難以理解掌握的根本原因。相較于其他課程，計算機(jī)算法課要想取得顯著的教學(xué)效果，其難度要大得多。

1 發(fā)散思維和計算機(jī)算法簡述

心理學(xué)研究認(rèn)為發(fā)散思維（又稱輻射思維或擴(kuò)散思維）是指大腦在思維時呈現(xiàn)的一種擴(kuò)散狀態(tài)的思維模式，它表現(xiàn)為思維視野廣闊，思維呈現(xiàn)出多維發(fā)散狀。如“一題多解”“一事多寫”“一物多用”等方式。不少心理學(xué)家認(rèn)為，發(fā)散思維是創(chuàng)造性思維的最主要特點，是測定創(chuàng)造力的主要標(biāo)志之一。

具體到計算機(jī)算法中，發(fā)散思維需要具備兩點，一是想象力，二是多角度。按通常的思路難以想到的方法和解決問題的途徑，若能有效運(yùn)用發(fā)散思維，就可能迎刃而解。

發(fā)散思維有三大特性：流暢性、變通性、獨特性。流暢性反映的是發(fā)散思維的速度和數(shù)量特征，具體到計算機(jī)算法中，就是掌控一連串長的思路的能力，這個能力的取得相當(dāng)有難度，需要長時間培訓(xùn)。變通性就是克服人們頭腦中某種僵化的思維框架，按照某一新的方向來思索問題的過程，表現(xiàn)出多面性和多樣性。在計算機(jī)算法中，變通性天分在這方面具有重要作用，后天的刻苦訓(xùn)練也有顯著效果，二者必須結(jié)合。獨特性是指人們在發(fā)散思維中做出不同尋常的異于他人的新奇反應(yīng)的能力。獨特性是發(fā)散思維的最高目標(biāo)。在計算機(jī)算法中，獨特性是指獨立解決前人所不能解決超難問題的能力，這當(dāng)然也是算法的最高境界。筆者主要著重于前兩點。

事實上，計算機(jī)算法并無具體的定律規(guī)則可循，針對不同的問題，各種可能的算法千差萬別，因而算法課程教學(xué)要想取得成效也是相當(dāng)?shù)牟灰?。先?qū)們創(chuàng)造了許多算法（針對具體問題）和算法思維方式（通用性不具體針對），但遇到新問題根本不可能照搬照套，教師只是將一些概念方法灌輸給學(xué)生是沒有用的，必須使學(xué)生能運(yùn)用這些概念方法解決問題，其中想象力和思維能力的培養(yǎng)尤為重要。這些不僅需要教師在教學(xué)中通過實例培訓(xùn)學(xué)生這方面的能力，還要有意識地引導(dǎo)、點撥學(xué)生，使他們能在自己的學(xué)習(xí)過程中有意識地訓(xùn)練這種能力。作為學(xué)生，要想得到強(qiáng)大的算法功力，僅靠教師和課堂遠(yuǎn)遠(yuǎn)不夠，還需要自學(xué)。

集多年開發(fā)和教學(xué)的雙重經(jīng)驗，筆者在長年對計算機(jī)算法進(jìn)行精心研究的基礎(chǔ)上，揭示了算法教與學(xué)中的一些關(guān)鍵技巧，遵循這些技巧，不僅能大大提高算法的教學(xué)效果，同時也為提高軟件開發(fā)人員復(fù)雜思路的構(gòu)思能力提供了切實有效的途徑。此外，注意從趣味性吸引和多種不同的方法思路的角度，來講解計算機(jī)算法問題，也可以達(dá)到消除算法枯燥乏味的目的。

2 史上重大的發(fā)散思維成果剖析

發(fā)散思維就是創(chuàng)新，就是創(chuàng)造性想象力，就是想別人想不到、想別人所不敢想。當(dāng)然，發(fā)散思維必須以堅實的知識基礎(chǔ)和邏輯思維基礎(chǔ)做后盾，方法要切實可行，而不是漫無邊際的遐想。

1）人工智能圍棋。

眾所周知，人工智能早就能戰(zhàn)勝國際象棋特級大師，但圍棋由于變化超大，人工智能圍棋進(jìn)展一直不大，多年一直停留在業(yè)余棋手的水平。近兩年才獲得了根本的突破，不僅接連戰(zhàn)勝頂尖世界冠軍，而且很快將人類頂尖棋手甩開了很長的距離。能做到這些，正是由于思維方式的根本性改變，也就是發(fā)散思維的成果。如在蒙特卡羅樹搜索算法上思維方式的改變，將機(jī)器的學(xué)習(xí)過程從學(xué)習(xí)人類棋譜開始的框框中解脫出來，摒棄了人類棋譜的影響，通過機(jī)器人從零水平開始的對弈來實現(xiàn)自我提高。

2）伽羅華群論。

在科學(xué)史上在運(yùn)用發(fā)散思維尤其是獨特性的發(fā)散思維方面，最經(jīng)典的例子，當(dāng)屬法國伽羅華發(fā)明群倫，這是獨特性發(fā)散思維的光輝頂點。在高次方程的根式解上，前人一直將途經(jīng)放在如何直接開發(fā)出高次方程的求根公式上，經(jīng)過較長歷史時期的探索，二次、三次乃至四次方程的求根公式先后被攻克，但到了五次方程，一直未有進(jìn)展。伽羅華另辟蹊徑，他不是著眼于如何去找到求根公式，而是運(yùn)用對稱性和排列組合原理發(fā)明了一套全新的理論，即群論，用這套理論去間接判斷方程是否可能具有根式解，取得了前所未有的成功。

3）質(zhì)數(shù)判定。

在很長的時期，判斷一個數(shù)是否是質(zhì)數(shù)，一直被認(rèn)為是困難的，就是因為沒有多項式時間算法。直到2002年，印度3位科學(xué)家M. Agrawal、N.Kayal以及N. Saxena發(fā)明了AKS質(zhì)數(shù)測試算法，可以絕對準(zhǔn)確地快速判斷一個數(shù)是否質(zhì)數(shù)。檢查一個正整數(shù)N是否為質(zhì)數(shù)，最簡單的方法就是試除法，將該數(shù)N用小于等于根號N的所有素數(shù)去試除，若均無法整除，N則為素數(shù)。印度科學(xué)家從根本上突破了這種思維限制。他們的算法最終得到了學(xué)界的認(rèn)可，它是正確和完整的多項式時間算法。他們的成功表明，在算法領(lǐng)域，發(fā)散思維能導(dǎo)致無限的可能性。

4）張益唐陳景潤。

發(fā)散思維的多角度性有兩個方面，一是在同一個方法上深挖下去，另一個是發(fā)掘出一個全新的完全不同的方法。一個是靈感，一個是思維的深度和廣度。計算機(jī)算法實力需要的也是這方面的功力。許多高難度數(shù)學(xué)問題的解決，與計算機(jī)算法的思維方式是一致的，甚至就是一種算法的設(shè)計開發(fā)過程。例如，陳景潤完成哥德巴赫猜想的1+2，運(yùn)用的一直是前人所用到的篩法，但陳景潤在深度和廣度上進(jìn)行了發(fā)掘，取得了前人所未能取得的成就。據(jù)部分?jǐn)?shù)學(xué)家認(rèn)為，陳景潤已經(jīng)將篩法的深度和廣度開發(fā)到了極致，再無可能更進(jìn)一步了。這個例子說明了發(fā)散思維所能帶來的無限可能性。

3 發(fā)散思維算法實例研究

1）Hamilton環(huán)算法。

Hamilton環(huán)為著名的NP完全問題，因而在計算機(jī)算法研究中占據(jù)重要地位。學(xué)界對該算法的研究主要是基于Posa提出的旋轉(zhuǎn)—延展法。長期以來，對該問題算法的大量研究，都是以Posa的旋轉(zhuǎn)—延展法為基礎(chǔ)。該方法的基本要點是：對于n個節(jié)點的無向圖，每次選取1個節(jié)點，試圖構(gòu)成Hamilton環(huán)。比如首先選取節(jié)點a，再選取節(jié)點b，b與a有一條邊相連。然后在剩余節(jié)點中找到1個與b相連的節(jié)點……以此類推，可以得到1個節(jié)點串a(chǎn)bcd...efghij，該節(jié)點串中相鄰兩節(jié)點均有1條邊相連。再在剩余節(jié)點中找到1個與節(jié)點j相連的節(jié)點；若找不到這樣的節(jié)點，但剩余節(jié)點中有節(jié)點k與節(jié)點c相連，而節(jié)點j與b相連。此時將節(jié)點串的一部分旋轉(zhuǎn)一下，得到abjihgfe...dc，然后加上k得到abjihgfe...dck，稱此方法為旋轉(zhuǎn)。若是k與c相連，但j與a相連，可將原節(jié)點串ja相連，斷開bc，得到bajihgfe...dc，然后加上k，得到bajihgfe...dck，稱此方法為延展。

不難發(fā)現(xiàn)，這個旋轉(zhuǎn)—延展法很死板，只能在1個固定點上進(jìn)行旋轉(zhuǎn)和延展，當(dāng)圖形邊數(shù)稀少時，旋轉(zhuǎn)和延展的條件很難滿足。盡管多年來對此問題算法的研究有很大進(jìn)展，但對于稀疏圖形，成功率一直不理想。

筆者在長年研究的基礎(chǔ)上，運(yùn)用發(fā)散思維，從根本上改變了Posa的方法。鑒于Posa的方法是每次加進(jìn)1個節(jié)點，旋轉(zhuǎn)和延展都在固定的端點進(jìn)行，從而使運(yùn)算受到了極大的限制。筆者的方法是，一次性全部加入n個節(jié)點，構(gòu)成1個環(huán)，相鄰節(jié)點可能沒有邊相連，也就是該環(huán)有斷點，稱這樣的環(huán)為虛環(huán)。每次操作從某斷點切掉一截，插入到環(huán)的另一個地方。切和插的原則是，盡可能使斷點數(shù)變小，且在切和插之前就可以進(jìn)行旋轉(zhuǎn)和延展。大量實驗表明，本方法大大提高了計算效率[3]。

根據(jù)算法編制了程序，計算圖形是隨機(jī)產(chǎn)生的，筆者盡可能產(chǎn)生難算的稀疏圖形，實驗數(shù)據(jù)見表1（computer: HP PC, CPU: Intel 1G, Memory:1G）。

表1 隨機(jī)圖形Hamilton環(huán)計算結(jié)果表

同樣，成功計算國際著名網(wǎng)站上的圖形[4]，計算時間與表格中數(shù)據(jù)相當(dāng)。得到的結(jié)果與給出的答案不同，因為每個圖形有多個不同的Hamilton環(huán)。

2）經(jīng)典的二叉樹數(shù)據(jù)結(jié)構(gòu)和算法題。

國內(nèi)外計算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)和算法的經(jīng)典教材，幾乎都要講到這樣一個算法題，或作為習(xí)題，或作為例題[5]：對于任何一棵二叉樹T，如果其葉子節(jié)點數(shù)為n0，度數(shù)為2的節(jié)點數(shù)為n2，則n0=n2+ 1。

這是一個典型的數(shù)據(jù)結(jié)構(gòu)和算法類的問題，盡管屬于基礎(chǔ)簡單類別，但相當(dāng)具有代表性，大量本專業(yè)的學(xué)生甚至老師，都不能清晰透徹地解決該問題。

下面是教科書上關(guān)于此題的經(jīng)典證法。

證明：設(shè)n為二叉樹T中的節(jié)點總數(shù)，n1為度數(shù)為1的節(jié)點數(shù)，因為二叉樹中所有節(jié)點的度數(shù)均小于或等于2，故n=n0+n1+n2。

另一方面，除了根節(jié)點外，其余節(jié)點都有1個分支進(jìn)入，而分支都是由度數(shù)為1或度數(shù)為2的節(jié)點射出的，則n=n1+ 2n2+ 1，故n0+n1+n2=n1+ 2n2+ 1，解得n0=n2+ 1。

當(dāng)筆者講到這個問題時，總是首先讓學(xué)生自己看，爭取自己能看懂。這也是講解較有深度和難度的算法問題的基本方法：學(xué)生首先必須自己預(yù)習(xí)，才可能有收獲。然而，此題雖然簡單，但學(xué)生往往普遍反映看不懂。

于是，筆者將本題目進(jìn)行了如下修改：

假設(shè)孔子的所有男性后代，包括孔子本人，要么有1個兒子，要么2個兒子，要么1個兒子也沒有。假設(shè)有1個兒子的人數(shù)為10萬，2個兒子的人數(shù)為20萬，求1個兒子也沒有的孔子男性后代的人數(shù)。

不用說，沒學(xué)生能做出。

于是筆者進(jìn)一步講解道：這相當(dāng)于由孔子開始的1棵二叉樹，根節(jié)點是孔子。在這棵樹上，只有孔子一人不做兒子，因為孔子的父親不在這棵樹上，其他每個人都要做兒子。于是所有人的總數(shù)等于兒子的總數(shù)加1，即n0+n1+n2=n1+2n2+ 1。此等式左邊是所有人的總數(shù)，右邊是兒子的總數(shù)加1，解后得n0=n2+1。

學(xué)生終于明白了。

請注意此時并不意味學(xué)生就真的透徹搞懂了該問題，稍微變換一下此題目，學(xué)生還是不會。這也是算法這門課的根本特點，稍有難度的算法很難讓學(xué)生順暢接受。此題非常有趣，深入挖掘此題極其有利于學(xué)生數(shù)據(jù)結(jié)構(gòu)和算法功力的提高和加深理解。

筆者總結(jié)了該問題4種完全不同的解法，每種解法都能以不同方式加強(qiáng)學(xué)生對數(shù)據(jù)結(jié)構(gòu)和算法的理解。

解法1：兒子總數(shù)加1法。也就是上面所述的方法。

解法2：滿樹法。任何1個二叉樹，都是通過切掉一些滿二叉樹的后代所得到。分兩種情況：①切掉的滿二叉樹的根節(jié)點是獨子，②切掉的滿二叉樹的根有1個親兄弟。我們很容易得到，對于1個滿二叉樹，n0=n2+ 1。 對第1種情況，由于切掉的滿二叉樹是獨子，故切掉后，它的父節(jié)點由原來的度數(shù)1變?yōu)槎葦?shù)0，也就是葉節(jié)點的個數(shù)增加了1個。切掉的滿二叉樹的葉節(jié)點的個數(shù)比度數(shù)為2的節(jié)點的個數(shù)多1個，正好抵消，也就是相當(dāng)于：每切掉1個滿二叉樹，葉節(jié)點與度數(shù)為2的節(jié)點減少的數(shù)目正好一樣，也就是說他不影響兩者之間的大小差關(guān)系。對第2種情況，由于切掉的滿二叉樹有一兄弟，故切掉后，他們的父節(jié)點由原來的度數(shù)2變?yōu)槎葦?shù)1，也就是度數(shù)為2的節(jié)點的個數(shù)減少了1個。切掉的滿二叉樹的葉節(jié)點的個數(shù)比度數(shù)為2的節(jié)點的個數(shù)多1個，正好抵消，同樣也就是相當(dāng)于：每切掉1個滿二叉樹，葉節(jié)點與度數(shù)為2的節(jié)點減少的數(shù)目正好一樣，同樣不影響兩者之間的大小差關(guān)系。由于最初的滿二叉樹n0=n2+ 1，故最后剩下的那棵樹亦滿足n0=n2+ 1，得證。

解法3：頭胎二胎法。我們用一步一步增加節(jié)點的方法形成二叉樹，每次增加1個節(jié)點。最初只有1個根節(jié)點。因為這個根節(jié)點的度數(shù)為0，顯然，此時n0=n2+ 1。以后每加1個節(jié)點，相當(dāng)于某個節(jié)點添了個兒子。有2種類型的兒子：頭胎和二胎。若是頭胎，相當(dāng)于父節(jié)點的度數(shù)由0變?yōu)?，也就是減少了1個度數(shù)為0的節(jié)點，但新添的兒子正好度數(shù)為0，故n0和n2都沒有改變。若是二胎，相當(dāng)于度數(shù)為2的節(jié)點增加了1個，而度數(shù)為0的節(jié)點也增加了1個，就是新添的兒子度數(shù)為0，故兩者的大小差依然不變。從而n0=n2+ 1 一直保持。

解法4：借兒子法。請注意借兒子法，首先必須證明，只要存在有節(jié)點擁有2個兒子，那就總可以將兒子借出去。因為，這是一棵樹，無論如何，它總有葉子節(jié)點，從而總有能借兒子的節(jié)點。將有2個兒子的節(jié)點的兒子借1個給某葉節(jié)點，注意這時候可能會連同該兒子的后代也就是那個子樹一起借出。每借出1個，相當(dāng)于度數(shù)為2的節(jié)點（借出者）減少了1個，而度數(shù)為0的節(jié)點（借入者）也減少了1個。從而兩者之差沒有改變。到最后，因為只剩下度數(shù)為1的節(jié)點和葉節(jié)點，很容易得到此時n0=1，而n2=0，于是n0=n2+ 1。因為兩者之差一直沒有改變，故最初的關(guān)系也是n0=n2+ 1。

毫無疑問，對于此問題，若是學(xué)生自己能想出或透徹理解這4種解法，對于計算機(jī)算法所必需的想象力和縝密的思維力，都是極大的鍛煉和提高。

4 結(jié) 語

計算機(jī)軟件專業(yè)的核心是復(fù)雜思路的構(gòu)思能力。這一能力從根本上體現(xiàn)在對算法的理解和設(shè)計上，因此，算法教學(xué)在計算機(jī)軟件專業(yè)中起著舉足輕重的作用，同時具備強(qiáng)大的算法功力亦是軟件開發(fā)人員最重要的素質(zhì)。然而，算法課難講難學(xué)，無論是教學(xué)和學(xué)習(xí)，都難有固定的規(guī)則可循。筆者在多年實踐研究的基礎(chǔ)上，從發(fā)散思維的角度論述了如何鍛煉和培訓(xùn)這方面的實力，既可供教學(xué)時參考，亦可為軟件開發(fā)人員培訓(xùn)提供借鑒。