實(shí)例驅(qū)動(dòng)教學(xué)在《算法設(shè)計(jì)與分析》課程中的探討

摘 要：實(shí)例驅(qū)動(dòng)教學(xué)是一種具有實(shí)踐性和啟發(fā)性的新型教學(xué)方法?！端惴ㄔO(shè)計(jì)與分析》是實(shí)踐性較強(qiáng)的一門(mén)課程。教學(xué)內(nèi)容的比較抽象與復(fù)雜，學(xué)生在這門(mén)課程的學(xué)習(xí)中會(huì)感到困難。本文針對(duì)該課程教學(xué)內(nèi)容，對(duì)典型實(shí)例驅(qū)動(dòng)教學(xué)在《算法設(shè)計(jì)與分析》課程中做了一些探索。通過(guò)典型的實(shí)例驅(qū)動(dòng)教學(xué)，一個(gè)抽象的算法更具體化與形象化，使學(xué)生能快速理解算法的原理及各個(gè)算法之間的主要區(qū)別，同時(shí)激發(fā)他們學(xué)習(xí)的興趣和熱情，從而提高教學(xué)質(zhì)量和教學(xué)效果。

關(guān)鍵詞：算法設(shè)計(jì)與分析 實(shí)例驅(qū)動(dòng)教學(xué) 背包問(wèn)題 教學(xué)改革

中圖分類(lèi)號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1673-9795（2013）06（a）-0070-01

1 問(wèn)題的提出

《算法設(shè)計(jì)與分析》[1]是實(shí)踐性較強(qiáng)的一門(mén)課程。這門(mén)課程的主要目的，通過(guò)對(duì)計(jì)算機(jī)算法系統(tǒng)的學(xué)習(xí)與研究，掌握算法設(shè)計(jì)算法策略和技巧，培養(yǎng)學(xué)生對(duì)算法的計(jì)算復(fù)雜性正確分析的能力，對(duì)不同的實(shí)際問(wèn)題設(shè)計(jì)出清晰高效的算法，為獨(dú)立設(shè)計(jì)算法和對(duì)算法進(jìn)行復(fù)雜性分析奠定堅(jiān)實(shí)的理論基礎(chǔ)。軟件的效率和穩(wěn)定性取決于軟件中所采用的算法，學(xué)習(xí)《算法設(shè)計(jì)與分析》課程，可以開(kāi)闊編程思路，有助于編寫(xiě)出高效程序。因此，提高《算法設(shè)計(jì)與分析》課程教學(xué)水平有著極其深遠(yuǎn)的意義和重要的作用。

《算法設(shè)計(jì)與分析》內(nèi)容的比較抽象與復(fù)雜，從學(xué)生的普遍反映來(lái)看，這是一門(mén)比較難的課程。《算法設(shè)計(jì)與分析》課程的教學(xué)內(nèi)容按算法分類(lèi)組織。在教科書(shū)中[2]，每一章對(duì)應(yīng)一種算法，主要內(nèi)容涵蓋了動(dòng)態(tài)規(guī)劃、貪心法、回溯法和分支限界法經(jīng)典的算法。本文針對(duì)該課程，對(duì)典型實(shí)例驅(qū)動(dòng)教學(xué)在《算法設(shè)計(jì)與分析》教學(xué)中的應(yīng)用做了一些探索。通過(guò)典型的實(shí)例教學(xué)，一個(gè)抽象的算法使其更具體化、形象化，學(xué)生能快速理解各種算法的原理及算法之間的區(qū)別，因此，在《算法設(shè)計(jì)與分析》教學(xué)中合理利用典型實(shí)例，激發(fā)學(xué)生學(xué)習(xí)興趣和熱情，從而提高教學(xué)效果。

2 0-1背包問(wèn)題實(shí)例

0-1背包問(wèn)題是經(jīng)典組合優(yōu)化問(wèn)題[3]，有著廣泛的實(shí)際應(yīng)用背景，0-1背包問(wèn)題比較簡(jiǎn)單，把抽象的，復(fù)雜的算法應(yīng)用到該問(wèn)題便于同學(xué)理解和掌握。0-1背包問(wèn)題描述為：給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大。

3 動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化的一種方法，該方法是由美國(guó)數(shù)學(xué)家貝爾曼等人提出的。用于解決生產(chǎn)管理、工程技術(shù)等方面的許多問(wèn)題，并建立了運(yùn)籌學(xué)的一個(gè)新的分支，即動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題。但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。動(dòng)態(tài)規(guī)劃方法能夠把復(fù)雜問(wèn)題的算法從指數(shù)階的計(jì)算量減少到多項(xiàng)式階。

4 貪心算法

貪心算法通過(guò)一系列的選擇來(lái)得到問(wèn)題的最優(yōu)解，它所做的每一個(gè)選擇都是當(dāng)前狀態(tài)最好的選擇，即貪心選擇。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。用貪心算法不能求解0-1背包問(wèn)題，但能解決背包問(wèn)題，背包問(wèn)題與0-1背包問(wèn)題類(lèi)似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，即xi∈[0，1]。

5 回溯算法

回溯法在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)系統(tǒng)地搜索一個(gè)問(wèn)題的所有解或任一解。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解：如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。

如果采用回溯法解決0-1背包問(wèn)題，如一個(gè)結(jié)點(diǎn)的左兒子結(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)就搜索其左子樹(shù)。而對(duì)于右子樹(shù)，需要用貪心算法構(gòu)造一個(gè)上界函數(shù)，上界函數(shù)是通過(guò)講將0-1背包問(wèn)題松弛為背包問(wèn)題利用貪心算法求得的，這個(gè)函數(shù)表明這個(gè)結(jié)點(diǎn)的子樹(shù)所能達(dá)到的可能的最優(yōu)值，只在這個(gè)上界函數(shù)的值超過(guò)當(dāng)前最優(yōu)解時(shí)才進(jìn)入搜索。隨著搜索進(jìn)程的推進(jìn)，最優(yōu)解不斷得到加強(qiáng)，對(duì)搜索的限制就越來(lái)越嚴(yán)格。如果這個(gè)上界小于當(dāng)前值Bestf，說(shuō)明該子樹(shù)不可能包含最優(yōu)解，即可以被“剪枝”。

6 分支限界法

分支限界法類(lèi)似于回溯法，也是一種在問(wèn)題的解空間樹(shù)上搜索問(wèn)題解的算法。分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。采用分支限界法解決0-1背包問(wèn)題，同樣需要用到貪心算法構(gòu)造的上界函數(shù)。所不同的是，這個(gè)上界函數(shù)的作用不在于判斷是否進(jìn)入一個(gè)結(jié)點(diǎn)的子樹(shù)繼續(xù)搜索，因?yàn)樵谒阉鞯竭_(dá)葉節(jié)點(diǎn)之前，大家也無(wú)法知道已經(jīng)得到的最優(yōu)解是什么。在這里，可用一個(gè)最大堆來(lái)實(shí)現(xiàn)活結(jié)點(diǎn)的優(yōu)先隊(duì)列，上界函數(shù)的值將作為優(yōu)先級(jí)，這樣一旦有一個(gè)葉結(jié)點(diǎn)成為擴(kuò)展結(jié)點(diǎn)，就表明已經(jīng)找到了最優(yōu)解。

7 結(jié)語(yǔ)

通過(guò)典型0-1背包問(wèn)題實(shí)例，學(xué)生可以快速理解各種算法的基本思想、特點(diǎn)及算法之間區(qū)別，便于理解與掌握。筆者在這門(mén)課程的教學(xué)過(guò)程中深刻地體會(huì)到，要上好這門(mén)課，教師要注意觀察學(xué)生的課堂反應(yīng)及接受能力，采用適當(dāng)?shù)慕虒W(xué)方法。實(shí)踐證明，《算法設(shè)計(jì)與分析》實(shí)例教學(xué)方法是一種將抽象算法理論與實(shí)際典型實(shí)例相結(jié)合，讓學(xué)生帶著感興趣的問(wèn)題進(jìn)入課程的學(xué)習(xí)，其探究能力和創(chuàng)新意識(shí)得到了較好的培養(yǎng)，同時(shí)培養(yǎng)學(xué)生分析問(wèn)題及解決問(wèn)題的能力。

參考文獻(xiàn)

[1]阿霍.計(jì)算機(jī)算法設(shè)計(jì)與分析：英文版，[M].北京：機(jī)械工業(yè)出版社，2006.

[2]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2010，5.

[3]王曉云，陳業(yè)綱.計(jì)算機(jī)算法設(shè)計(jì)、分析與實(shí)現(xiàn)[M].北京：科學(xué)出版社，2012.