Гарвард Онлайн CS50 - Степени

Question

Только что запустил введение CS50 в AI, и я считаю, что правильно реализовал алгоритм поиска очереди BFS, чтобы найти кратчайший путь между двумя участниками. Я не знаю, в чем может быть проблема, но я был бы признателен, если бы кто-то мог пролить свет на то, что я могу делать неправильно. Кроме того, никаких ошибок не возникает, так что на самом деле это немного раздражает, чтобы понять.

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

Answer 1

я предполагаю, что ваш чек на frontier.contains_state(person_id) слишком велик, потому что вы предотвращаете добавление узлов с одним и тем же человеком в другом mov ie к границе и обрезаете возможный путь к решению

Кажется, это работает:

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; -)