X一>O),并将c放入OPEN中。 取OPEN中最小的K值K砌,反复调用Process—node(),直到 K,d>=h(C),C被移出OPEN。这样将权值变化扩散到c及 附近节点,附近节点的子节点也可能会变化。新的最短路径 序列产生。指引C从新路径走向目标。下面详细介绍Proeess —node()函数:Process—node()
{
L1X=MIN—STATE() //取OPEN中k值最小的节点 L2if X=NULL then return一1//如表空则结束
L3k,d=K(X);//取OPEN中最小的k值 IJ4OF.LETE(X);//将x从OPEN中移到CLOSED,以下 将权值变化传递给邻居节点
15if k,d
L6for each neighbor Y ofX:
L7if h(Y)<=k,d and="" h(x)="">h(Y)+c(Y,X)then //在x将影响传播给其邻居之前,//如果x的一个邻 居Y可以减少x的路径费用,则x的子节点是Y,x采用较小 的路径费用,
L8next(X)=Y;h(X)=h(Y)+c(Y,X) //注意:L8下面程序的h(X)也被修改
L9if k讪=h(X)then//2.路径变化,x节点到O最少路 径费用减小
L10for each neighbor Y of X://将x的变化扩散给每个 邻居Y,
Lll ift(Y)=NEw or//新的
(next(Y)=X and h(Y)≠h(X)+c(X,Y))
or//如果Y的子节点是X,//X的任何路径费用变化都 会影响Y的路径费用。
L12(next(Y)≠X and h(Y)>h(X)+c(X,Y)) then//检验x的每个邻居Y,是否有更短的路径
L13next(Y)=X;INSERT(Y,h(X)+C(X,Y))//所有的获得新路径费用的邻居都放在OPEN中 //这样它 们也会将权值变化扩散到它们自己的邻居。
L14else //3.L8处h(X)可能被降低,使k,d> h(x),路径费用减小,
L15for each neighbor Y ofX:
L16if t(Y)=NEW or
L17(next(Y)=X and h(Y)≠h(X)+C(X,Y)) then
L18next(Y)一x;INSERT(Y,h(X)+e(X,Y)); //权值变化传播给新节点及它的子节点
L19else
L20if next(Y)≠X and h(Y)>h(X)+C(X,Y) then //Y的子节点不是x,
I::2l INSERT(X,h(x))//但从X走能减少Y的路径 费用,则将X放回OPEN表
L22else
L23if next(Y)≠X and h(x)>h(Y)+C(Y,X) and//假如X的路径费用能被非子节点Y减少
L24t(Y)=CLOSED and h(Y)>kv.1then 125INSERT(Y,h(Y))//将Y重新放回OPEN L26Return GET—K,d()//从OPEN表中取k的最小值 K试
}
这样车辆在C找出新的子节点,按照这个新子节点指引 行走,直到找到目标012J。
动态算法在动态环境中寻路非常有效,向目标点移动 中,只检查最短路径上下一节点或临近节点的变化情况,修 改时也是只修改障碍物附近局部节点。它也可用在机器人寻 路上,机器人寻路要求陕速,当外界环境不断发生变化,频繁 等待系统重新计算整个路径无疑是低效率的;或应用在游戏 中,敌人或障碍物不断移动的情况下。
4仿真实现及性能分析:
按照以上动态算法思路,用Visual C++实现算法,创建 一个40×40节点路网,s是起点,O是目标点。黑色是障碍。可 以看出初始时,路网中每个点(除了O)都用箭头指向下一个 点,即它的子节点,在任一点按照箭头方向一步步走,即可以 最少费用到达O。在图1,显然S到O按箭头指引,直线走最 短。图2,当车辆走到大半路程时,发现新障碍物挡住去路,修 改附近节点h值,并修改每个节点的子节点(看新障碍物左 边,箭头方向被修改)。逐渐将新变化扩散到各邻居,从而寻 找到新的最短路径。浅灰色粗线是车辆行走轨迹。从图1、图 2对比看出,发现新障碍后,只重新修改其附近的节点(浅灰 色细线内),并没有将重新计算所有节点。本路网节点较少, 当节点较多时,本算法的优势更明显。
图1初始路网中各节点的子节点
图2发现障碍后,附近节点的子节点变化
静态和动态这两个算法在相同的环境条件比较,越早发 现路径变化(堵塞、障碍等),效率越高,因为静态算法需要重 新计算更多的节点。而且节点越多,路途中路径变化越频繁, 动态算法效率越高。下面是在同一台计算机上,路途上遇到 路径变化也相同,在不同节点数情况下得出的计算花费时 间。可以看到在节点大小逐渐增大的情况下得出,节点越多, 动态算法效率越高。
表1静态算法和动态算法比较
(下转第206页)
一155—
图3曲柄滑块机构 图4四连杆机构 方便)技术的支持下,直接用IE观看;另外只需改变时间传 感器的cycleInterval域值,运动的快慢可以控制;其次虚拟仿 真模型的VRML文件很小,图3曲柄滑块机构只有8.98k,图 4的四连杆机构只有3.99k,便于网络发布。
参考文献:
[1]康与云,赵晓春.基于VRML的牛头刨床机构运动的虚拟仿 真[J].工程图学学报,2006,(1).
[2]叶琳.VRML网络3D仿真系统中的机构运动仿真[J].计算机 辅助工程,Jun.2002(2).
[3]邱丽芳,翁海珊.基于VRML与Java的机械设计网上实验室 软件的研制【J].仪器与仪表用户,2006,13(1).
[4]吴小华,VRML与JAVA编程[M].北京:国防工业出版社, 2002—1.
[5]赛博科技工作室.VRML与JAVA编程技术[M].北京:人民 邮电出版社,2002—1.
[6]刘臣勇,等.基于VRML和VRMLScript的虚拟现实仿真研究 [J].计算机工程与应用,2002—4.
[7]黄锡恺,郑文纬.机械原理第六版[M].北京:高等教育出版 社,1989—4.
[作者简介]
方锡武(1971一),男(汉族),湖北武穴人,硕士,讲 师,主要从事工程制图、计算机图形学教学与研究 工作。
(上接第155页)
5结束语
随着城市交通快速发展,城市汽车数量不断增多,城市 越来越拥挤,交通堵塞情况更会频繁发生。现阶段,静态最短 路径算法已经比较完善,但在实践中动态条件下最短路径算 法更有实际意义,尤其在嵌入式系统中,采用动态算法可在 不影响准确性的情况下,减少计算量,对变化做出快速反应, 找出理想的路径。
本算法侧重于减少搜索节点、从而减少计算时间,怎样 进一步减少存储空间是要一步考虑的问题。
参考文献:
[1]郭晶,等.嵌入式导航系统得最短路径算法研究[J].装备指 挥技术学院学报,2005,(5):101.
[2]Anthony Stentz.Optimal and Efficient Path Planning for Partially—Known Environments[C].Proceedings of IEEE International Conference on Robotics and Automation,1994, (5).
-?———206.--——
Anthony Stentz.The Focussed D￥Algorithm for Real—Time Replanning[C].Proceedings of the International Joint Conference on Artificial Intelligence,1995,(8).
Ismail Chabini.Discrete Dynamic Shortest Path Problems In Transportation Applications:Complexity and Algorithms with Optimal Run Time[J].Transportation Research Records, 1998.
Nils J Nilsson.人工智能[M].机械工业出版社,2000.
Andrew S Tanenbaum.计算机网络[M].清华大学出版社, 1998.
严蔚敏,吴伟民.数据结构[M].清华大学出版社,1996.
[作者简介]
田鹏飞(1979一),男(汉族),安徽人,硕士研究生, 主要研究方向:最短路径算法、嵌入式系统。
王剑英(1948一),男(汉族),安徽人,副教授,主要 研究方向:算法、嵌入式系统、图形图像处理。
1j
1J
b
H
口№
口
动态最短路径算法及其仿真
作者:田鹏飞 , 王剑英 , TIAN Peng-fei, WANG Jian-ying作者单位:中国科学技术大学计算机科学与技术系,安徽,合肥,230027刊名:计算机仿真
英文刊名:COMPUTER SIMULATION年,卷(期):2007,24(6)被引用次数:
1次
参考文献(7条)
1. 郭晶 嵌入式导航系统得最短路径算法研究 [期刊论文]-装备指挥技术学院学报 2005(05)
2. Anthony Stentz Optimal and Efficient Path Planning for Partially-Known Environments 19943. Anthony Stentz The Focussed D* Algorithm for Real-Time Replanning 1995
4. Ismail Chabini Discrete Dynamic Shortest Path Problems In Transportation Applications:Complexityand Algorithms with Optimal Run Time 19985. Nils J Nilsson 人工智能 2000
6. Andrew S Tanenbaum. 熊桂喜 . 王小虎 计算机网络 19987. 严蔚敏 . 吴伟民 数据结构 1996
相似文献(10条)
1.学位论文 徐海云 动态最短路径的拟物方法的研究 2005
随着经济的讯猛发展,交通运输的需求变得愈加迫切。而大城市中新建和扩建道路的可能性却越来越小,并且,仅仅依靠基础设施的建设,不可能 满足交通需求,城市交通拥挤状况越来越严重。
随着科技的飞速发展,计算机技术、网络技术和通讯技术已逐步渗入到交通领域。随着计算机的迅猛普及以及信息技术的发展,地理信息系统得到 日益广泛和深入的应用。随着信息的发展,利用现代化科学技术管理城市交通,合理并科学地引导和控制交通流,有效地提高现有交通网络的运行效率 ,这是城市交通管理发展的必然。智能运输系统ITS,正是在这种情况下提出来的。城市交通流诱导系统,简称UTFGS,是ITS的重要组成部分,是解决城 市交通问题的关键。最短路径算法是交通网络分析的核心,网络分析是空间分析的一个重要方面,网络分析中最基本最关键的问题是最短路径问题。最 短路径问题是许多领域中选择最优问题的基础,在交通网络分析中占有重要地位。
本文正是基于交通信息的路网的动态最短路径的拟物方法研究。在本文中,首先从图论的角度描述了最短路径含义及其分类,讨论了静态最优路径 的算法及高度信息化的条件下的动态最短路径算法;然后阐述了拟物方法的含义、应用并给出用拟物方法解决问题的路线;最后,分析了已有的求静态 和动态最短路径的算法的不足,提出了用拟物方法求解最短路径的思路。
本文提出了拟物方法求最短路径的思路,这无疑对解决城市交通问题提供了一定的理论基础,因此此文具有一定的学术价值和现实意义。
2.期刊论文 邹亮 . 徐建闽 . 朱玲湘 . ZOU Liang. XU Jian-min. ZHU Ling-xiang A*算法改进及其在动态最短路径问题 中的应用 -深圳大学学报(理工版) 2007,24(1)
动态最短路径搜索算法是智能交通系统技术应用的关键问题之一.为了解决这一问题,提出以一致性原则动态形式为基础的动态A*算法(dynamic A*algorithm,DA* algorithm)并证明了在两节点间动态下界满足一致性原则动态形式前提下,该算法能够求解满足先进先出原则的动态网络中两节点间最短 路径问题.在以广州市交通路网为基础的动态网络上对DA*算法进行试验.试验结果表明,Dijkstra算法的和A*算法的平均计算时间分别是DA*算法的6.55和 1.43倍.
3.学位论文 俞峰 复杂动态随机网络最短路径问题研究 2009
经典的最短路径问题是图论、网络优化中一个重要的研究内容,它不仅可用于解决生产实际中的许多问题,而且还常常作为一个基本工具用于解决 其他优化问题。然而,大量现实世界中的网络都具有动态、随机特性,这种网络中两节点间最短路径的定义及其求解方法都不同于传统最短路径问题 ,对其进行研究具有广泛的实际应用价值和理论研究价值.本文针对动态随机网络最短路径问题进行了较为深入的系统研究.论文的研究内容和创新点 主要包括以下几个方面:
(1).提出了基于蚁群优化(ACO)的赋时蚁群优化(TACO)算法,用于解决动态随机网络先验(a priori)最短路径问题。首先阐明了在动态,随机环境下对 先验最短路径问题进行研究的重要意义。然后对当前复杂网络搜索问题的研究情况及其方法进行了介绍,分析表明这些方法能够用于解决动态随机网络 最短路径问题,然而,单独应用这些方法又存在一些不可避免的缺陷。考虑到复杂网络搜索方法本身的特点,本文将其融合于赋时蚁群优化的框架之中 ,既解决了单独采用这些方法时带来的缺陷,又充分利用了这些搜索方法提供的网络结构信息,从而提高了TACO算法的搜索质量和效率.此外,本文提 出的TACO算法并不是适合所有的网络模型,而是主要针对现实世界中广泛存在的无标度网络模型,并希望籍此增强算法的针对性,从而进一步提高算法 的有效性。
(2).动态随机网络最短路径的求解需要考虑时间以及网络的状态,因此其问题规模相对经典最短路径问题显著增加。而对于诸如动态随机网络实时最 短路径这类问题的求解,问题规模的扩大将使下一节点的选择计算量大增,这势必影响算法的有效性。而事实上,对于给定的动态随机网络源.目标节 点对以及源节点出发时刻,可能只有很少一部分节点、边以及边的状态能真正最终构成实时最短路径,即大量的网络信息对于给定的最短路径求解都是 冗余的。基于此,本文研究了用于动态随机网络实时最短路径求解的网络化简问题,给出了网络化简的具体思路和方法,并对影响算法化简结果的一些 因素以及算法的复杂性进行了分析。
(3).动态随机网络中边的通过耗费是一个不确定量,因此在某些边的通过耗费不具有周期性且难以预测的情况下,采用实时最短路径往往比采用先验 最短
路径更为有效。这里,实时最短路径由根据网络当前状态在线选择的下一节点构成。本文根据已有的研究成果,进一步分析了实时最短路径可能的度量 方式,进而给出了采用负效用函数度量网络最短路径的定义.将CPA(Convolution—propagation approach)近似处理方法引入到动态随机网络实时最短 路径的求解中,并基于改进的遗传算法设计了相应的路径搜索算法GASPSP。 (4).针对本文提出的TACO算法的算法性能进行了仿真分析,并对算法中一 些影响算法性能的重要参数进行了相关分析;针对本文提出的网络化简算法进行了仿真分析,验证了其有效性;针对本文提出的实时最短路径算法进行
了仿真分析和比较,验证了该算法的有效性。
关键词 动态随机网络;最短路径;复杂网络;蚁群优化算法:网络化简;路由策略
4.期刊论文 王江晴 . 康立山 . Wang Jiangqing. Kang Lishan动态车辆路径问题中的实时最短路径算法研究 -武汉理
工大学学报(交通科学与工程版) 2007,31(1)
分析了现有算法处理动态车辆路径问题时的缺陷,提出了一个动态网络环境下的实时路径评估模型,在此基础之上构造了一个改进的Dijkstra双桶算 法.该算法能根据静态和动态的交通信息找出客户之间的实时最短路径,并对车辆的旅行线路进行调整,具有对随机事件和突发事件进行实时处理的能力 ,已用于解决动态车辆路径问题.实验结果表明,该算法能在动态网络环境下找到实时的最短路径,减少车辆旅行的总成本.
5.期刊论文 章昭辉 一种基于离散变权网络的动态最短路径快速算法 -计算机科学 2010,37(4)
在离散变权动态网络中,求解最短路径的最优化算法的计算复杂性通常远大于O(n~2),不适用于实时的动态交通信息导航系统.提出的动态最短路径快 速算法,是在所有的当前点与下一个待选点之间以及待选点与目标点之间的动态弧的权值之和中选择一个最小值,然后把该待选点作为当前点继续选择下 一个待选点,如此反复,直到达到目标点为止.该算法所得到的路径是一个次优解,但其执行时间却比寻找最优解算法要小得多,并且所得到的解要优于选择 最短距离路径的动态解.实验结果证明这是一种适用于动态交通导航的有效算法.
6.学位论文 焦元 警用GIS中动态时间最短路径的研究与应用 2009
这些年来,由于国内经济的飞速发展,汽车的数量越来越多,而道路容量不能满足现在的需求,交通事故和交通堵塞时时刻刻在发生,城市的交通 压力越来越大。在这种形势下,由于无法避开前方道路可能发生的交通拥挤,对警察快速出警带来了非常大的困扰。而警用地理信息(GIS)系统则不同 ,这种警用GIS系统通过最短路径算法来搜索得到一条最佳路线来满足司机的要求。这样不仅使得路径最短,而且还可以避开拥堵的交通,对警察快速出 警,提高出警效率,并极大的保证了人民群众的生命和财产安全。
本文研究了警用地理信息系统最优路径规划的系统方法,包括:交通路网特点,优化的Dijktsra最短路径算法,动态时间权重的最优路径规划等。 首先,介绍了地理信息系统的概念原理,其中包括了基本概念、地图信息模型、还有地理信息系统数据的管理组织,在实际的道路网中,由于它的 特殊性,我们经过分析原来的算法,选择出了最佳算法来改进。
其次,警用地理信息系统最优路径规划问题特点,选择Dijktsra算法进行优化。本文通过对目前较典型的两种Dijktsra算法优化方法进行测试与对 比,发现各自的优缺点,而且每种典型优化算法都有一定的局限条件,并非各种情况都适用,为应用人员结合实际情况选择合适的算法提供了依据。 最后,本文研究了在警用地理信息系统中这种特殊的情况下的最短路径算法。提出了从起点到终点所用时间最短的路径的方法,这个就是时间最短 路径算法。当得到动态道路限制值以后,利用数据结构的数组来存储该动态道路限制值。并设计实现了基于动态时间最短路径算法的警用地理信息系统 。
7.期刊论文 崔岚 . 阮秋琦 . CUI Lan. RUAN Qiu-qi结点有拥塞的动态最短路径问题的算法研究 -信号处理
2005,21(z1)
最短路径问题在交通运输领域以及网络路由选择方向都有着重要的应用.本文在有必经结点且所经结点无序的最短路径算法的基础上,研究结点有拥 塞且拥塞程度是动态变化的最短路径问题.对于这种情况的研究,在交通运输领域的高速公路以及局域网络上的路由选择都有着重要的应用.文中对结点的 权值,即拥塞程度的预测采用了Kalman滤波方法,并用改进了的Dijkstra算法求解结点间的最短路径.相关实验结果及分析表明,该方案可以有效地解决结 点有拥塞且拥塞动态变化的最短路径问题.
8.学位论文 邵永强 网络分析在车辆导航系统中的应用——及最佳路径搜索软件的开发 2003
论文首先系统的介绍网络分析、图论、地理网络的建模问题等相关理论以及导航电子地图的数据结构、数据模型等理论,接着论述了交通道路网络在 电子地图中的表示和网络边的定权问题.在此基础上论文以图论作为网络分析的主要方法,对导航电子地图的道路网进行网络分析,将最佳路径搜索问题转 化为图论中的最短路径搜索问题.最短路径搜索是图论的经典问题,论文对最短路径搜索问题作了简单的分类,重点介绍了Dijkstra、Moore等几种经典的 最短路径搜索算法,对它们之间时间复杂度进行了简单的比较,并针对传统算法的表达方式、存储结构等方面的缺点讨论了最短路径搜索算法的优化方法 ,以此为基础论文提出了改进的Moore算法,着重讨论了基于改进Moore算法的次最短路径的搜索、实时动态最短路径搜索以及复杂条件下最短路径搜索等 问题.并运用了改进的Moore算法编制了一套最佳路径搜索的软件.
9.期刊论文 李洪波 . 张吉赞 . Li Hongbo. Zhang Jizan单源点最短路径动态优化算法 -计算机工程与应用
2006,42(3)
设计了最短路径时间复杂度取决于边数e和点数n的动态优化算法.采用了独特的动态PV集合链,改进了当前求得的最短路径向量D的存储结构,用PV集 合链对向量D进行动态管理,使其时间开销为e+(n-1)×(n-2)/2+3n.当n>4时,SPDOA算法的性能明显优于Dijkstra算法,呈现出良好的动态优化特性.最后 对动态优化算法与Dijkstra算法用理论公式得出的数据进行了时间性能比较.
10.学位论文 金振伟 基于图论的动态导航系统最短路径算法研究 2006
近几年来,随着国民经济的发展,城市中机动车辆渐渐增多,交通需求在不断增加,公路交通流量也越来越大,由此导致了交通拥堵的频繁发生 ,城市交通正面临着越来越大的压力。在这种形势下,基于静态地图的自主导航虽然可为驾驶员规划一条“最短”路径,但却无法避开前方道路可能发 生的交通拥挤。而动态导航则不同,系统获知出发点与目的地之间的交通状况,经过规划得到一条满足用户需求的合理路径。这种导航方式不仅可以有 效的避开拥堵,节省出行成本,而且对整个路网有着良性影响。
本文研究了车载动态导航系统最优路径规划的系统方法,包括:交通路网的矢量地图表达,图论中的最短路径算法,动态时间权重的最优路径规划 等。
首先,简述了有关地理信息系统的一些基本概念,包括地理信息系统概念、地理信息系统数据模型、地理信息系统数据的组织和管理,针对城市交 通道路网的特点,着重分析研究了城市交通道路网的矢量地图表达、网络中的交通限制信息的表示等。
其次,本文介绍了图论的相关理论,研究了图的邻接矩阵、邻接表的表达方式,对图的搜索方式进行了分析,基于边带的通用图搜索,基于FIFO队 列的广度优先搜索,基于栈的深度优先搜索。同时分析了Dijkstra算法求单源点最短路径问题,即图的最短路径树,以及用在交通网络中的欧几米得试 探法。
最后,本文研究了基于交通路网的A*算法,该算法能够有效降低Dijkstra算法的时间复杂性,提高系统的运行效率。提出了从起点到终点所用时间 最短的路径的方法,即所谓的时间最短路径算法。确定了算法对路段动态阻抗的获得方法。提出了动态路段阻抗的数据结构即各路段的阻抗序列数组以 及时段数组。综合考虑了动态导航系统路径规划子系统的解决方案。
引证文献(1条)
1. 柯文德 . 彭志平 基于时间最短的足球机器人进攻路径规划 [期刊论文]-计算机工程与设计 2008(14)
下载时间:2010年6月28日
范文五：路径规划(最短路径)算法C_实现
路径规划（最短路径）算法C#实现路径规划（最短路径）算法C#实现
以前空闲的时候用C#实现的路径规划算法，今日贴它出来，看大家有没有更好的实现方案。关于路径规划（最短路径）算法的背景知识，大家可以参考《C++算法－－图算法》一书。
该图算法描述的是这样的场景：图由节点和带有方向的边构成，每条边都有相应的权值，路径规划（最短路径）算法就是要找出从节点A到节点B的累积权值最小的路径。
首先，我们可以将“有向边”抽象为Edge类：
publicclassEdge
{
publicstringStartNodeID;
publicstringEndNodeID;
publicdoubleWeight;//权值，代价
} 节点则抽象成Node类，一个节点上挂着以此节点作为起点的“出边”表。
publicclassNode
{
privatestringiD;
privateArrayListedgeList;//Edge的集合－－出边表
publicNode(stringid)
{
this.iD=id;
this.edgeList=newArrayList();
}
property#regionproperty
publicstringID
{
get
{
returnthis.iD;
}
}
publicArrayListEdgeList
{
get
{
returnthis.edgeList;
}
}
#endregion
}
在计算的过程中，我们需要记录到达每一个节点权值最小的路径，这个抽象可以用PassedPath类来表示：
///<summary>
///PassedPath用于缓存计算过程中的到达某个节点的权值最小的路径
///</summary>
publicclassPassedPath
{
privatestringcurNodeID;
privateboolbeProcessed;//是否已被处理
privatedoubleweight;//累积的权值
privateArrayListpassedIDList;//路径
publicPassedPath(stringID)
{
this.curNodeID=ID;
this.weight=double.MaxValue;
this.passedIDList=newArrayList();
this.beProcessed=false;
}
#regionproperty
publicboolBeProcessed
{
get
{
returnthis.beProcessed;
}
set
{
this.beProcessed=value;
}
}
publicstringCurNodeID
{
get
{
returnthis.curNodeID;
}
}
publicdoubleWeight
{
get
{
returnthis.weight;
}
set
{
this.weight=value;
}
}
publicArrayListPassedIDList
{
get
{
returnthis.passedIDList;
}
}
#endregion
}
另外，还需要一个表PlanCourse来记录规划的中间结果，即它管理了每一个节点的PassedPath。
///<summary>
///PlanCourse缓存从源节点到其它任一节点的最小权值路径＝》路径表
///</summary>
publicclassPlanCourse
{
privateHashtablehtPassedPath;
#regionctor
publicPlanCourse(ArrayListnodeList,stringoriginID)
{
this.htPassedPath=newHashtable();
NodeoriginNode=null;
foreach(NodenodeinnodeList)
{
if(node.ID==originID)
{
originNode=node;
}
else
{
PassedPathpPath=newPassedPath(node.ID);
this.htPassedPath.Add(node.ID,pPath);
}
}
if(originNode==null)
{
thrownewException("Theoriginnodeisnotexist!");
}
this.InitializeWeight(originNode);
}
privatevoidInitializeWeight(NodeoriginNode)
{
if((originNode.EdgeList==null)||(originNode.EdgeList.Count==0))
{
return;
}
foreach(EdgeedgeinoriginN
ode.EdgeList)
{
PassedPathpPath=this[edge.EndNodeID];
if(pPath==null)
{
continue;
}
pPath.PassedIDList.Add(originNode.ID);
pPath.Weight=edge.Weight;
}
}
#endregion
publicPassedPaththis[stringnodeID]
{
get
{
return(PassedPath)this.htPassedPath[nodeID];
}
}
}
在所有的基础构建好后，路径规划算法就很容易实施了，该算法主要步骤如下：
(1)用一张表(PlanCourse)记录源点到任何其它一节点的最小权值，初始化这张表时，如果源点能直通某节点，则权值设为对应的边的权，否则设为double.MaxValue。
(2)选取没有被处理并且当前累积权值最小的节点TargetNode，用其边的可达性来更新到达其它节点的路径和权值（如果其它节点 经此节点后权值变小则更新，否则不更新），然后标记TargetNode为已处理。
(3)重复(2)，直至所有的可达节点都被处理一遍。
(4)从PlanCourse表中获取目的点的PassedPath，即为结果。
下面就来看上述步骤的实现，该实现被封装在RoutePlanner类中：
///<summary>
///RoutePlanner提供图算法中常用的路径规划功能。
///2005.09.06
///</summary>
publicclassRoutePlanner
{
publicRoutePlanner()
{
}
#regionPaln
//获取权值最小的路径
publicRoutePlanResultPaln(ArrayListnodeList,stringoriginID,stringdestID)
{
PlanCourseplanCourse=newPlanCourse(nodeList,originID);
NodecurNode=this.GetMinWeightRudeNode(planCourse,nodeList,originID);
#region计算过程
while(curNode!=null)
{
PassedPathcurPath=planCourse[curNode.ID];
foreach(EdgeedgeincurNode.EdgeList)
{
PassedPathtargetPath=planCourse[edge.EndNodeID];
doubletempWeight=curPath.Weight+edge.Weight;
if(tempWeight<targetPath.Weight)
{
targetPath.Weight=tempWeight;
targetPath.PassedIDList.Clear();
for(inti=0;i<curPath.PassedIDList.Count;i++)
{
targetPath.PassedIDList.Add(curPath.PassedIDList[i].ToString());
}
targetPath.PassedIDList.Add(curNode.ID);
}
}
//标志为已处理
planCourse[curNode.ID].BeProcessed=true;
//获取下一个未处理节点
curNode=this.GetMinWeightRudeNode(planCourse,nodeList,originID);
}
#endregion
//表示规划结束
returnthis.GetResult(planCourse,destID);
}
#endregion
#regionprivatemethod
#regionGetResult
//从PlanCourse表中取出目标节点的PassedPath，这个PassedPath即是规划结果
privateRoutePlanResultGetResult(PlanCourseplanCourse,stringdestID)
{
PassedPathpPath=planCourse[destID];
if(pPath.Weight==int.MaxValue)
{
RoutePlanResultresult1=newRoutePlanResult(null,int.MaxValue);
returnresult1;
}
string[]passedNodeIDs=newstring[pPath.PassedIDList.Count];
for(inti=0;i<passedNodeIDs.Length;i++)
{
passedNodeIDs[i]=pPath.PassedIDList[i].ToString();
}
RoutePlanResultresult=newRoutePlanResult(passedNodeIDs,pPath.Weight);
returnresult;
}
#endregion
#regionGetMinWeightRudeNode
//从PlanCourse取出一个当前累积权值最小，并且没
有被处理过的节点
privateNodeGetMinWeightRudeNode(PlanCourseplanCourse,ArrayListnodeList,stringoriginID)
{
doubleweight=double.MaxValue;
NodedestNode=null;
foreach(NodenodeinnodeList)
{
if(node.ID==originID)
{
continue;
}
PassedPathpPath=planCourse[node.ID];
if(pPath.BeProcessed)
{
continue;
}
if(pPath.Weight<weight)
{
weight=pPath.Weight;
destNode=node;
}
}
returndestNode;
}
#endregion
#endregion
}
2006.05.22 应众多朋友要求，下面给出一个简单示例：
RoutePlanner.Plan 过程详解：
(1)用一张表(PlanCourse)记录源点到任何其它一节点的最小权值，初始化这张表时，如果源点能直通某节点，则权值设为对应的
边的权，否则设为double.MaxValue
(2)选取没有被处理并且当前累积权值最小的节点TargetNode，用其边的可达性来更新到达其它节点的路径和权值（如果其它节点
经此节点后权值变小则更新，否则不更新），然后标记TargetNode为已处理
(3)重复(2)，直至所有的可达节点都被处理一遍。
(4)从PlanCourse表中获取目的点的PassedPath，即为结果。
[STAThread]
staticvoidMain(string[]args)
{
ArrayListnodeList=newArrayList();
//*****************BNode*******************
NodeaNode=newNode("A");
nodeList.Add(aNode);
//A->B
EdgeaEdge1=newEdge();
aEdge1.StartNodeID=aNode.ID;
aEdge1.EndNodeID="B";
aEdge1.Weight=10;
aNode.EdgeList.Add(aEdge1);
//A->C
EdgeaEdge2=newEdge();
aEdge2.StartNodeID=aNode.ID;
aEdge2.EndNodeID="C";
aEdge2.Weight=20;
aNode.EdgeList.Add(aEdge2);
//A->E
EdgeaEdge3=newEdge();
aEdge3.StartNodeID=aNode.ID;
aEdge3.EndNodeID="E";
aEdge3.Weight=30;
aNode.EdgeList.Add(aEdge3);
//*****************BNode*******************
NodebNode=newNode("B");
nodeList.Add(bNode);
//B->C
EdgebEdge1=newEdge();
bEdge1.StartNodeID=bNode.ID;
bEdge1.EndNodeID="C";
bEdge1.Weight=5;
bNode.EdgeList.Add(bEdge1);
//B->E
EdgebEdge2=newEdge();
bEdge2.StartNodeID=bNode.ID;
bEdge2.EndNodeID="E";
bEdge2.Weight=10;
bNode.EdgeList.Add(bEdge2);
//*****************CNode*******************
NodecNode=newNode("C");
nodeList.Add(cNode);
//C->D
EdgecEdge1=newEdge();
cEdge1.StartNodeID=cNode.ID;
cEdge1.EndNodeID="D";
cEdge1.Weight=30;
cNode.EdgeList.Add(cEdge1);
//*****************DNode*******************
NodedNode=newNode("D");
nodeList.Add(dNode);
//*****************CNode*******************
NodeeNode=newNode("E");
nodeList.Add(eNode);
//C->D
EdgeeEdge1=newEdge();
eEdge1.StartNodeID=eNode.ID;
eEdge1.EndNodeID="D";
eEdge1.Weight=20;
eNode.EdgeList.Add(eEdge1);
RoutePlannerplanner=newRoutePlanner();
RoutePlanResultresult=planner.Paln(nodeList,"A","D");
planner=null;
}
转载请注明出处范文大全网 » 利用动态规划算法求解最短路径
亖呉?盀
