from ..problem import Problem
from ..datastructures.priority_queue import PriorityQueue
import queue
def get_solver_mapping():
return dict(ucs=UCS)
class UCS(object):
# TODO, excercise 1:
# - implement Uniform Cost Search (UCS), a variant of Dijkstra's Graph Search
# - use the provided PriorityQueue where appropriate
# - to put items into the PriorityQueue, use 'pq.put(<priority>, <item>)'
# - to get items out of the PriorityQueue, use 'pq.get()'
# - store visited nodes in a 'set()'
def solve(self, problem: Problem):
node = problem.get_start_node()
visited = set()
pq = queue.PriorityQueue()
pq.put((0, node, [node]))
while not pq.empty():
f, current_node, path = pq.get()
visited.add(current_node)
if current_node.is_goal:
return path
else:
for edge in current_node.out_edges:
child = edge.to()
if child not in visited:
pq.put((current_node_priority + edge.weight, child, path + [child]))
return None
问问题
17 次