利用动态规划算法求解最短路径_梁娟
第14卷第5期 2006年09月
河南机电高等专科学校学报
JournalofHenanMechanicalandElectricalEngineeringCollege
Vol.14l.5
Sept.2006
利用动态规划算法求解最短路径
梁 娟,郭军丽,魏 勇
1
2
1
*
(1.河南机电高等专科学校计算机科学系,2.新乡市消防支队,河南新乡453002)
摘要:动态规划是研究一类最优化问题的算法。文中介绍了如何将最短路径问题通过动态规划来求解。关键词:动态规划;优化;路径;算法
中图分类号:TP311 文献标识码:A 文章编号:1008-2093(2006)05-0030-02
1 概述
最短路径问题是一类比较简单而又很重要的最优化问题[1]。所谓最短路径问题就是指给定起点及终点,并知道由起点到终点的各种可能的路径,问题是要找一条由起点到终点的最短的路,即长度最短的路。需要指出的是,最短路径中的/长度0可以是通常意义上的距离,也可以是运输费用等等。本文介绍如何将一个最优化问题通过动态规划来求解的基本原理。
态规划方法解决。
动态规划是一种思维方法,可以从多方面去考察,不同的方面对动态规划有不同的表述。动态规划可分为正向思维法和逆向思维法。逆向思维法是指从问题目标状态出发倒推回初始状态或边界状态的思维方法。
性质1:如果最短路径的第k站通过Pk,则这一最短路径在由Pk出发到达终点的那一部分路径,对于始点为Pk到终点的所有可能的路径来说,必定也是距离最短的
[3]
2 动态规划的实现过程
2.1 问题的提出
如下图,从A0点铺设一条管道到A6点,中间必须经过5个中间站,第一站可以在A1,B1两地中任选一个,同理,第二、三、四、五站可供选择的地点分别是:{A2,B2,C2,D2},{A3,B3,C3},{A4,B4,C4},{A5,B5}。要求选一条从A0到A6的铺设管道,使总距离最短。
。
根据这一性质,计算时从最后一段开始,我们运用逆向思维法从后向前逐步递推,求出各点到A6的最短路径,从而求得从A0到A6的最短路径。2.3 建立动态规划模型
1)把问题的演变过程划分为恰当的阶段。可以图中的顶点来划分状态。
2)正确选择状态变量,使之既能描述过程的演变又满足无后效性。令状态量s[k]表示顶点A6到顶点k的最短距离。
3)选择决策变量Xi及相应的允许决策集合。4)正确写出状态转移方程。
初始状态:s[A6]=0,s[I]=+](1[i[n,iX
2.2 问题的分析
求解一个具有n个结点的图的最短路,我们首先想到的是穷举法,其运算量是n的指数函数。当n比较大,同时图的深度较深时,这个算法是不可取的。如果用最优化原理来思考这个问题,我们可以注意到最短路径有这样一个特性,即最短路径的子路径也必然是最短路径,而且最短路径的长度只和各条子路径的最短长度有关[2]。由此,可以把最短路径问题用动
*收稿日期:2006-05-27
A6)
状态转移方程:s[k]=min{s[j]+W[j,k]},若sIE
5)正确写出效益函数(满足三个性质)Gt,T的关系使I满足以下三个性质:
a.是定义在全过程和所有后部子过程上的数量函数。
b.要具有可分离性,并可满足递推关系即:
作者简介:梁娟(1979-),女,河南安阳人,本科,主要从事计算机应用研究。
梁娟等:利用动态规划算法求解最短路径
Gt,T(St,Xt,,,St+1)=5t(St,Xt,Gt+1,T(St+1,Xt+1,,,St+1)。
c.函数5t(St,Xt,Gt+1,T)是关于Gt+1,T严格单调。
2.4 算法实现
n中存放站点个数以及m中存放站点层数确定之后,一维数组a[10]中存放每层站点数,第一个和最后一个均为一;
a[0]=1;a[m-1]=1;
二维数组d[20][20]中存放所有距离,无路径处用相对较大值代替。
for(i=0;i
for(i=1;i
for(i=0;i
值,因为第一和最后一个值已被定义为1。
4)输入距离值时应注意,当两个站点间为开路时,只需将该值输入成一个相对比较大的值,如本例中可输入1000作为开路值。
3.2 结果分析(就例题的输出结果进行分析)
用穷举法,从A0到A6共有2@3@2@2@2@1=48种不同路径。可通过48*5=240次加法,47次比较,即通过各种可能方案的穷举,最后可求出从A0到A6的最短路径是:A0→A1→B2→A3→B4→B5→A6。相应的最短距离是18。若用本文中所述方法,需用15次比较运算和28次加法运算就够了,而且还可得到其他各点到A6的最短路径和最短距离。
4 结束语
本文介绍了一种动态规划最短路径的方法,不仅求出原问题的最优值,还可以求所有子问题的最优值。换句话说,当这个递推算法执行结束后,我们得到的不仅仅是由起点A0出发到终点A6的最短路径,而且还得到了从顶点A0出发所用中间顶点的最短路。因此,上述方法不仅是求单对顶点间最短路径算法,也是求图上单源点最短路径问题的算法。
(责任编辑 吕春红)
3 实验验证
参考文献:3.1 通过程序调试可知
1)所定义的数组均有固定大小,这使得当遇见一[1](美)维斯著冯舜玺译.数据结构与算法分析:C语言描述(原书第
二版)[M].北京:机械工业出版社,2004.
个大于此大小的路径图,不能实现求其最小路径的[2]郭嵩山等.国际大学生程序设计竞赛辅导教程[M].北京:北京大解。学出版社,2001.
2)当遇见大于本程序的路径图时,只需改动定义[3]卢开澄.计算机算法导引-设计与分析[M].北京:清华大学出版
社,1996.中数组的大小值即可。
3)输入层数时应注意应比实际层数少输入两个
SolvestheMostShor-tpath
UsingtheDynamicProgrammingAlgorithm
LIANGJuan,etal
(HenanMechanicalandEngineeringCollege,Xinxiang453002,China)
Abstract:Thedynamicprogrammingisanarithmeticwhichstudiesakindofoptimizationproblems.Thisarticleintroducedhowtosolvethemostshort-pathquestionbythedynamicprogramming.
Keywords:dynamicprogramming;optimization;path;algorithm