最短路徑求解的教學(xué)問題

《最短路徑求解的教學(xué)問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、《數(shù)據(jù)結(jié)構(gòu)》屮Dijkstra算法的教學(xué)問題摘要:根據(jù)《數(shù)據(jù)結(jié)構(gòu)》的教學(xué)，結(jié)合學(xué)生的接受能力，分別應(yīng)用肓觀圖示法、數(shù)據(jù)表格法等，由淺入深、從直觀到抽象探討了Dijkstra算法的講授問題,有利于改善各類最短路徑求解的教學(xué)效果。關(guān)鍵詞:數(shù)據(jù)結(jié)構(gòu)；Dijkstra；授短路徑;教學(xué)研究《數(shù)據(jù)結(jié)構(gòu)》是一門比較獨特的課程，內(nèi)容涉及面廣而散，卻具內(nèi)在聯(lián)系；知識很抽象，實用性卻很強,尤其是與計算機應(yīng)用結(jié)合得I?分緊密。在《數(shù)據(jù)結(jié)構(gòu)》課教學(xué)上普遍會遇到如下矛盾：內(nèi)容繁多與課時冇限的矛盾;知識抽象與學(xué)生接受能力的矛盾;講授零散與知識整體性的矛盾;學(xué)習(xí)知識為培養(yǎng)能力的矛盾。解決好上述矛盾，對提高教學(xué)質(zhì)量是十分重要

2、的。本文僅以最短路徑的求解為例，來探討有關(guān)《數(shù)據(jù)結(jié)構(gòu)》課的教學(xué)問題。1、最短路徑求解的講授內(nèi)容最短路徑求解主要講授3個方而的內(nèi)容：?單源最短路徑(即從一點出發(fā)到其他各點的最短距離)；?所有點到點之間的最短路徑；?對完全圖每個頂點恰好訪問一次，而回路的總長度最短(即推銷員問題)o單源最短路徑求解是最基本的，也是教學(xué)的重點。學(xué)好它對處理計算機網(wǎng)絡(luò)、交通線路等問題有幫助。2、多角度講解Dijkstra算法講授求解算法的方式很多，是先用抽彖的描述，還是先用直觀的實例？可以根據(jù)所講算法的特點，采取不同的方式。就Dijkstra算法而言，如果開始就介紹求解的步驟，由于步驟繁多,學(xué)牛接受起來會很勉強，教V效

3、果不會好。根據(jù)學(xué)牛接受能力、思維方式及理解問題上存在的差異，筆者從實例出發(fā)采用了肓?觀圖示法教學(xué)，使他們對Dijkstra算法先有一個感性的認識;進一步再采用數(shù)據(jù)表格法教學(xué)，使他們認識各個所需數(shù)據(jù)Z間的聯(lián)系；在此棊礎(chǔ)上，再采用步驟描述法教學(xué)，使學(xué)生達到理性的認識,最后對Dijkstra算法做一個嚴謹闡釋。這樣，多角度逐層深入講授，可以使學(xué)生掌握授矩路徑各類問題最佳的求解方法。首先,通過講解一個簡單的實例使學(xué)牛初步了解Dijkstra算法的原理：在如圖1所示的帶權(quán)圖例子中，問a和f之間最短通路的長度是多少？帶權(quán)圖Dijkstra算法是這樣解決問題的:求從a到各個頂點的最短通路,直至到f為止。從a

4、開始到除a以外的頂點的通路有(a,b)和(a,c)。(a,b)和(a,c)的長度分別為4和2,c是與a最靠近的頂點?？梢酝ㄟ^杳看只經(jīng)過a和c的所有通路，來求出下一個與a最靠近的頂點。到b的最短通路現(xiàn)在是長度為3的(a,c,b),比長度為4的仏b)短，而到e的最短通路是長度為12的(a,c,e)o所以，下一個與a最靠近的頂點是b。為了求岀第四個與a授靠近的頂點，只需檢查經(jīng)過了a,c和b的那些通路。有長度為8的到d的通路即(a,c,b,d),也有長度為10的到d的通路，即(a,c,d)和長度為12到e的通路,BP(a,c,e)o所以,d是下一個與a最靠近的頂點。以此類推,d到e的通路是(a,c,b

5、,d,e),長度為10oa到f的通路最短為(a,c,b,d,e,f),長度為13o通過這個簡單實例，可以使學(xué)牛対Dijkstra算法產(chǎn)生一個初步的印象。若使他們對Dijkstra算法有精確的認識，必須進一步用步驟描述法教學(xué)。步驟描述法比鮫抽彖,難以講清楚，亦先用肓觀圖示法教學(xué)。不妨結(jié)合下面的具體例題來講授。例1求下列有權(quán)圖小a到f的最短路徑(見圖2)。圖2帶權(quán)圖可采取比較直觀的帶權(quán)圖講授求解過程,參見圖3~圖8,Dijkstra算法的每一次迭代都可以畫出新帶權(quán)圖，圖屮加上人括號的頂點表示從a開始最短路徑所經(jīng)過的點。當(dāng)?shù)絝時，算法終止。這樣找到從a到f的最短通路是a,e,d,f,長度為60。

6、￡100(a)二U60圖4求解過程之二圖5求解過程之三圖6求解過程之四圖7求解過程之五圖8求解過程Z六這種直觀圖示法講解起來更為形彖，學(xué)生容易接受。求解最短路徑問題有時還對以將所需要的數(shù)據(jù)列成表格，這樣不但可減少-?次次畫圖的麻煩，節(jié)省了篇幅，還可以明了各數(shù)據(jù)之間的聯(lián)系。這種數(shù)據(jù)表格法成為肯觀圖示法到步驟描述法的過渡。可上面的例了用數(shù)據(jù)表格法講解。引進一個輔助向量D,它的每個分量D[i]表示當(dāng)前所找到的從始點a到每個終點的最短路徑長度。它的初態(tài)為：若兩個頂點之間有狐，則D[i]為狐上的權(quán)值；否則置D[i]為8。圖9說明最短路徑的求解過程：皺占—、八、、從a到各終點的D值和最短路徑的求解過程i=

7、li=2i=3i=4i=5bOOOOOOOOOO無C10(a,c)dOO60(a,c,d)50(a,e,d)c30(a,e)30(a,e)f100(a,f)100(a,f)90(a,c,f)60(a,c,d,f)最短路徑點cedfs{a,c}{a,c,e}{a,c,e,d}{a,c,e,d,f}圖9表格法求解過程對于以上描述步驟,記憶起來的首要困難是術(shù)語，如P標記,T標記。其實,不妨將P標記看作最