资源描述：
《复杂网络中最短路径问题的求解算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《自动化技术与应用》2010年第29卷第3期计算机应用ComputerApplications复杂网络中最短路径问题的求解算法研究*冯震1,刘佳2,李靖2,曹延飞3(1.湖北师范学院控制科学与工程系,湖北黄石435002;2.石家庄铁路职业技术学院信息工程系,河北石家庄050041;3.石家庄经济学院,河北石家庄050031)摘要:本文以时间代价作为目标函数,针对复杂网络的优化问题进行研究,给出了目标评价函数模型的建立过程,提出了改进的A*算法求解复杂网络中最短路径问题的算法,并以城市交通为例,对算法进行了验证,实验结果表明所
2、提出的算法可适用于一般多重图中最短路径问题的快速求解,具有广泛的应用价值。关键词:多重图;A*算法;最短路径;中图分类号:TP393.02文献标识码:A文章编号:1003-7241(2010)03-0032-05ResearchontheAlgorithmforShortestPathProbleminComplicatedNetworkFENGZhen1,LIUJia2,LIJing2,CAOYan-fei3(1.DepartmentofControlScienceandEngineeringHubeiNormalUnive
3、rsityHuangshi,435002China;2.DepartmentofInformationEngineeringShijiazhuangInstituteofRailwayTechnologyShijiazhuang050041China;3.ShijiazhuangInstituteofEconomicsShijiazhuang050031China)Abstract:Focusingontheoptimizationproblemsaboutcomplicatednetwork,thispaperpresent
4、sanalgorithmtosolvetheshortestpathsproblemincomplicatednetworkbasedonA*algorithm,inwhichthetimecostistakenastargetfunctionandtheestablishmentofthetargetfunctionmodelisgiven.Experimentalresultsshowthatthealgorithmproposedcanbeusedtosolvetheshortestpathsproblemsquickl
5、yinmulti-graph.Keywords:multi-graph;A*algorithm;shortestpaths1引言了时间依赖的网络中最小时间路径算法;贺红[7]等人提出了时间依赖网络最短路径的新算法;林澜[8]等人对动最短路径问题是计算机科学与地理信息科学等领域的研究热点问题,人们继Dijkstra开创性的工作提出态网络中的最短路径进行了研究。然而以上大部分求了大量求解最短路径问题的算法[1-5]。目前一些简单网解算法要么以时间作为目标函数,要么以空间作为目标络图是最短路径搜索问题的主要研究对象,因此出现的函数进
6、行求解,并不同时涉及时间和空间的搜索,下面相关算法也都是针对简单网络的。计算机网络与通信、本文将以城市公共交通为例,介绍复杂网络中涉及时空分布式处理和智能交通系统(ITS)的兴起给这个传统的搜索的最短路径问题的求解算法。研究课题带来了新的转折,这些要求解决最短路径问题的领域都以复杂网络图的结构呈现。因此,对复杂网络2算法模型的建立中最短路径问题求解算法的研究具有重大的意义,一些2.1空间数据结构的建立专家和学者开始着手这方面的研究,谭国真[6]等人提出公共交通网络空间数据结构的建立主要是道路和停靠站点数据结构的建立。道路网是一
7、个网状结构,道*基金项目:河北省教育厅自然科学项目(编号Z2009460)路数据结构采用拓扑型矢量表示法。整个道路网络,可收稿日期:2009-12-1832
8、TechniquesofAutomation&Applications计算机应用《自动化技术与应用》2010年第29卷第3期ComputerApplications以看成是由多段道路连接而成,连接点即为道路和道路速度。Y是常数,因为每次换乘可能会遇到许多不可知的交叉点。以道路和道路的交叉点为结点,结点和结点因素,如过马路需要绕行天桥等等。所以每次换乘除了之间的道路为链,可
9、建立链-结点式的拓扑数据结构,所需的换乘时间外,还应额外添加一段时间。t1是所有可曲线道路可由多段道路进行拟合。每段道路由两个交能换乘公车的最晚首发车时间。t2是所有可能换乘公车叉点确定,且每段道路和每段道路只在端点处相交。公的最早末班车时间。Nmin是最少换乘次数。Nmax
