统一成本搜索及其 Time/Space 复杂性
Uniform Cost Search and its Time/Space Complexity
作为编程作业的一部分，我在 Python 3 中编写了一个函数 ucs(G,v)，它搜索具有加权边的有向图 G。 G中的三个节点被随机选择为目标节点，这个函数的任务是应用统一成本搜索（即最便宜的优先搜索）从a中找到最便宜的路径给定节点 v 到目标节点之一。
我有两个问题：
实现是否正确？我怀疑当到同一节点的多条路径被推送到优先级队列时，正在进行冗余检查。
如何根据 |V| 确定时间和 space 复杂性和 |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]))
关于你的第一个问题：代码对我来说似乎没问题。
关于你的第二个问题：
Uniform Cost Search 不使用启发式函数（它是蛮力搜索）。如果所有边的成本都是正数，UCS 最终会达到有限成本的目标。在这种情况下，如果存在到目标节点的有限路径，则 UCS returns 最佳路径。
时间复杂度
- 其中 e 是每条边的最小成本，b 是分支因子，c 是 成本。
因此，要发现成本为 c 的所有节点，正确的算法 必须 生成深度为 c/e 的所有节点。否则，可能会有更好（更便宜）的解决方案，但没有找到。
因此，算法最坏情况下的时间复杂度为 （因为您在每个级别上分支 b）
Space 复杂度
每个生成的节点都存储在Open List或Close List中，因此时间和space复杂度为其实一样这意味着 space 复杂度也是 .
限制
UCS 被认为是内存有限，因为内存需求是指数级的。
作为编程作业的一部分，我在 Python 3 中编写了一个函数 ucs(G,v)，它搜索具有加权边的有向图 G。 G中的三个节点被随机选择为目标节点，这个函数的任务是应用统一成本搜索（即最便宜的优先搜索）从a中找到最便宜的路径给定节点 v 到目标节点之一。
我有两个问题：
实现是否正确？我怀疑当到同一节点的多条路径被推送到优先级队列时，正在进行冗余检查。
如何根据 |V| 确定时间和 space 复杂性和 |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]))
关于你的第一个问题：代码对我来说似乎没问题。
关于你的第二个问题：
Uniform Cost Search 不使用启发式函数（它是蛮力搜索）。如果所有边的成本都是正数，UCS 最终会达到有限成本的目标。在这种情况下，如果存在到目标节点的有限路径，则 UCS returns 最佳路径。
时间复杂度
c/e 的所有节点。否则，可能会有更好（更便宜）的解决方案，但没有找到。
因此，算法最坏情况下的时间复杂度为 b）
Space 复杂度
每个生成的节点都存储在Open List或Close List中，因此时间和space复杂度为其实一样这意味着 space 复杂度也是
限制
UCS 被认为是内存有限，因为内存需求是指数级的。