《算法設(shè)計(jì)與分析》課程典型實(shí)例教學(xué)的應(yīng)用

張曉霞，張寶鑫，陳倩

（遼寧科技大學(xué)軟件學(xué)院，鞍山 114051）

1 問(wèn)題的提出

《算法設(shè)計(jì)與分析》是計(jì)算機(jī)學(xué)科一門重要的專業(yè)基礎(chǔ)課[1]，是理論與實(shí)踐相結(jié)合較強(qiáng)的一門課程。其主要教學(xué)目標(biāo)是通過(guò)對(duì)常用的算法理論進(jìn)行系統(tǒng)而深入的學(xué)習(xí)，使學(xué)生掌握常規(guī)算法設(shè)計(jì)的基本原理，培養(yǎng)學(xué)生對(duì)一些算法的復(fù)雜性能進(jìn)行正確分析，同時(shí)針對(duì)具體實(shí)際問(wèn)題設(shè)計(jì)出高效的算法。計(jì)算機(jī)算法設(shè)計(jì)的是否高效直接決定于軟件系統(tǒng)運(yùn)行的效率和穩(wěn)定性，學(xué)生掌握好《算法設(shè)計(jì)與分析》這門課程，為將來(lái)設(shè)計(jì)及編寫出高效算法程序打下堅(jiān)實(shí)的理論基礎(chǔ)。所以，探討與研究提高《算法設(shè)計(jì)與分析》課程教學(xué)效率具有理論意義和現(xiàn)實(shí)意義。

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

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

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

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

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

3 回溯算法

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

步驟1：開(kāi)始時(shí)，1為唯一擴(kuò)展結(jié)點(diǎn)，擴(kuò)展1結(jié)點(diǎn)，先到達(dá)2結(jié)點(diǎn)。

步驟2：此時(shí)1、2為活結(jié)點(diǎn)，2成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。因2結(jié)點(diǎn)滿足能力約束，擴(kuò)展2結(jié)點(diǎn)，先到達(dá)4結(jié)點(diǎn)，因4結(jié)點(diǎn)滿足能力約束，擴(kuò)展4到達(dá)8結(jié)點(diǎn)，因結(jié)點(diǎn)8不滿足能力約束，結(jié)點(diǎn)8不可行，結(jié)點(diǎn)8剪去。

步驟3：回溯到4，再次擴(kuò)展4到達(dá)9結(jié)點(diǎn)，由于9是葉結(jié)點(diǎn)，即得到一個(gè)可行解x=（1,1,0），當(dāng)前最好值Bestf=52。

步驟4：回溯到4，再回溯到2結(jié)點(diǎn)，因?yàn)橛易訕浣Y(jié)點(diǎn) 5 界函數(shù) bound（5）=54＞Bestf，5 成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，擴(kuò)展結(jié)點(diǎn)5到10，結(jié)點(diǎn)10葉結(jié)點(diǎn)，得到一個(gè)可行解x=（1,0,1），Bestf=54。

步驟5：回溯到5，結(jié)點(diǎn)10剪去?；厮莸?，最后回溯到1，擴(kuò)展1結(jié)點(diǎn)，到達(dá)3結(jié)點(diǎn)，結(jié)點(diǎn)3界函數(shù)bound（3）=51，因?yàn)?bound（3）＜滿足 Bestf，結(jié)點(diǎn) 3 剪去。

圖1 0-1背包問(wèn)題的解空間樹

4 結(jié)語(yǔ)

本文針對(duì)回溯法算法特點(diǎn)，采用典型實(shí)例教學(xué)，有助于學(xué)生快速理解和掌握回溯法的基本原理及算法步驟?！端惴ㄔO(shè)計(jì)與分析》是計(jì)算機(jī)學(xué)科的重要課程，也是一門比較難的課程。作為教師要講好這門課，對(duì)教師也提出更高的要求，教師要多學(xué)習(xí)，擴(kuò)展知識(shí)，根據(jù)算法的特點(diǎn)，選好典型的實(shí)例，同時(shí)在課堂教學(xué)過(guò)程中，要隨時(shí)觀察學(xué)生的課堂接受能力，適當(dāng)動(dòng)態(tài)調(diào)整教學(xué)內(nèi)容與進(jìn)度。經(jīng)過(guò)多年教學(xué)實(shí)際驗(yàn)證，采用典型實(shí)例教學(xué)方法，將復(fù)雜抽象算法理論與簡(jiǎn)單的典型實(shí)例有機(jī)結(jié)合，這樣使學(xué)生由被動(dòng)學(xué)習(xí)變?yōu)橹鲃?dòng)學(xué)習(xí)，培養(yǎng)學(xué)生對(duì)算法學(xué)習(xí)的興趣，提高學(xué)生獨(dú)立分析問(wèn)題及解決問(wèn)題的實(shí)際動(dòng)手能力。