ACM—ICPC競賽趣味學(xué)習(xí)系統(tǒng)設(shè)計(jì)

[摘 要]目前，很多教材或者網(wǎng)站對(duì)動(dòng)態(tài)規(guī)劃思想的介紹都很枯燥乏味且理解起來頗為費(fèi)勁，人們?cè)絹碓叫枰环N高效有趣的方法來學(xué)習(xí)該算法。本文致力于提高動(dòng)態(tài)規(guī)劃教學(xué)趣味性的研究，通過設(shè)計(jì)簡單明了的例子，以游戲的形式介紹動(dòng)態(tài)規(guī)劃思想。在演示過程中，使用了狀態(tài)壓縮，位運(yùn)算，滾動(dòng)數(shù)組等算法優(yōu)化計(jì)算過程。通過加入ACM元素，最終實(shí)現(xiàn)了一個(gè)ACM-ICPC競賽趣味學(xué)習(xí)系統(tǒng)。

[關(guān)鍵詞]ACM-ICPC；動(dòng)態(tài)規(guī)劃；狀態(tài)壓縮；趣味學(xué)習(xí)

中圖分類號(hào)：TG333.2 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-914X（2016）19-0215-01

0 前言

ACM國際大學(xué)生程序設(shè)計(jì)競賽（ACM-ICPC：ACM International Collegiate Programming Contest）[1]是由國際計(jì)算機(jī)界權(quán)威組織、美國計(jì)算機(jī)協(xié)會(huì)主辦的世界公認(rèn)的規(guī)模最大、水平最高的國際大學(xué)生程序設(shè)計(jì)競賽，旨在使大學(xué)生運(yùn)用計(jì)算機(jī)來鍛煉自己分析問題和解決問題的能力，可以充分展示大學(xué)生創(chuàng)新能力、團(tuán)隊(duì)精神和在壓力下編寫程序、分析和解決問題能力，經(jīng)過近30多年的發(fā)展，已經(jīng)成為最具影響力的大學(xué)生計(jì)算機(jī)競賽。動(dòng)態(tài)規(guī)劃作為其中一個(gè)很重要的考點(diǎn)，是參賽學(xué)生必須要掌握的知識(shí)。本文致力于提高動(dòng)態(tài)規(guī)劃算法教學(xué)趣味性的研究，基于狀態(tài)壓縮的方法，利用簡單明了的例子，介紹了動(dòng)態(tài)規(guī)劃思想，達(dá)到了比較理想的效果。在解題過程中中，運(yùn)用了位運(yùn)算，滾動(dòng)數(shù)組等不同方法，優(yōu)化了計(jì)算過程。

1 動(dòng)態(tài)規(guī)劃算法簡介

動(dòng)態(tài)規(guī)劃（dynamic programming）[2]是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程（decision process）最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程（multistep decision process）的優(yōu)化問題[3]時(shí)，提出了著名的最優(yōu)化原理（principle of optimality），把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對(duì)解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。動(dòng)態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。

動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。

求解基本步驟：

（1） 分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。

（2）遞歸的定義最優(yōu)解。

（3）以自底向上或自頂向下的記憶化方式（備忘錄法）計(jì)算出最優(yōu)值

（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造問題的最優(yōu)解

使用動(dòng)態(tài)規(guī)劃求解問題，最重要的就是確定動(dòng)態(tài)規(guī)劃三要素：

（1）問題的階段

（2）每個(gè)階段的狀態(tài)

（3）從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系。

遞推關(guān)系必須是從次小的問題開始到較大的問題之間的轉(zhuǎn)化，從這個(gè)角度來說，動(dòng)態(tài)規(guī)劃往往可以用遞歸程序來實(shí)現(xiàn)，因?yàn)檫f推可以充分利用前面保存的子問題的解來減少重復(fù)計(jì)算，所以對(duì)于大規(guī)模問題來說，有遞歸不可比擬的優(yōu)勢(shì)，這也是動(dòng)態(tài)規(guī)劃算法的核心之處。

確定了動(dòng)態(tài)規(guī)劃的這三要素，整個(gè)求解過程就可以用一個(gè)最優(yōu)決策表來描述，最優(yōu)決策表是一個(gè)二維表，其中行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對(duì)應(yīng)此問題的在某個(gè)階段某個(gè)狀態(tài)下的最優(yōu)值（如最短路徑，最長公共子序列，最大價(jià)值等），填表的過程就是根據(jù)遞推關(guān)系，從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個(gè)表格的數(shù)據(jù)通過簡單的取舍或者運(yùn)算求得問題的最優(yōu)解。

f（n，m）=max{f（n-1，m）， f（n-1，m-w[n]）+P（n，m）}

2 系統(tǒng)設(shè)計(jì)

系統(tǒng)首先對(duì)ACM-ICPC進(jìn)行介紹，讓用戶對(duì)比賽有一個(gè)認(rèn)識(shí)。動(dòng)態(tài)規(guī)劃學(xué)習(xí)中，首先通過設(shè)計(jì)一個(gè)簡單的例子，以小游戲的形式，讓用戶在操作過程體會(huì)動(dòng)態(tài)規(guī)劃的思想，接著引出概念，介紹算法。通過設(shè)計(jì)一道POJ上的題目——炮兵布陣，演示動(dòng)態(tài)規(guī)劃算法的應(yīng)用，加深用戶的理解。最后提供HDU以及PKU的題庫。

3 結(jié)語

本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)完整的動(dòng)態(tài)規(guī)劃算法學(xué)習(xí)系統(tǒng)，并且應(yīng)用文字與視頻相結(jié)合的方式詳細(xì)介紹ACM競賽的背景與研究意義，通過設(shè)計(jì)兩個(gè)例子讓用戶在游戲的氛圍中學(xué)習(xí)算法的思想，達(dá)到了寓教于樂的效果。在使用戶能夠快速高效理解算法思想的同時(shí)，也增加了測(cè)評(píng)環(huán)節(jié)，幫助用戶鞏固所學(xué)內(nèi)容，從而更加牢固的 掌握所學(xué)算法。

參考文獻(xiàn)：

[1] ACMICPC官網(wǎng). http：//icpc.baylor.edu/.

[2] Richard E. Bellman. Dynamic Programming[M]. Princeton University Press； Revised editi-on， 2010.7.1.

[3] Talha Amin and Igor Chikalov and Mikhail Moshkov and Beata Zielosko. Dyn-amic progr-amming approach to optimization of approximate decision rules[J]. In-formation Sciences， 2013，221.

作者簡介：

劉志丹 （1992—） ，女，河北省邢臺(tái)市人，學(xué)歷碩士，專業(yè)或職業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)。