陳芳芳，姜忠義，吳春青

?

運籌學(xué)教學(xué)中的動態(tài)規(guī)劃求解最短路徑問題的一個注記1

陳芳芳，姜忠義1，吳春青

（常州大學(xué) 數(shù)理學(xué)院，江蘇 常州 213164）

動態(tài)規(guī)劃是運籌學(xué)課程教學(xué)中的重要內(nèi)容．在教學(xué)過程中，發(fā)現(xiàn)在用動態(tài)規(guī)劃方法求解最短路徑問題時，如果舉例不恰當(dāng)，很容易對學(xué)生造成誤導(dǎo)．對出現(xiàn)誤導(dǎo)的情形進行了分析，找出了發(fā)生的原因．基于問題的分析，找到了解決的方法．

動態(tài)規(guī)劃；最短路徑；Dijkstra算法

動態(tài)規(guī)劃是運籌學(xué)課程中的重要內(nèi)容，是求解優(yōu)化問題的一類非常重要的方法[1-4]，它的基本思路是為了尋找系統(tǒng)最優(yōu)決策，可將系統(tǒng)運行過程劃分為若干相繼的階段．這種決策過程就稱為多段（多步）決策過程．多段決策過程的每一階段的輸出狀態(tài)就是下一階段的輸入狀態(tài)．多段決策過程的最優(yōu)化問題必須從系統(tǒng)整體出發(fā)，要求各階段選定的決策序列所構(gòu)成的策略最終能使目標(biāo)函數(shù)達(dá)到最優(yōu)．

最短路徑問題是動態(tài)規(guī)劃求解的一類重要的問題，也是絕大部分運籌學(xué)教材中引入動態(tài)規(guī)劃的基本思想時所舉的一類重要的實例[5-6]．

1　問題分析

在課程教學(xué)中，當(dāng)給出動態(tài)規(guī)劃求解最短路徑問題的引例時，如果闡述不嚴(yán)密，很容易對學(xué)生產(chǎn)生誤導(dǎo)，使之認(rèn)為，只要能將網(wǎng)絡(luò)分為不同的階段，就可以用教材中提供的動態(tài)規(guī)劃求解最短路徑的方法求解．而實際情況并非如此．

2　問題解決

出現(xiàn)這樣現(xiàn)象的主要原因在于動態(tài)規(guī)劃求最短路徑的這個方法上．在由這個方法求解時，由于無后效性的原因，只是順次地考慮各個階段的路徑長度，如與級各結(jié)點中各點的最短路的長度，只考慮了由到級結(jié)點再到級結(jié)點之間的各條路徑，而沒有考慮由到級結(jié)點到級結(jié)點到級結(jié)點再到級結(jié)點這樣回溯的路徑，從而忽略了更短的路徑長度．

這個問題的出現(xiàn)主要有2個原因，一是沒有嚴(yán)格地定義所謂的最短路徑這個概念，如果加上某些限制條件，嚴(yán)格地定義，尋找的就是從到到再到這樣的一條最短路徑（即所給的求解圖為有向圖），則該算法顯然就沒有問題．二是從尋找最短路徑的角度，由動態(tài)規(guī)劃的基本方程出發(fā)尋找最短路徑，但解法并不嚴(yán)密．求最短路徑的動態(tài)規(guī)劃的基本方程為

基于以上分析，可以看出在課程教學(xué)中，為避免對學(xué)生造成誤導(dǎo)，需要在實例中注明該方法僅適用于權(quán)非負(fù)的有向的網(wǎng)絡(luò)的最短路徑問題，并不適用于一般的最短路徑問題，如同教材[7-8]所列實例一樣，該問題將不會存在．而求解權(quán)非負(fù)的無向圖最短路徑問題，Dijkstra算法本質(zhì)上也是一種動態(tài)規(guī)劃的算法，可以在課堂教學(xué)上作為引例的補充，對加深學(xué)生理解動態(tài)規(guī)劃基本思想也有很好的效果．

本文對動態(tài)規(guī)劃求最短路徑的算法進行了分析，在教學(xué)過程中，發(fā)現(xiàn)在用動態(tài)規(guī)劃方法求解最短路徑問題時，如果舉例不恰當(dāng)，很容易對學(xué)生造成誤導(dǎo)．對出現(xiàn)誤導(dǎo)的情形進行了分析，找出了發(fā)生的原因．基于問題的分析，找到了解決的方法．一是嚴(yán)格限定求解目標(biāo)為權(quán)非負(fù)的有向圖；二是對于權(quán)非負(fù)的無向圖，使用Dijkstra算法求解，該算法在本質(zhì)上也是一種動態(tài)規(guī)劃的算法．

[1] 于春田，李法朝．運籌學(xué)[M]．北京：科學(xué)出版社，2006：177-181

[2] 胡運權(quán)．運籌學(xué)教程[M]．4版．北京：清華大學(xué)出版社，2012：186-192

[3] 刁在筠，鄭漢鼎，劉家壯，等．運籌學(xué)[M]．2版．北京：高等教育出版社，2001：152-158

[4] Bernhard Korte．Combinatorial Optimization：Theory and Algorithms[M]．NewYork：The Springer Press，2000：448-451

[5] 張瑩．運籌學(xué)基礎(chǔ)[M]．2版．北京：清華大學(xué)出版社，2014：204-209

[6] 趙可培．運籌學(xué)[M]．3版．上海：上海財經(jīng)大學(xué)出版社，2013：131-136

[7] 孫小玲，李端．整數(shù)規(guī)劃[M]．北京：科學(xué)出版社，2010：55-58

[8] Hamdy A T．Operations Research An Introduction[M]．London：Pearson/Education，2010：399-403

A note on the dynamics program for the shortest path problem in the operational research teaching

CHEN Fang-fang，JIANG Zhong-yi，WU Chun-qing

（School of Mathematics and Physics，Changzhou University，Changzhou 213164，China）

Dynamics program is very important in the lessons of the operational research．During the teaching process，the students may be misled by some improper example．The things which may mislead students are analyzed and the reasons are found．Then the ways to resolve the problem are found．

dynamics programming；shortest path；Dijkstra algorithm

1007-9831（2016）09-0056-03

O221∶G642.0

A

10.3969/j.issn.1007-9831.2016.09.016

2016-05-10

常州大學(xué)信息數(shù)理學(xué)院教研課題（2015XSJY08）

陳芳芳（1980-），女，江蘇鹽城人，講師，碩士，從事運籌學(xué)研究．E-mail：sunnychen@cczu.edu.cn