哈佛在线CS50 -学位
我刚刚开始使用BFS Intro to AI，我相信我正确地实现了CS50队列搜索算法，以找到两个参与者之间的最短路径。我不知道可能是什么问题，但如果有人能指出我可能做错了什么，我将不胜感激。此外，没有出现错误，因此这实际上使理解它变得更令人恼火。
def shortest_path(source, target):
"""
Returns the shortest list of (movie_id, person_id) pairs
that connect the source to the target.
If no possible path, returns None.
"""
#initialize the frontier to be a queue frontier because BFS is a queue and will find
#the shortest path
frontier = QueueFrontier()
#first node is added to the frontier
frontier.add(Node(source, None, None))
#Initialize the nodes explored as a empty set
nodesExplored = set()
if source == target:
raise Exception("Can't choose the same actor twice!")
# Keep looping until solution found
while True:
#if there are no solutions then just return None
if frontier.empty():
return None
# Choose a node from the frontier and remove it
node = frontier.remove()
# If node is the target, then we have a reached our goal state, our solution
if node.state == target:
#initalize an array of solutions
solutions = []
# continue to search if node has a parent
while node.parent is not None:
solutions.append(node.action, node.state)
node = node.parent
solutions.reverse()
return solutions
# Mark node as explored
nodesExplored.add(node.state)
# Add neighbors to frontier
for movie_id, person_id in neighbors_for_person(node.state):
if not frontier.contains_state(person_id) and person_id not in nodesExplored:
child = Node(person_id, node, movie_id)
frontier.add(child)这是应该发生的事情：
$ python degrees.py large Loading data... Data loaded. Name: Emma Watson Name: Jennifer Lawrence 3 degrees of separation. 1: Emma Watson and Brendan Gleeson starred in Harry Potter and the Order of the Phoenix 2: Brendan Gleeson and Michael Fassbender starred in Trespass Against Us 3: Michael Fassbender and Jennifer Lawrence starred in X-Men: First Class
但是在我输入第二个参与者之后，什么也没有发生。它只是保持空白，不返回任何东西，甚至不返回错误，所以我得到的是：
$ python degrees.py large Loading data... Data loaded. Name: Emma Watson Name: Jennifer Lawrence
回答 2
Stack Overflow用户
发布于 2020-05-04 05:41:15
我的猜测是，您对frontier.contains_state(person_id)的检查太多了，因为您阻止了将不同电影中具有相同人物的节点添加到边界，并切断了通往解决方案的可能路径
这似乎起作用了：
def shortest_path(source, target):
frontier = QueueFrontier()
frontier.add(Node(source, None, None))
nodesExplored = set()
if source == target:
raise Exception("Can't choose the same actor twice!")
while True:
if frontier.empty():
return None
node = frontier.remove()
if node.state == target:
solutions = []
while node.parent is not None:
solutions.append((node.action, node.state))
node = node.parent
solutions.reverse()
return solutions
nodesExplored.add(node.state)
for movie_id, person_id in neighbors_for_person(node.state):
if not (person_id in nodesExplored):
child = Node(person_id, node, movie_id)
frontier.add(child)然而，课程的注释也说：“如果你检测到一个目标节点，不需要将它添加到边界，你可以简单地立即返回解决方案”我认为你的代码仍然可以通过移动目标检查来改进……祝你课程顺利，我也刚刚开始学习cs50 ;-)
Stack Overflow用户
发布于 2021-04-12 17:31:16
我的猜测是，在大型数据集中，探索所有节点需要花费太多时间，这就是为什么你看不到任何东西的原因。如果您在探索邻居时移动check if node.state == target，则会极大地提高性能。
https://stackoverflow.com/questions/61516189
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号