運籌學教學中的動態規劃求解最短路徑問題的一個注記1

陳芳芳，姜忠義，吳春青

?

運籌學教學中的動態規劃求解最短路徑問題的一個注記1

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

（常州大學 數理學院，江蘇 常州 213164）

動態規劃是運籌學課程教學中的重要內容．在教學過程中，發現在用動態規劃方法求解最短路徑問題時，如果舉例不恰當，很容易對學生造成誤導．對出現誤導的情形進行了分析，找出了發生的原因．基于問題的分析，找到了解決的方法．

動態規劃；最短路徑；Dijkstra算法

動態規劃是運籌學課程中的重要內容，是求解優化問題的一類非常重要的方法[1-4]，它的基本思路是為了尋找系統最優決策，可將系統運行過程劃分為若干相繼的階段．這種決策過程就稱為多段（多步）決策過程．多段決策過程的每一階段的輸出狀態就是下一階段的輸入狀態．多段決策過程的最優化問題必須從系統整體出發，要求各階段選定的決策序列所構成的策略最終能使目標函數達到最優．

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

1　問題分析

在課程教學中，當給出動態規劃求解最短路徑問題的引例時，如果闡述不嚴密，很容易對學生產生誤導，使之認為，只要能將網絡分為不同的階段，就可以用教材中提供的動態規劃求解最短路徑的方法求解．而實際情況并非如此．

2　問題解決

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

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

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

本文對動態規劃求最短路徑的算法進行了分析，在教學過程中，發現在用動態規劃方法求解最短路徑問題時，如果舉例不恰當，很容易對學生造成誤導．對出現誤導的情形進行了分析，找出了發生的原因．基于問題的分析，找到了解決的方法．一是嚴格限定求解目標為權非負的有向圖；二是對于權非負的無向圖，使用Dijkstra算法求解，該算法在本質上也是一種動態規劃的算法．

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

[2] 胡運權．運籌學教程[M]．4版．北京：清華大學出版社，2012：186-192

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

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

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

[6] 趙可培．運籌學[M]．3版．上海：上海財經大學出版社，2013：131-136

[7] 孫小玲，李端．整數規劃[M]．北京：科學出版社，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

常州大學信息數理學院教研課題（2015XSJY08）

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