Python中的統一成本搜索

Question

我已經在Python中實現了一個簡單的圖形數據結構，其結構如下。代碼在這裏只是爲了澄清函數/變量的含義，但它們很容易理解，所以你可以跳過去閱讀它。

# Node data structure 
class Node: 

    def __init__(self, label):   
     self.out_edges = [] 
     self.label = label 
     self.is_goal = False 


    def add_edge(self, node, weight = 0):   
     self.out_edges.append(Edge(node, weight)) 


# Edge data structure 
class Edge: 

    def __init__(self, node, weight = 0):   
     self.node = node 
     self.weight = weight 

    def to(self):         
     return self.node 


# Graph data structure, utilises classes Node and Edge 
class Graph:  

    def __init__(self):        
     self.nodes = [] 

    # some other functions here populate the graph, and randomly select three goal nodes. 

現在我想實現一個uniform-cost search（即BFS與優先級隊列，保證最短路徑），它從一個給定節點v啓動，並返回一個最短路徑（以列表形式）的一個三個目標節點。通過目標節點，我的意思是一個節點的屬性is_goal設置爲true。

這是我的實現：現在

def ucs(G, v): 
    visited = set()     # set of visited nodes 
    visited.add(v)     # mark the starting vertex as visited 
    q = queue.PriorityQueue()  # we store vertices in the (priority) queue as tuples with cumulative cost 
    q.put((0, v))     # add the starting node, this has zero *cumulative* cost 
    goal_node = None     # this will be set as the goal node if one is found 
    parents = {v:None}    # this dictionary contains the parent of each node, necessary for path construction 

    while not q.empty():    # while the queue is nonempty 
     dequeued_item = q.get()   
     current_node = dequeued_item[1]    # get node at top of queue 
     current_node_priority = dequeued_item[0] # get the cumulative priority for later 

     if current_node.is_goal:     # if the current node is the goal 
      path_to_goal = [current_node]   # the path to the goal ends with the current node (obviously) 
      prev_node = current_node    # set the previous node to be the current node (this will changed with each iteration) 

      while prev_node != v:     # go back up the path using parents, and add to path 
       parent = parents[prev_node] 
       path_to_goal.append(parent) 
       prev_node = parent 

      path_to_goal.reverse()     # reverse the path 
      return path_to_goal      # return it 

     else: 
      for edge in current_node.out_edges:  # otherwise, for each adjacent node 
       child = edge.to()     # (avoid calling .to() in future) 

       if child not in visited:   # if it is not visited 
        visited.add(child)    # mark it as visited 
        parents[child] = current_node # set the current node as the parent of child 
        q.put((current_node_priority + edge.weight, child)) # and enqueue it with *cumulative* priority 

，大量的測試後，並與其他算法的比較，這個實現似乎工作得很好 - 直到我用這個圖試了一下：

無論出於何種原因，ucs(G,v)返回路徑H -> I其成本0.87，而不是路徑H -> F -> I，成本0.71（此路徑獲得了ru指定DFS）。下圖也給了一個不正確的路徑：

算法給G -> F代替G -> E -> F，由DFS再次獲得。在這些罕見的情況下，我可以觀察到的唯一模式是選定的目標節點總是有一個循環。我無法弄清楚哪裏出了問題。任何提示將不勝感激。

Answer 1

通常對於搜索，我傾向於保持隊列的節點部分的路徑。這不是真正的記憶效率，但實施起來更便宜。

如果您想要父映射，請記住當子項位於隊列頂部時更新父映射只是安全的。只有這樣算法才能確定到當前節點的最短路徑。

def ucs(G, v): 
    visited = set()     # set of visited nodes 
    q = queue.PriorityQueue()  # we store vertices in the (priority) queue as tuples 
            # (f, n, path), with 
            # f: the cumulative cost, 
            # n: the current node, 
            # path: the path that led to the expansion of the current node 
    q.put((0, v, [v]))    # add the starting node, this has zero *cumulative* cost 
            # and it's path contains only itself. 

    while not q.empty():    # while the queue is nonempty 
     f, current_node, path = q.get() 
     visited.add(current_node) # mark node visited on expansion, 
            # only now we know we are on the cheapest path to 
            # the current node. 

     if current_node.is_goal:  # if the current node is a goal 
      return path    # return its path 
     else: 
      for edge in in current_node.out_edges: 
       child = edge.to() 
       if child not in visited: 
        q.put((current_node_priority + edge.weight, child, path + [child])) 

注意：我還沒有真正測試過這個，所以請隨時發表評論，如果它不能馬上工作。