直线优化Dijkstra算法

2019-12-20 14:57:44  浏览:261  作者:老王

  原始Dijkstra算法一种行之有效的优化方法是:减小算法中成功搜索的搜索范围,以尽快到达目标结点。其核心思想是:在所研究的网络可以被看成平面网络的条件下,将临时标记结点到源点的最短路径与本临时标记结点到目标结点的直线距离之和作为此临时标记结点的一个属性值,这个属性值将作为从临时标记结点集合中选取永久标记结点的依据。即选取此属性值最小的临时结点作为永久标记结点,这种优化方法称为直线优化Dijkstra算法。此方法使得Dijkstra算法的搜索方向智能地趋向于目标结点,减少了算法中遍历的结点个数,从而提高了搜索速度。

  直线优化Dijkstra算法与原始Dijkstra算法的搜索过程比较示意图如图1所示。

  由图1可见,原始Dijkstra算法的搜索过程,可近似为以源点为圆心的一系列同心圆,搜索过程没有考虑终点所在的方向或位置,在从源点出发的搜索过程中,其他结点与终点被搜索到的概率是相同的;直线优化Dijkstra算法的搜索过程,可近似为以源点和终点为焦点的一系列同心椭圆。

直线优化Dijkstra算法

  因为永久标记点的选取原则为:当前结点距源点的最短距离与此结点到终点的直线距离之和最小者被选取为永久标记点,所以其搜索过程明显趋向于终点,搜索过程到达终点的速度明显快于原始Dijkstra算法,搜索到的结点少于原始Diikstra算法。

  如图1(b)所示,设SP=2,Sq=5。PE一8,qE=2。从源点出发进行原始Dijkstra算法搜索,首先选取结点P和q作为临时标记点,因为Sp长度小于Sp长度,所以选取结点p为永久标记结点,再以p为新的源点继续进行下一轮搜索,而结点P则是最后要被淘汰的。如果采用直线优化Dijkstra算法,则因为Sp+pE=10,Sq+qE=7,所以结点q被选取为永久标记点。如图2所示,L1为临时标记结点,p1距源点的最短路径长度,Lq为临时标记结点pn距源点的最短路径长度,D1为结点P1,到终点的真线距离,Dn为结点Pn到终点的直线距离,P1和Pn的连线为c。原始Dijkstra算法永久标记结点的选取原则是:如果L1>Ln,则选取P。为永久标记结点,如果L1<Ln,则选取P1。为永久标记点。直线优化Dijkstra算法永久标记点的选取原则是:如果L1+D1>Ln+Dn,则选取尸。为永久标记结点,如果L1+D1>Ln+Dn,则选取P1为永久标记结点。

直线优化Dijkstra算法

  直线优化Dijkstra算法永久标记结点选取原则的一个前提条件是L1为P1。到源点的最短路径,即P1的最短路径值不会再被修改,也即

图片.png

图片.png

  直线优化Diikstra算法特别适合于网络中弧的权值为弧长度,并且可以认为整个网络在同一平面内。在地理信息系统中,一般在较小的地理范围内,可以用平面代替地球表面;网络中两结点间的直线距离最短是此优化算法的另外一个前提条件,

  直线优化Dijkstra算法优于原始Dijkstra算法的关键在于其最大搜索范围得到了明显的减小,从而使搜索速度得到提高,图3显示了两种算法的最大搜索范围。图中圆为原始Dijkstra算法的最大搜索范围,椭圆为直线优化Dijkstra算法的最大搜索范围。

直线优化Dijkstra算法

  设最短路径长度为2a,则原始Dijkstra算法的最大搜索圆半径极限为2a,直线优化Dijkstra算法的最大搜索椭圆长轴长度为2n。椭圆上一点到两个焦点的直线距离之和为2a,设其短轴长度为2a,源点和终点为焦点。用圆和椭圆的面积来近似表示两种算法所搜索的结点数目,其分别为

图片.png

  图片.png,所以图3所示的圆和椭圆面积之比大于4:1。即说明原始Dijkstra算法的最大搜索范围是直线优化Dijkstra算法最大搜索范围的4倍以上,表1中的数据进一步证明了这一点。

  直线优化Dijkstra算法最大搜索范围与源点在网络中的位置有关。当源点接近网络边界或者处在网络边界上时,其搜索的结点数目刚能不会明显地少于原始Dijkstra算法的。总之。直线优化Dijkstra算法搜索的结点数目要比原始Dijkstra算法少,具体的数量根据网络的具体情况不同而有所差异。另外,当源点和终点不连通时,两种算法的搜索范围是相同的,它们的搜索终止条件都是搜索到整个网络所有与源点连通的结点而未找到终点。在这种情况下,直线优化Dijkstra算法与原始Dijkstra算法搜索的结点数相同,但直线优化Dijkstra算法的开销要高于原始Dijkstra算法,因为直线优化I)ijkslra算法要处理两结点间的最短距离计算问题。

直线优化Dijkstra算法

评论区

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

【随机新闻】

返回顶部