python - 统一成本搜索及其时间/空间复杂度

Question

作为编程作业的一部分，我在 Python 3 中编写了一个函数 ucs(G,v)，它搜索具有加权边的二合字母 G。 G 中的三个节点被随机选择为目标节点，该函数的任务是应用统一成本搜索(即最便宜的优先搜索)从将节点 v 赋给目标节点之一。

我有两个问题:

• 实现是否正确？我怀疑在将到同一节点的多条路径推送到优先级队列时进行了冗余检查。

• 我怎样才能根据 |V| 确定时间和空间的复杂性和 |E|?

我很感激任何建议，尤其是第二个问题。就 |V| 而言，我无法在网上任何地方找到 UCS 的复杂性和|E|。

这是我的实现:

def ucs(G, v):
    visited = set()                  # set of visited nodes
    q = queue.PriorityQueue()        # paths are tuples with cumulative cost
    q.put((0, [v]))                  # add the starting node, zero cost   

    while not q.empty():             # while the queue is nonempty
        current_path_priority, current_path = q.get()  # get top item
        current_node = current_path[-1]    # current_node is the node at the end  
        visited.add(current_node)          # mark it as visited

        if current_node.is_goal:           # if the current node is a goal
            return current_path            # return it

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

                if child not in visited:                # if it is not visited 
                    new_cost = current_path_priority + edge.weight  
                    q.put((new_cost, current_path + [child])) 

Answer 1

关于您的第一个问题:代码对我来说似乎没问题。

关于你的第二个问题:

Uniform Cost Search 不使用启发式函数(这是一种强力搜索)。如果所有边的成本都是正数，UCS 最终会达到有限成本的目标。在这种情况下，如果存在到目标节点的有限路径，UCS 将返回最优路径。

时间复杂度

- 其中 e 是每条边的最小成本，b 是分支因子，c 是成本。 因此，要发现成本 c 内的所有节点，正确的算法必须 生成深度 c/e 内的所有节点。否则，可能会有更好(更便宜)的解决方案，但没有找到。 所以，算法最坏情况时间复杂度是 (因为您在每个级别上按 b 因子进行分支)

空间复杂度

每个生成的节点都存储在Open List 或Close List 中，因此时间和空间复杂度实际上是相同的。这意味着空间复杂度也是 .

限制

UCS 被认为是内存有限，因为内存需求是指数级的。