李群　趙玉霞

摘 要：為了更好的發(fā)揮探究式學(xué)習(xí)理論對算法教學(xué)的促進(jìn)作用，在探究式學(xué)習(xí)理論的基礎(chǔ)上，研究并實(shí)踐了以探究式教學(xué)為主線，結(jié)合啟發(fā)式、項(xiàng)目式教學(xué)方法的教學(xué)模式。本文以最短路徑算法的講授過程為例，具體講述探究式學(xué)習(xí)在算法教學(xué)中的應(yīng)用。讓學(xué)生領(lǐng)悟探究式學(xué)習(xí)思想，教學(xué)結(jié)果表明，學(xué)生獲得了很大的進(jìn)步，在課程項(xiàng)目中將迪杰斯特拉算法應(yīng)用到不同的生產(chǎn)背景中。

關(guān)鍵詞：算法教學(xué)；探究式學(xué)習(xí)；迪杰斯特拉算法；自主學(xué)習(xí)

中圖分類號：TN915.0

算法的設(shè)計(jì)與分析是計(jì)算機(jī)科學(xué)的核心問題之一，通過學(xué)習(xí)，可以掌握算法設(shè)計(jì)的常用方法，以便利用這些方法去獨(dú)立設(shè)計(jì)解決各類實(shí)際問題。因?yàn)樗惴ǔ橄笮愿?，邏輯性極強(qiáng)，要求學(xué)生具有較高的抽象思維能力，導(dǎo)致學(xué)生在算法學(xué)習(xí)中往往存在很大的難度，這也給教學(xué)提出了較高要求。

探究式教學(xué)是一種仿照科學(xué)研究的過程來組織教學(xué)的方法，讓學(xué)生在掌握知識的同時(shí)體驗(yàn)、理解和應(yīng)用科學(xué)研究的方法，加大邏輯思維寬度，從而提高解決問題的能力。這種教學(xué)模式非常適用于算法教學(xué)。教師根據(jù)教學(xué)內(nèi)容，通過設(shè)置問題情境，引導(dǎo)輔助學(xué)生去自主探究算法的設(shè)計(jì)、實(shí)現(xiàn)直至優(yōu)化，相比傳統(tǒng)教學(xué)方式，會(huì)更大程度激發(fā)學(xué)生的學(xué)習(xí)興趣，更好的培養(yǎng)學(xué)生解決問題的能力和創(chuàng)新能力。

筆者在多年的算法與數(shù)據(jù)結(jié)構(gòu)的教學(xué)中，通過不斷的嘗試和探索，提出了探究式教學(xué)的授課模式，并取得了良好的教學(xué)效果。

現(xiàn)以單源最短路徑（Single-source Shortest Path，SSSP）問題的教學(xué)實(shí)施過程為例，介紹探究式教學(xué)在算法教學(xué)中的應(yīng)用模式。

1 探究式教學(xué)方法在最短路徑問題教學(xué)中的應(yīng)用

單源最短路徑問題是圖論研究中的一個(gè)經(jīng)典問題，目標(biāo)是找出從某個(gè)定源頂點(diǎn)到每個(gè)頂點(diǎn)的最小價(jià)值路徑。該算法在許多領(lǐng)域有著廣泛應(yīng)用，比如文獻(xiàn)1描述了一種K最短路徑在通信網(wǎng)絡(luò)上的一種應(yīng)用。在教學(xué)中基于探究式學(xué)習(xí)理論，完成了教學(xué)設(shè)計(jì)與實(shí)施。

1.1 教學(xué)過程設(shè)計(jì)

（1）學(xué)生的背景知識

該教學(xué)內(nèi)容安排在圖的深度優(yōu)先遍歷（Depth-first Search，DFS）、廣度優(yōu)先遍歷（Breadth-first Search，BFS）、最小生成樹（Minimum Spanning Tree）等問題之后，此時(shí)學(xué)生已經(jīng)掌握了圖的基本概念、存儲方式、遍歷以及生成樹的簡單應(yīng)用。

（2）背景知識回顧

由于本節(jié)講解的內(nèi)容與學(xué)生掌握的背景知識有比較大的聯(lián)系，甚至使用了背景知識中相似的解題思路。因此有選擇的復(fù)習(xí)BFS、普里姆（Prim）算法，并重點(diǎn)復(fù)習(xí)兩種算法均使用了“層次遍歷”的思路。讓在學(xué)生鞏固已學(xué)知識的同時(shí)，將兩個(gè)算法聯(lián)系在了一起，并引出本節(jié)算法中的基本思路，讓學(xué)生消除對新算法的畏懼感，并增加他們對新算法的興趣。

（3）問題情境與探究過程設(shè)計(jì)

借助教材中提出的交通咨詢問題：一位旅客如何從A地到B地找到一條中轉(zhuǎn)最少的路線，啟發(fā)學(xué)生去思考能否通過圖的遍歷實(shí)現(xiàn)最短路徑的尋求。學(xué)生在對這個(gè)問題分析中，比較容易想到廣度優(yōu)先遍歷算法（BFS）：從A出發(fā)對圖進(jìn)行廣度優(yōu)先搜索，一旦遇到頂點(diǎn)B就終止。[2]學(xué)生需要將教材中的BFS算法加以修改：記錄所經(jīng)過的結(jié)點(diǎn)的父結(jié)點(diǎn)，實(shí)現(xiàn)這一問題的求解。

如何在一個(gè)非遞歸且反復(fù)調(diào)用不同結(jié)點(diǎn)的算法中記錄每個(gè)訪問的結(jié)點(diǎn)的父結(jié)點(diǎn)，這里需要發(fā)揮學(xué)生的探究能力。學(xué)生在課前的預(yù)習(xí)工作，課堂上的工具書或電子設(shè)備發(fā)揮重大作用。讓學(xué)生在短時(shí)間內(nèi)進(jìn)行頭腦風(fēng)暴，尋找最佳答案。緊迫感也有利于讓學(xué)生更加集中注意力，提升他們對競爭勝利的渴望。使用前綴樹（Trie）是一個(gè)比較好的解決方案，將其應(yīng)用到BFS這個(gè)已熟悉的算法中，能夠讓他們更快的熟悉前綴樹的方法；減輕在學(xué)習(xí)新算法的同時(shí)對前綴樹的陌生感，降低學(xué)習(xí)新知識的困難度。

經(jīng)過一路的引導(dǎo)，雖然課程還沒有講解到新的算法，但是學(xué)生已經(jīng)通過對背景的知識的復(fù)習(xí)和探究理解了新算法的基本思路和部分知識要點(diǎn)。

最短路程往往要比最短中轉(zhuǎn)點(diǎn)更具有實(shí)用性和現(xiàn)實(shí)價(jià)值，在此設(shè)置貼近學(xué)生的校園導(dǎo)航問題，作為項(xiàng)目任務(wù)布置給學(xué)生。為了完成這一項(xiàng)目，如何實(shí)現(xiàn)最短路徑算法，這里引入迪杰斯特拉（Dijkstra）算法。因?yàn)榈辖芩固乩惴ㄊ褂昧素澬乃惴ǎ℅reedy Algorithm）理論，且貪心算法不易證明其正確性。因此需要通過前面提及的“層次遍歷”思路，將迪杰斯特拉算法稍作解釋，重點(diǎn)理解“層次遍歷”思路在其算法中的應(yīng)用。由于學(xué)生對“層次遍歷”比較了解，故不會(huì)對此算法產(chǎn)生強(qiáng)烈抵觸。詢問學(xué)生怎么能夠說明這個(gè)算法的就是正確的呢？暫且不去證明，使用教材中給定的交通圖[2]，指定兩個(gè)地點(diǎn)，使用迪杰斯特拉算法做一次最短路徑查找工作，并找出最短路徑。通過這個(gè)方法讓學(xué)生感覺到這個(gè)算法可能更可靠，也讓學(xué)生進(jìn)一步理清算法思路，為算法的證明過程打下一個(gè)基礎(chǔ)。

下一步結(jié)合貪心算法的理論，來證明最短路徑的正確性。通過貪心算法性質(zhì)：一個(gè)全局最優(yōu)解可以通過局部最優(yōu)解選擇來達(dá)到[3]，講解最短路徑的子路徑是最短路徑這條重要性質(zhì)。使用文獻(xiàn)3中的定理24.6證明迪杰斯特拉算法的正確性。通過推出一組矛盾來證明迪杰斯特拉算法的結(jié)果是一個(gè)最優(yōu)解。學(xué)生則進(jìn)一步思考最短路徑的尋找，每一步選擇距離起點(diǎn)路徑最短的結(jié)點(diǎn)，這也正是Dijstra算法的核心思想。

至此迪杰斯特拉算法的理論基本講解完成，進(jìn)入迪杰斯特拉算法實(shí)現(xiàn)環(huán)節(jié)。從簡單開始，講解不記錄經(jīng)過路徑和路徑權(quán)值的算法，并分析時(shí)間空間復(fù)雜度，減輕理解的難度。然后讓學(xué)生分組討論教材上的給出的代碼，并嘗試分析代碼含義，提出教材中算法的優(yōu)缺點(diǎn)，及其改進(jìn)思路，寫出改進(jìn)算法。由于前面已經(jīng)講解過前綴樹，并做適當(dāng)引導(dǎo)。讓小組代表回答分析結(jié)果，并給出改進(jìn)思路。參考代碼如下：

//使用最小前綴樹，生成路徑：

int ShortestPath_DJK（Graph*g，int beginIndex，int*pathValue，int*minPreTree）

{

int visited[]；

for（i=0；ivernum；i++）{

visited[i]=0；

//獲取beginIndex->w邊的權(quán)值，如果不存在 返回MAX_INT

pathValue[i]=GetArcValue（g，beginIndex，i）；

if（pathValue[i]！=INT_MAX）

minPreTree[i]=beginIndex；

else

minPreTree[i]=-1；

}

visited[beginIndex]=1；

pathValue[beginIndex]=0；

for（i=1；ivernum；i++）{

minValue=INT_MAX；

for（j=0；jvernum；j++）

if（visited[j]==0 && pathValue[j] < minValue）{

minIndex=j；

minValue=pathValue[j]；

}

if（minValue==INT_MAX）

return 1；

visited[minIndex]=1；

for（j=0；jvernum；j++）{

int value=GetArcValue（g，minIndex，j）；

if（visited[j]==0 && minValue

pathValue[j]=minValue+value；

minPreTree[j]=minIndex；

}

}

}

return 1；

}

1.2 學(xué)生探究實(shí)施過程

（1）分組討論

學(xué)生以學(xué)習(xí)小組為單位，針對教師所設(shè)置的情境問題，開展探究工作。該過程中，學(xué)生必須在課前做好預(yù)習(xí)，并注重參考書籍、電子設(shè)備在課堂上的作用，學(xué)生通過合理的查閱文獻(xiàn)資料，提出最短路徑的解決方案。

（2）項(xiàng)目開發(fā)及提交

以小組為單位，依據(jù)所提出的設(shè)計(jì)方案，合理的解決校園導(dǎo)航問題。完成項(xiàng)目的各項(xiàng)任務(wù)，也可在基本要求上加以改善和豐富。

（3）小組交流

以討論、答辯、演講等形式為學(xué)生搭建一個(gè)平臺，各小組將各自的設(shè)計(jì)方案、思路、算法實(shí)現(xiàn)方法等進(jìn)行交流切磋。學(xué)生可以在短時(shí)間內(nèi)接受多種思路、解決方案和知識，通過互相借鑒，使學(xué)習(xí)效率得到最大化。

（4）總結(jié)及評價(jià)

在此階段中，學(xué)生對該教學(xué)內(nèi)容進(jìn)行總結(jié)，從圖的最短路問題概念的厘定、基本算法到算法的優(yōu)化，進(jìn)行完善的梳理；并針對本組所做的探究工作，從思路、研究方法、項(xiàng)目成效等方面進(jìn)行客觀評價(jià)。

教師對各小組的探究過程、方案、項(xiàng)目進(jìn)行分析和評價(jià)，并為學(xué)生推薦最短路徑及相關(guān)問題的參考資料，如書籍、期刊文章、博客等，供學(xué)生開展更深入的探究活動(dòng)。

2 教學(xué)成效

在校園導(dǎo)航項(xiàng)目的開發(fā)中，學(xué)生通過深入探究最短路徑問題，改進(jìn)了教材中的迪杰斯特拉算法，將時(shí)間復(fù)雜度由O（n3）提高到O（n2），空間性能也有所提高。而且學(xué)生在某知名IT企業(yè)招聘面試中，憑借此項(xiàng)目獲得面試官的肯定，對算法的優(yōu)化得到認(rèn)同。

在最短路徑算法教學(xué)中，通過開展探究式教學(xué)，讓圖論中的這個(gè)復(fù)雜問題更具趣味性，極大的調(diào)動(dòng)了學(xué)生的學(xué)習(xí)積極性；并幫助學(xué)生了解科學(xué)研究的過程，逐步掌握科學(xué)研究的方法，在探究的過程中體驗(yàn)到知識帶來的樂趣。

3 結(jié)束語

在算法教學(xué)中，結(jié)合各種算法的特點(diǎn)，筆者實(shí)施了探究式教學(xué)。巧妙布設(shè)問題情境，通過對問題的探究，一步步引領(lǐng)學(xué)生構(gòu)建起新知識框架，使課堂教學(xué)在探究中逐步推進(jìn)。學(xué)生從中學(xué)會(huì)了如何發(fā)現(xiàn)問題，解決問題，拓寬了思路，并逐步建立起算法設(shè)計(jì)與分析的理念，善于發(fā)現(xiàn)已有算法和程序的弱點(diǎn)并加以改進(jìn)。

參考文獻(xiàn)：

[1]毛少武，張煥國，黃崇超.改進(jìn)的K最短路徑算法在通信網(wǎng)絡(luò)中的應(yīng)用[J].武漢大學(xué)學(xué)報(bào)（理學(xué)版），2013（06）：534-538.

[2]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，1997.

[3]Thoms H.Cormen，Charles E.Leiserson，Ronald L.Rivest Clifford Stein.潘金貴，顧鐵成，李成法，譯.算法導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2011.

作者簡介：李群（1978-），女，山東惠民人，講師，碩士，研究方向：群智能、計(jì)算機(jī)軟件技術(shù)教學(xué)等。

作者單位：濱州學(xué)院信息工程系，山東濱州 256603

基金項(xiàng)目：濱州學(xué)院教學(xué)研究項(xiàng)目（項(xiàng)目編號：BYJYYB200916）。