运筹学教学中的动态规划求解最短路径问题的一个注记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