基于案例的比較法在《算法設計與分析》教學中的應用研究

耿霞 劉建華

1.山東農業大學信息科學與工程學院 山東 泰安 271018；2.山東農業大學經濟管理學院 山東 泰安 271018

1 《算法設計與分析》課程的性質與特點

算法在計算機科學中具有不可代替的重要地位[1-2]。算法對計算機科學的所有分支都非常重要，比如，大數據、機器學習需要用到分類決策樹算法、遺傳算法、爬山算法、模擬退火算法等；通信網絡中的路由協議需要使用經典的最短路徑算法；公鑰加密依賴于高效的數論算法；計算機圖像學需要用到幾何算法等。

《算法設計與分析》是計算機類專業、人工智能專業等的一門核心專業基礎課，本課程介紹非數值算法設計的策略與技術，課程內容主要包括：遞推算法、遞歸與分治策略、動態規劃算法、貪心算法、回溯算法、分支限界算法等[3]。通過本課程的學習，使學生能夠掌握經典算法的基本思想并能靈活利用這些算法思想去解決實際問題，并掌握算法設計與分析的基本技巧，能夠從時間復雜度和空間復雜度兩個方面去分析算法的優劣[4]。本課程既具有較強的理論性又具有較強的實踐性[5]，并且在學生就業和考研過程中，本課程知識點是經常被考察的內容。但本課程中涉及的一些經典算法由于比較抽象，因此學生在學習的過程中比較難理解，并且很難使學生達到靈活應用算法解決問題的教學目標。

2 案例教學法和比較教學法的內涵

案例教學法是在教學過程中通過引入一些學生生活或學習過程中的典型案例，借助于這些生動的案例幫助學生更好地理解抽象、枯燥的知識點的一種教學方法。案例教學法已被廣泛應用于各種課程的教學過程中，是一種非常有效的教學方法。通過案例教學方法，可以把難理解的知識點融入有趣的案例中，從而能夠激發學生的學習興趣，更容易地理解和掌握有關知識點。教育學家葉圣陶說過，“教材無非是個例子”。案例教學法可以達到事半功倍的教學效果。

3 基于案例的比較教學法在課程中的應用

3.1 案例設計原則

好的案例是案例教學法取得好的教學效果的基礎，因此教師在備課的過程中，一定要認真謹慎選擇和設計教學案例。設計的教學案例應該具有貼切性、代表性、生動性。

貼切性是指設計的案例一是應該符合教學目標和要求，不能“跑題”，要與要講授的知識點密切相關，案例應該能啟發學生積極思考，或者能幫助學生更好地理解有關知識。二是應該難度適中，如果案例太簡單的話，則引不起學生的興趣，也可能會讓學生忽視有關知識點的學習，不能讓學生掌握好課程的重點或難點；如果案例太難的話，學生找不到解決問題的思考點或者很難理解其中包含的內容，則不利于幫助學生掌握課程內容。

代表性是指設計的案例要能起到范例作用，讓學生能夠舉一反三，利用解決此問題的思路可以類推到其他相似的問題中，從而有利于培養學生分析問題、解決問題的能力。

生動性是指設計的案例一是應該來源于生活，與學生的日常學習、生活密切相關，這樣的案例容易引起學生的興趣，愛因斯坦說過：“興趣是最好的老師”，在興趣的驅使下，學生才能更加積極思考和學習。二是適合學生展開討論和交流，具有一定的“話題性”。通過案例，便于教師引導學生積極思考，展開討論，通過討論找到問題的解決方法，自然而然地讓學生理解有關的算法知識。

設計的案例可以分成引導型案例和學習型案例。所謂引導型案例，是指通過該案例，可以引起學生對某個知識點的興趣，領著學生“入門”；所謂學習型案例，是指通過該案例，學生可以比較輕松地學習掌握某個知識點，是一種“潤物細無聲”傳授知識的案例。

比如案例：用“貪心算法”找到偷車賊。

來自圣母大學計算機系副教授史戈宇在和家人外出的過程中遭遇了劫匪劫車，被搶之后，史教授原本通過撥打911借助于警察幫忙，但無奈警察不作為，史教授只好自己親自解決。他最終借助于GPS定位功能和“貪心算法”思想成功找到了丟失的車輛。

本案例就屬于一個引導型案例，設計此案例的目的是讓學生對貪心算法有一個初步印象，體會所學知識和現實生活的密切關系，從而引發學生對學習貪心算法的興趣，讓學生非常期待后續有關知識的學習，調動了學生學習的積極性。

3.2 基于案例的比較法教學在《算法設計與分析》課程中的應用

通過幾個具體例子來說明基于案例的比較教學法在《算法設計與分析》教學過程中的應用。

案例1：給定一個載重量為M的背包，考慮n個物品，其中第i個物品的重量wi，價值vi（1≤i≤n），要求把物品裝入背包，且使背包內的物品價值最大。有兩類背包問題（根據物品是否可以分割），如果物品不可以分割，稱為0-1背包問題；如果物品可以分割，則稱為背包問題。假設背包容量為50，有3件物品，每件物品的重量和價值如表1所示。

表1 每件物品重量和價值

分析：如果把此問題當作0-1背包問題，用動態規劃算法可以解決，得到裝載方案為：物品2和物品3裝入背包，此時可以得到最大價值為220。此問題也可以使用貪心算法解決，首先按照單位價值從高到低排序，依次裝入物品1和物品2，此時背包剩余容量只有20，無法再繼續裝入物品3，因此，此時背包中物品的價值為160。

如果把此問題當作背包問題，只能使用貪心算法解決。按性價比從高到低的順序選取物品，獲得最優值240。由于物品可以分割，剩下的空間裝入物品3的一部分，而獲得了更好的性能。

通過此案例，可以對比動態規劃算法和貪心算法的算法思想，不同的算法得到的解決方案是不同的。根據得到的結果，學生很容易得到結論：0-1背包問題適合采用動態規劃算法解決，背包問題適合采用貪心算法解決。基于同一個案例，學生可以比較動態規劃算法和貪心算法的差異，從而能夠更好地掌握兩個算法的核心思想。

案例2：一銷售商從n個城市中的某一城市出發，不重復地走完其余n-1個城市并回到原出發點，在所有可能的路徑中求出路徑長度最短的一條。本題假定該旅行商從第1個城市出發。

假設有4個城市，各個城市之間的長度如圖1所示。

圖1 城市之間長度示意圖

分析：旅行商問題可以采用回溯法解決，也可以采用分支限界算法解決。

如果采用回溯法，旅行商問題的解空間是一棵排列樹。開始時，x＝｛1，2，…，n｝，相應的排列樹由x的全排列構成。回溯法實現的偽代碼如下：

旅行商問題也可以采用分支限界算法解決，解空間同回溯法一樣也是一棵排列樹。回溯法是以深度優先方式搜索解空間樹，分支限界算法是以廣度優先的方式搜索問題的解空間樹。在分支限界算法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所需的解或活結點表為空時為止。使用分支限界算法解決旅行商問題的偽代碼本文不再詳述。

4 結束語

案例法和比較法都是被實踐證明了的有效教學方法。《算法設計與分析》本身既有很強的理論性又有很強的應用性，涉及的經典算法理解起來比較困難，學生在學習的過程中存在畏難情緒。為了增強該課程的趣味性，激發學生的學習興趣，更好地理解該課程的內容，本文研究了基于案例的比較法在教學過程中的應用。設計具有多種求解算法的教學案例，通過對同一案例不同實現算法的比較，使學生深刻理解這些算法的內涵和應用場景，既能促成學生更好地掌握算法設計與分析的理論和方法，又能培養學生的發散思維，提高學生分析問題、解決問題的能力。