實例驅動教學在《算法設計與分析》課程中的探討

摘 要：實例驅動教學是一種具有實踐性和啟發性的新型教學方法。《算法設計與分析》是實踐性較強的一門課程。教學內容的比較抽象與復雜，學生在這門課程的學習中會感到困難。本文針對該課程教學內容，對典型實例驅動教學在《算法設計與分析》課程中做了一些探索。通過典型的實例驅動教學，一個抽象的算法更具體化與形象化，使學生能快速理解算法的原理及各個算法之間的主要區別，同時激發他們學習的興趣和熱情，從而提高教學質量和教學效果。

關鍵詞：算法設計與分析 實例驅動教學 背包問題 教學改革

中圖分類號：G642 文獻標識碼：A 文章編號：1673-9795（2013）06（a）-0070-01

1 問題的提出

《算法設計與分析》[1]是實踐性較強的一門課程。這門課程的主要目的，通過對計算機算法系統的學習與研究，掌握算法設計算法策略和技巧，培養學生對算法的計算復雜性正確分析的能力，對不同的實際問題設計出清晰高效的算法，為獨立設計算法和對算法進行復雜性分析奠定堅實的理論基礎。軟件的效率和穩定性取決于軟件中所采用的算法，學習《算法設計與分析》課程，可以開闊編程思路，有助于編寫出高效程序。因此，提高《算法設計與分析》課程教學水平有著極其深遠的意義和重要的作用。

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

2 0-1背包問題實例

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

3 動態規劃算法

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

4 貪心算法

貪心算法通過一系列的選擇來得到問題的最優解，它所做的每一個選擇都是當前狀態最好的選擇，即貪心選擇。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。在一些情況下，即使貪心算法不能得到整體最優解，其最終結果卻是最優解的很好近似。用貪心算法不能求解0-1背包問題，但能解決背包問題，背包問題與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，即xi∈[0，1]。

5 回溯算法

回溯法在問題的解空間樹中，按深度優先策略，從根結點出發系統地搜索一個問題的所有解或任一解。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解：如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續按深度優先策略搜索。

如果采用回溯法解決0-1背包問題，如一個結點的左兒子結點是一個可行結點就搜索其左子樹。而對于右子樹，需要用貪心算法構造一個上界函數，上界函數是通過講將0-1背包問題松弛為背包問題利用貪心算法求得的，這個函數表明這個結點的子樹所能達到的可能的最優值，只在這個上界函數的值超過當前最優解時才進入搜索。隨著搜索進程的推進，最優解不斷得到加強，對搜索的限制就越來越嚴格。如果這個上界小于當前值Bestf，說明該子樹不可能包含最優解，即可以被“剪枝”。

6 分支限界法

分支限界法類似于回溯法，也是一種在問題的解空間樹上搜索問題解的算法。分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹。采用分支限界法解決0-1背包問題，同樣需要用到貪心算法構造的上界函數。所不同的是，這個上界函數的作用不在于判斷是否進入一個結點的子樹繼續搜索，因為在搜索到達葉節點之前，大家也無法知道已經得到的最優解是什么。在這里，可用一個最大堆來實現活結點的優先隊列，上界函數的值將作為優先級，這樣一旦有一個葉結點成為擴展結點，就表明已經找到了最優解。

7 結語

通過典型0-1背包問題實例，學生可以快速理解各種算法的基本思想、特點及算法之間區別，便于理解與掌握。筆者在這門課程的教學過程中深刻地體會到，要上好這門課，教師要注意觀察學生的課堂反應及接受能力，采用適當的教學方法。實踐證明，《算法設計與分析》實例教學方法是一種將抽象算法理論與實際典型實例相結合，讓學生帶著感興趣的問題進入課程的學習，其探究能力和創新意識得到了較好的培養，同時培養學生分析問題及解決問題的能力。

參考文獻

[1]阿霍.計算機算法設計與分析：英文版，[M].北京：機械工業出版社，2006.

[2]王曉東.計算機算法設計與分析[M].北京：電子工業出版社，2010，5.

[3]王曉云，陳業綱.計算機算法設計、分析與實現[M].北京：科學出版社，2012.