实现双向A *最短路径算法 [英] Implementing Bidirectional A* Shortest Path Algorithm

问题描述

我正在实现对称双向A *最短路径算法，如

我可能不正确地理解算法逻辑。这是我如何将单向A *改成双向的（参考）

• 在向前搜索和向后搜索之间进行替换。保持变量 mu 作为s-t路径长度的当前最佳估计。


• 在正向搜索中，如果边缘（v，w） w >已由向后搜索扫描，请勿更新w的标签。


• 每次前向搜索扫描（v，w）以及是否 w 已通过反向搜索进行扫描，如果 dist（s，v）+ len（v，w）+ dist（w，t），则更新 mu ）< = mu


• 停止条件：当正向搜索将要扫描具有 v 的顶点时 dist（s，v）+ potential_backward（v）> = mu


• （类似的规则适用于向后搜索）

如果有人能指出我的实现中的缺陷，或者对双向A *算法进行更详细的说明，我将不胜感激

Python中的代码：

  
 bidirectional_a_star：双向A *搜索
 
g：输入图（networkx对象）
s，t：来源和目标节点
 pi_forward，pi_backward：向前和向后的潜在函数值
 wt_attr：用作边缘权重的属性名称
 
 
 def bidirectional_a_sta r（g，s，t，pi_forward，pi_backward，wt_attr ='weight'）：
＃初始化
 gRev = g.reverse（）＃反向图
 ds = {v：float（ v in g的'inf'）}＃与s或t的最佳距离
 dt = ds.copy（）
 ds [s] = 0 
 dt [t] = 0 
父母= {}＃向前/向后搜索中的前辈
父母= {} 
 pqueues = [（ds [s] + pi_forward [s]，s）]＃向前/向后搜索的优先级队列
 pqueuet = [（dt [t] + pi_backward [t]，t）] 
 
 mu = float（'inf'）＃最佳st距离
 
 scan_forward = set（）＃向前/向后搜索中的一组扫描顶点
 scan_backward = set（）
 
而（len（pqueues）> 0和len（pqueuet）> 0）：
＃前向搜索
（priority_s，vs）= heappop（pqueues）＃vs：前向队列
 
 if（priority_s> = mu）：＃停止条件
 break 
 
 for g in g.neighbors（vs）：＃扫描vs中的输出边缘
 newDist = ds [vs] + g.edge [vs] [w] [wt_attr] 
 
 if（ds [w]> newDist和w不在scand_backward中：
 ds [w] = newDist＃更新w的标签
父母[w] = vs 
 heappush（pqueues，（ds [w] + pi_forward [w] ，w））
 
 if（（（w in scand_backward）和（newDist + dt [w]< mu）））：
 mu = newDist + dt [w] 
 
 scand_forward.add（vs）＃标记为已扫描 
 
＃向后搜索
（priority_t，vt）= heappop（pqueuet）＃vt：向后队列中的第一个节点
 
如果（priority_t> = mu）：
打破
 
在gRev.w（邻居）：
 newDist = dt [vt] + gRev .edge [vt] [w] [wt_attr] 
 
 if（dt [w]> = newDist并且w不在scand_forward中）：
 if（dt [w] == newDist and parentt [vt]< w）：
继续
其他：
 dt [w] = newDist 
 parentt [w] = vt 
 heappush（pqueuet，（dt [w] + pi_backward [w]，w））
 if（w在scand_forward和newDist + ds [w]< = mu中）：
 mu = newDist + dt [w] 
 
 scand_backward.add（vt）
 
＃计算st距离和最短路径
 scan = scan_s.intersection（scanned_t）
 minPathLen = min（[扫描中的v的ds [v] + dt [v]]）＃查找st距离
 minPath = recombinantPath（ds，dt，parents，parentt，scanned）＃加入sv和vt路径
 
返回（minPathLen，minPath）
  

---

更新

遵循

<但是，在道路网络上，前向搜索扫描的节点与后向搜索扫描的节点的并集仍然大于单向搜索所扫描的节点的数量。也许这取决于输入图？

解决方案

您的问题是，您没有将正确的条件停止，停止条件是（和向后搜索都可以满足）

I am implementing a symmetric bidirectional A* shortest path algorithm, as mentioned in [Goldberg and Harrelson,2005]. This is only for understanding the algorithm, therefore I used the most basic version without any optimization steps.

My problem is the bidirectional algorithm appears to scan almost two times the number of edges scanned in a uni-directional A* search on the test graph.

Example: a s-t query on a road network using A* (left) and bidirectional A* (right). Nodes scanned by the forward and backward search are colored in red and green, respectively. The heuristic function is simply the euclidean distance to t or s. The computed paths (blue) are correct in both figures.

I may be understanding the algorithm logic incorrectly. Here is how I adapted unidirectional A* to bidirectional (from reference)

• Alternate between forward search and backward search. Maintain variable mu as the current best estimate of s-t path length.
• In the forward search, if w in edge (v,w) has been scanned by the backward search, do not update w's labels.
• Each time a forward search scan (v,w) and if w has been scanned by the reverse search, update mu if dist(s,v) + len(v,w)+dist(w,t)<= mu
• Stopping condition: when forward search is about to scan a vertex v with dist(s,v) + potential_backward(v) >= mu
• (Similar rules apply in the backward search)

I'd appreciate if anyone can point out the flaws in my implementation, or some more detailed explanation of the bidirectional A* algorithm.

Code in Python:

""" 
bidirectional_a_star: bidirectional A* search 

g: input graph (networkx object)
s, t: source and destination nodes
pi_forward, pi_backward: forward and backward potential function values
wt_attr: attribute name to be used as edge weight 
"""

def bidirectional_a_star(g,s,t,pi_forward, pi_backward, wt_attr='weight' ):
    # initialization 
    gRev = g.reverse() # reverse graph        
    ds =   { v:float('inf') for v in g } # best distances from s or t
    dt = ds.copy()
    ds[s]=0
    dt[t]=0  
    parents = {} # predecessors in forward/backward search
    parentt = {}
    pqueues =[(ds[s]+pi_forward[s],s)]  # priority queues for forward/backward search
    pqueuet = [(dt[t]+pi_backward[t],t)]

    mu = float('inf') # best s-t distance

    scanned_forward=set() # set of scanned vertices in forward/backward search
    scanned_backward=set()

    while (len(pqueues)>0 and len(pqueuet)>0):
        # forward search
        (priority_s,vs) = heappop(pqueues) # vs: first node in forward queue

        if (priority_s >= mu): # stop condition
            break

        for w in g.neighbors(vs): # scan outgoing edges from vs
            newDist = ds[vs] + g.edge[vs][w][wt_attr]            

            if (ds[w] > newDist and w not in scanned_backward):                
                ds[w] = newDist  # update w's label
                parents[w] = vs
                heappush(pqueues, (ds[w]+pi_forward[w] , w) )

            if ( (w in scanned_backward) and  (newDist + dt[w]<mu)):
                 mu = newDist+dt[w]

        scanned_forward.add(vs)  # mark vs as "scanned" 

        # backward search
        (priority_t,vt) = heappop(pqueuet) # vt: first node in backward queue

        if (priority_t>= mu ):  
            break

        for w in gRev.neighbors(vt): 
            newDist = dt[vt] + gRev.edge[vt][w][wt_attr]

            if (dt[w] >= newDist and w not in scanned_forward):
                if (dt[w] ==newDist and parentt[vt] < w):
                    continue
                else:
                    dt[w] = newDist
                    parentt[w] = vt
                    heappush(pqueuet,(dt[w]+pi_backward[w],w))
            if ( w in scanned_forward and  newDist + ds[w]<= mu):
                 mu = newDist+dt[w]

        scanned_backward.add(vt)

    # compute s-t distance and shortest path
    scanned = scanned_s.intersection(scanned_t)    
    minPathLen = min( [ ds[v]+dt[v] for v in scanned ] ) # find s-t distance   
    minPath = reconstructPath(ds,dt,parents,parentt,scanned) # join s-v and v-t path

    return (minPathLen, minPath)

---

Update

Following Janne's comment, I created a demo that tests the search on a few examples. The implementation has been improved, and fewer nodes are scanned.

Example: Shortest path from the red dot to the green dot on a (directed) grid graph. The middle figure highlights nodes scanned by A*; The right figure shows nodes scanned by the forward search (orange) and those scanned by the backward search (blue)

However, on the road network, the union of nodes scanned by the forward search and those scanned by the backward search is still more than the number of nodes scanned by a unidirectional search. Perhaps this depends on the input graph?

解决方案

Hy, Your problem is that, you don't put the right condition to stop, the stop condition is when (forward and backward search are meet),

这篇关于实现双向A *最短路径算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！