《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語言描述）教案 李春葆 第6-9章 分支限界法-NP完全問題

教案教案PAGE5算法設(shè)計(jì)與分析基礎(chǔ)(Java)PAGE8算法設(shè)計(jì)與分析課程教案總課堂學(xué)時(shí)：44目前各個(gè)高校都存在算法設(shè)計(jì)與分析課程學(xué)時(shí)少、內(nèi)容多的情況，老師可以針對(duì)實(shí)際情況調(diào)整知識(shí)點(diǎn)，建議如下。（1）學(xué)時(shí)少于36：教學(xué)中主要講授五大算法策略，包括第1章，第4～8章，重點(diǎn)為各種經(jīng)典算法的設(shè)計(jì)思路，少講算法實(shí)現(xiàn)細(xì)節(jié)。（2）學(xué)時(shí)為36～52：教學(xué)中可以選擇部分經(jīng)典算法進(jìn)行講授，相關(guān)實(shí)戰(zhàn)題等可以引導(dǎo)學(xué)生自學(xué)，但要注意知識(shí)點(diǎn)的完整性，例如重點(diǎn)講授采用各種算法策略求解0/1背包問題，讓學(xué)生體會(huì)各種算法策略的要點(diǎn)。（3）學(xué)時(shí)多于52：教學(xué)中講授盡可能多的知識(shí)點(diǎn)，但要突出重點(diǎn)，同一個(gè)知識(shí)點(diǎn)重點(diǎn)講授兩個(gè)左右的經(jīng)典算法，可以適當(dāng)講授一些實(shí)戰(zhàn)題（特別是LeetCode題目），激發(fā)學(xué)生在線編程的興趣。建議：引導(dǎo)學(xué)生（或者學(xué)生小組）做一些專題研究，特別是利用LeetCode中相關(guān)題目做驗(yàn)證工作，例如：（1）求無序序列中第k小元素的算法設(shè)計(jì)。（2）二分查找算法及其應(yīng)用。（3）歸并排序算法及其應(yīng)用。（4）優(yōu)先隊(duì)列及其在算法設(shè)計(jì)中的應(yīng)用。（5）采用各種算法策略求0/1背包問題。（6）采用各種算法策略求貨郎擔(dān)問題。（7）采用各種算法策略求任務(wù)分配問題。（8）求冪集問題的各種算法設(shè)計(jì)。（9）求全排列問題的各種算法設(shè)計(jì)。（10）為什么采用貪心法求0/1背包問題是錯(cuò)誤的。（11）基于子集樹框架的問題求解。（12）基于排列樹框架的問題求解。（13）廣度優(yōu)先算法及其應(yīng)用。（14）利用剪支提高算法性能。（15）求最短路徑問題的研究（LeetCode網(wǎng)站有大量的類似應(yīng)用題目）。（16）基于0/1背包問題的問題求解（LeetCode網(wǎng)站有大量的類似應(yīng)用題目）。（17）基于完全背包問題的問題求解（如零錢兌換LeetCode332等）。第6章分支限界法（共6學(xué)時(shí)）課次：12（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第6章分支限界法。（2）教學(xué)內(nèi)容：分支限界法概述，限界函數(shù)設(shè)計(jì)，廣度優(yōu)先搜索。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：基本廣度優(yōu)先搜索，分層次的廣度優(yōu)先搜索和多起點(diǎn)廣度優(yōu)先搜索。（5）教學(xué)難點(diǎn)：如何利用廣度優(yōu)先搜索求解最優(yōu)解問題。（6）教學(xué)過程：通過3個(gè)實(shí)戰(zhàn)題（到家的最少跳躍次數(shù)-LeetCode1654★★，滑動(dòng)謎題-LeetCode773★★★，腐爛的橘子-LeetCode994★★）講授廣度優(yōu)先搜索的應(yīng)用。（7）作業(yè)：無課次：13（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第6章分支限界法。（2）教學(xué)內(nèi)容：隊(duì)列式分支限界法。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：隊(duì)列式分支限界法概述，圖的單源最短路徑和0/1背包問題。（5）教學(xué)難點(diǎn)：隊(duì)列式分支限界法中的限界函數(shù)設(shè)計(jì)。（6）教學(xué)過程：通過圖的單源最短路徑和0/1背包問題講授隊(duì)列式分支限界法的應(yīng)用方法。（7）作業(yè)：無課次：14（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第6章分支限界法。（2）教學(xué)內(nèi)容：優(yōu)先隊(duì)列式分支限界法。（3）教學(xué)方式：課堂講授+自學(xué)。（4）教學(xué)重點(diǎn)：優(yōu)先隊(duì)列式分支限界法概述，圖的單源最短路徑，0/1背包問題，任務(wù)分配問題和貨郎擔(dān)問題。（5）教學(xué)難點(diǎn)：優(yōu)先隊(duì)列式分支限界法與隊(duì)列式分支限界法的不同點(diǎn)。（6）教學(xué)過程：通過圖的單源最短路徑和0/1背包問題講授優(yōu)先隊(duì)列式分支限界法的應(yīng)用方法。由于時(shí)間限制，可以引導(dǎo)學(xué)生自學(xué)任務(wù)分配問題和貨郎擔(dān)問題。（7）作業(yè)：本章若干問答題和算法設(shè)計(jì)題。（8）實(shí)驗(yàn)：根據(jù)學(xué)生層次選擇一些在線編程題目。第7章貪心法（共6學(xué)時(shí)）課次：15（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第7章貪心法。（2）教學(xué)內(nèi)容：貪心法原理和要點(diǎn)，貪心法框架，求解組合問題。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：活動(dòng)安排問題Ⅰ和背包問題。（5）教學(xué)難點(diǎn)：貪心法的正確性證明。（6）教學(xué)過程：通過活動(dòng)安排問題Ⅰ和背包問題講授貪心法應(yīng)用方法。（7）作業(yè)：無。課次：16（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第7章貪心法。（2）教學(xué)內(nèi)容：求解圖問題。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：Prim算法、Kruskal算法和Dijkstra算法。（5）教學(xué)難點(diǎn)：3個(gè)算法中如何體現(xiàn)貪心法的特點(diǎn)。（6）教學(xué)過程：通過3個(gè)圖算法講授貪心法應(yīng)用方法。（7）作業(yè)：無。課次：17（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第7章貪心法。（2）教學(xué)內(nèi)容：求解調(diào)度問題和哈夫曼編碼。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：不帶懲罰的調(diào)度問題和帶懲罰的調(diào)度問題。（5）教學(xué)難點(diǎn)：帶懲罰的調(diào)度問題。（6）教學(xué)過程：通過調(diào)度問題求解講授貪心法應(yīng)用方法。由于時(shí)間限制，可以簡要介紹哈夫曼編碼，引導(dǎo)學(xué)生自學(xué)。（7）作業(yè)：本章若干問答題和算法設(shè)計(jì)題。（8）實(shí)驗(yàn)：根據(jù)學(xué)生層次選擇一些在線編程題目。第8章動(dòng)態(tài)規(guī)劃（共8學(xué)時(shí)）課次：18（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第8章動(dòng)態(tài)規(guī)劃。（2）教學(xué)內(nèi)容：動(dòng)態(tài)規(guī)劃原理和要點(diǎn)，一維動(dòng)態(tài)規(guī)劃。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：最大連續(xù)子序列和，最長遞增子序列。（5）教學(xué)難點(diǎn)：動(dòng)態(tài)規(guī)劃求解問題的性質(zhì)和步驟，如何設(shè)計(jì)動(dòng)態(tài)規(guī)劃數(shù)組。（6）教學(xué)過程：通過最大連續(xù)子序列和以及最長遞增子序列講授動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)方法。（7）作業(yè)：無。課次：19（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第8章動(dòng)態(tài)規(guī)劃。（2）教學(xué)內(nèi)容：二維動(dòng)態(tài)規(guī)劃，三維動(dòng)態(tài)規(guī)劃。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：三角形最小路徑和，F(xiàn)loyd算法。（5）教學(xué)難點(diǎn)：動(dòng)態(tài)規(guī)劃算法中的空間優(yōu)化。（6）教學(xué)過程：通過三角形最小路徑和講授如何優(yōu)化動(dòng)態(tài)規(guī)劃數(shù)組空間。（7）作業(yè)：無。課次：20（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第8章動(dòng)態(tài)規(guī)劃。（2）教學(xué)內(nèi)容：字符串動(dòng)態(tài)規(guī)劃，背包動(dòng)態(tài)規(guī)劃。（3）教學(xué)方式：課堂講授+自學(xué)。（4）教學(xué)重點(diǎn)：最長公共子序列，編輯距離，0/1背包問題，完全背包問題。（5）教學(xué)難點(diǎn)：動(dòng)態(tài)規(guī)劃算法中的空間優(yōu)化和動(dòng)態(tài)規(guī)劃數(shù)組的計(jì)算順序。（6）教學(xué)過程：從0/1背包問題到完全背包問題講授動(dòng)態(tài)規(guī)劃數(shù)組的計(jì)算順序。由于時(shí)間限制，字符串動(dòng)態(tài)規(guī)劃實(shí)際上是二維動(dòng)態(tài)規(guī)劃的應(yīng)用，這部分可以少講。（7）作業(yè)：無。課次：21（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第8章動(dòng)態(tài)規(guī)劃。（2）教學(xué)內(nèi)容：樹形動(dòng)態(tài)規(guī)劃，區(qū)間動(dòng)態(tài)規(guī)劃。（3）教學(xué)方式：課堂講授+自學(xué)。（4）教學(xué)重點(diǎn)：找礦（LeetCode337）和最長回文子串（LeetCode5）。（5）教學(xué)難點(diǎn)：樹形和區(qū)間動(dòng)態(tài)規(guī)劃的基本原理。（6）教學(xué)過程：通過LeetCode實(shí)例講授樹形和區(qū)間動(dòng)態(tài)規(guī)劃的基本原理。由于時(shí)間限制，其他引導(dǎo)學(xué)生自學(xué)。（7）作業(yè)：本章若干問答題和算法設(shè)計(jì)題。（8）實(shí)驗(yàn)：根據(jù)學(xué)生層次選擇一些在線編程題目。第9章NP完全問題（共2學(xué)時(shí)）課次：2