《高級算法與數(shù)據(jù)結(jié)構(gòu)》課程思政教學(xué)案例（一等獎）

一、授課內(nèi)容

1.1動態(tài)規(guī)劃算法的基本思想

在現(xiàn)實(shí)生活中，有一類問題被定義為最優(yōu)決策問題，這類問題

可能會有許多可行解，每一個(gè)解都對應(yīng)于一個(gè)值，我們希望找到具有

最優(yōu)值的那個(gè)解，即最優(yōu)解。20世紀(jì)40年代，RichardBellman首

次使用了動態(tài)規(guī)劃這個(gè)術(shù)語，用來描述最優(yōu)決策問題的求解過程。其

核心思想是將最優(yōu)決策問題按照時(shí)間或空間特征分解成若干相互關(guān)

聯(lián)的階段，以便按次序去求每個(gè)階段的解。各階段開始時(shí)具有客觀條

件（稱之為狀態(tài)），當(dāng)各階段的狀態(tài)確定以后，就可以做出不同的決

定，從而確定下一階段的狀態(tài)，這種決定稱為決策?！皠討B(tài)”是指在

一定條件下，根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)，“規(guī)

劃”是指建立狀態(tài)轉(zhuǎn)移方程。最優(yōu)決策問題的難點(diǎn)在于，各個(gè)階段決

策的選取不能任意確定，它既依賴于當(dāng)前面臨的狀態(tài)，又影響著以后

的發(fā)展。

1.2動態(tài)規(guī)劃算法與分治法的區(qū)別和聯(lián)系

動態(tài)規(guī)劃算法與（第二章）分治法類似，都是將待求解問題分

解為若干個(gè)子問題，先求解子問題，再結(jié)合這些子問題的解得到原問

題的解。與分治法不同之處在于：

（1）適合用動態(tài)規(guī)劃求解的問題經(jīng)分解得到的子問題往往不是

相互獨(dú)立的（即重疊子問題），在遞歸模型上采用分治法自頂向下求

解時(shí)，有些子問題被反復(fù)計(jì)算。動態(tài)規(guī)劃算法正是利用重疊子問題的

性質(zhì)，將各階段子問題的最優(yōu)值保存在一個(gè)表格中，在需要時(shí)以常數(shù)

時(shí)間查看結(jié)果，這樣可以避免大量的重復(fù)計(jì)算。對于一些在遞歸模型

上具有指數(shù)下界的算法來說，當(dāng)不同子問題的個(gè)數(shù)隨問題的大小呈多

項(xiàng)式增長時(shí)，用動態(tài)規(guī)劃的表格式方法來存儲重疊子問題的解，可以

將指數(shù)時(shí)間減少為多項(xiàng)式時(shí)間，從而有效降低了時(shí)間復(fù)雜度。

（2）每個(gè)階段的子問題可能會有許多可行解，當(dāng)問題的最優(yōu)解包

含了其子問題的最優(yōu)解時(shí)（即最優(yōu)子結(jié)構(gòu)），表格里只存儲子問題的

最優(yōu)解就可以了。利用最優(yōu)子結(jié)構(gòu)性質(zhì)，動態(tài)規(guī)劃可以自底向上的從

子問題的最優(yōu)解逐步構(gòu)造出原問題的最優(yōu)解，從而有效控制了空間復(fù)

雜度。

1.30T背包問題的動態(tài)規(guī)劃算法

0-1背包問題是指，給定n種物品和一個(gè)背包，物品i的重量為

wi,價(jià)值為vi,背包的容量為S,問如何選擇裝入背包中的物品，使

得背包中物品的總價(jià)值最大。利用動態(tài)規(guī)劃算法求解該問題的思想是,

先逐步解決容量為1,2,…的小背包問題，最后解決容量為S的背包

問題。

從動態(tài)規(guī)劃的基本性質(zhì)為切入點(diǎn)，分別證明0T背包問題具有最

優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì)，而后由淺入深地分析初始階段、終

止階段及各階段的問題空間，在此基礎(chǔ)上遞歸定義狀態(tài)變量（即最優(yōu)

值）及其狀態(tài)轉(zhuǎn)移方程。接下來，對于給定的問題實(shí)例，以自底向上

的方式計(jì)算最優(yōu)值，最后根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息、，調(diào)用遞歸模

型通過回溯的方式構(gòu)造最優(yōu)解。

二、實(shí)施過程

（一）思政元素類型：

社會主義核心價(jià)值觀教育，職業(yè)理想和職業(yè)道德教育。

（二）課堂教學(xué)方法：

1.教學(xué)手段：采用板書、PPT、動畫、視頻等多媒體形式。

2.課程思政融入點(diǎn)：知識點(diǎn)中的動態(tài)規(guī)劃基本原理與“知行合

一”哲學(xué)思想、“舍與得”的哲理、適中思想等相契合，從而引申出

思政案例。

三、思政元素內(nèi)容

元素一：動態(tài)規(guī)劃中的“知行合一”理念

（-）元素內(nèi)容

能夠采用動態(tài)規(guī)劃算法來求解的問題需要具備兩個(gè)重要性質(zhì)：

最優(yōu)子結(jié)構(gòu)、重疊子問題。對于給定問題，只有證明其具備了這兩個(gè)

性質(zhì)，才能設(shè)計(jì)相應(yīng)的狀態(tài)轉(zhuǎn)移方程，從而保證動態(tài)規(guī)劃算法的正確

性。這個(gè)過程中所體現(xiàn)的是“知行合一”的哲學(xué)思想，給出問題具備

最優(yōu)子結(jié)構(gòu)和重疊子問題性質(zhì)的定理是“知”，自底向上求解各階段

子問題的最優(yōu)值是“行”。由于對問題性質(zhì)的證明過程涉及數(shù)學(xué)歸納

法、反證法等，對學(xué)生的抽象思維、邏輯思維有一定的要求，因此同

學(xué)們往往會忽略對“知”的關(guān)注，而把動態(tài)規(guī)劃算法僅僅等同于用偽

代碼描述過程，或者直接通過編寫程序來運(yùn)行算法等“行”的范疇,

從而割裂了“知”與“行”之間的關(guān)系。

“知行”是中國傳統(tǒng)哲學(xué)的重要范疇，其始于《尚書》與《左

傳》，《尚書》有“非知之艱，行之惟艱”之說［1］,《左傳》有“非

知之實(shí)難，將在行之”之說［2］。東北大學(xué)校訓(xùn)“自強(qiáng)不息、知行合

一”中的“知行合一”出自于《傳習(xí)錄》［3］,它是明代著名哲學(xué)家

王守仁的弟子們記錄老師的學(xué)術(shù)講話及論學(xué)書信的集子。守仁說：

“知之真切篤行處即是行，行之明覺精察處即是知?！庇终f：“若會

得時(shí)，只說一個(gè)知已自有行在，只說一個(gè)行已自有知在?！倍际钦f明

知行本來合一，無可分割。對于知而不行的時(shí)弊，王守仁有這樣一段

一針見血的話：“今人卻將知行分作兩件去做，以為必先知了，然后

能行，我如今且去講習(xí)討論做知的功夫，待知得真了方去做行的功夫,

故遂終身不行，亦遂終身不知。此不是小病痛，其來已非一日矣。某

今說個(gè)知行合一，正是對病的藥。又不是某鑿空杜撰，知行本體原是

如此?！彼J(rèn)為，“真知即所以為行，不行不足謂之知”，又強(qiáng)調(diào)“圣

學(xué)只是一個(gè)功夫，知行不可分作兩事”。

理解了“知行合一”的哲學(xué)思想，就會將動態(tài)規(guī)劃算法的正確

性證明和算法設(shè)計(jì)思想有機(jī)融合在一起，不可分割。

（二）價(jià)值拓展

我們在生活中經(jīng)常會遇到復(fù)雜的最優(yōu)決策問題，要學(xué)會應(yīng)用“知

行合一”的哲學(xué)思想，分析思考問題的性質(zhì)（即致“知”）和實(shí)際去

解決問題（即格“物”）不可分割，“知是行之始，行