《算法設計與分析》課程典型實例教學的應用

張曉霞，張寶鑫，陳倩

（遼寧科技大學軟件學院，鞍山 114051）

1 問題的提出

《算法設計與分析》是計算機學科一門重要的專業基礎課[1]，是理論與實踐相結合較強的一門課程。其主要教學目標是通過對常用的算法理論進行系統而深入的學習，使學生掌握常規算法設計的基本原理，培養學生對一些算法的復雜性能進行正確分析，同時針對具體實際問題設計出高效的算法。計算機算法設計的是否高效直接決定于軟件系統運行的效率和穩定性，學生掌握好《算法設計與分析》這門課程，為將來設計及編寫出高效算法程序打下堅實的理論基礎。所以，探討與研究提高《算法設計與分析》課程教學效率具有理論意義和現實意義。

《算法設計與分析》內容的有些理論知識偏重與數學，學生感覺這是一門比較抽象與復雜比較難的課程。同時課程培養目標也要求學生既要掌握算法設計的基本理論，同時又要有實際調試程序的實際動手能力。在教科書中[2]，主要內容包括動態規劃算法、貪心算法、回溯法和分支限界算法。本文針對《算法設計與分析》課程實際情況，對實例教學在回溯算法做了深入研究與探討。采用典型的實例教學，把復雜而抽象的算法變為簡單化、形象化，使學生能快速掌握回溯算法的基本原理及主要步驟，因此，選擇合適的典型教學實例非常關鍵，在《算法設計與分析》教學中合理充分利用好典型實例，把復雜問題及算法簡單化、具體化，活躍課堂學習氣氛，從而激發學生對算法學習興趣，同時提高理論課堂教學效果。

2 0-1背包問題實例

0-1背包問題是典型組合優化問題[3]，在很多領域，有著比較廣泛的應用工程背景[4]。0-1背包問題描述為已知n個物品和一個帶容量限制的背包。每個物品有重量及相應的利潤，物品i的重量是wi，其利潤為vi，背包的容量限制為C。求解目標為如何選擇裝入背包的物品，且需要滿足容量約束條件，使得裝入該背包中物品獲得總利潤最大。

約束（2）為背包的容量約束，也就是指裝入背包物品不能超過背包的容量限制。約束（3）表示xi為0-1決策變量，當第i個物品放入背包時，xi=1，否則xi=0。0-1背包問題的解實際就是從物品集合中選出一個合適子集，并且滿足背包的容量約束條件，使裝入背包的物品獲得利函數值最大。

本文采用實例為簡單的0-1背包問題，這個問題貼近同學的日常生活，便于學生接受和理解。貪心算法就解背包問題上界函數是通過把0-1背包問題的xi?{0,1}整數松弛為小數 xi?[0,1]。例如：物品數目 n=3，背包容量C=35，各個物品的重量為W=（11,21,23），各個物品的價值為V=（21,31,33），如果是0-1背包問題，最優解為（1,0,1），最優值為54。如是背包問題，最優解（1,1,0.13），最優值為56。也就是說貪心算法求解背包問題為0-1背包問題提供一個上界函數。

3 回溯算法

采用回溯算法求解0-1背包問題，如果一個結點的左子樹滿足約束條件，就繼續搜索。對于右子樹，首先采用貪心算法生成一個上界函數，上界函數表明繼續搜索這個結點的子樹能獲得最優值，也就是說只有滿足上界函數的值大于當前最優解條件時才能進入下一級子樹繼續開始搜索。在搜索進程中，最優解逐漸得到改善。如果某個結點的上界函數小于當前最優值Bestf，那么搜索該子樹不可能獲得比較好的最優解，即該子樹可以被“剪枝”。圖1給出了0-1背包問題的解空間樹，下面給出用回溯法求解決實例1中0-1背包問題步驟：

步驟1：開始時，1為唯一擴展結點，擴展1結點，先到達2結點。

步驟2：此時1、2為活結點，2成為當前擴展結點。因2結點滿足能力約束，擴展2結點，先到達4結點，因4結點滿足能力約束，擴展4到達8結點，因結點8不滿足能力約束，結點8不可行，結點8剪去。

步驟3：回溯到4，再次擴展4到達9結點，由于9是葉結點，即得到一個可行解x=（1,1,0），當前最好值Bestf=52。

步驟4：回溯到4，再回溯到2結點，因為右子樹結點 5 界函數 bound（5）=54＞Bestf，5 成為當前擴展結點，擴展結點5到10，結點10葉結點，得到一個可行解x=（1,0,1），Bestf=54。

步驟5：回溯到5，結點10剪去?；厮莸?，最后回溯到1，擴展1結點，到達3結點，結點3界函數bound（3）=51，因為 bound（3）＜滿足 Bestf，結點 3 剪去。

圖1 0-1背包問題的解空間樹

4 結語

本文針對回溯法算法特點，采用典型實例教學，有助于學生快速理解和掌握回溯法的基本原理及算法步驟?！端惴ㄔO計與分析》是計算機學科的重要課程，也是一門比較難的課程。作為教師要講好這門課，對教師也提出更高的要求，教師要多學習，擴展知識，根據算法的特點，選好典型的實例，同時在課堂教學過程中，要隨時觀察學生的課堂接受能力，適當動態調整教學內容與進度。經過多年教學實際驗證，采用典型實例教學方法，將復雜抽象算法理論與簡單的典型實例有機結合，這樣使學生由被動學習變為主動學習，培養學生對算法學習的興趣，提高學生獨立分析問題及解決問題的實際動手能力。