Python проблема изменения направления поиска в ширину - PullRequest
Новая
       84

Python проблема изменения направления поиска в ширину

0 голосов
/ 18 июня 2020

В настоящее время я участвую в курсе CS50 «Введение в искусственный интеллект» на EDX. В первую неделю мне нужно было реализовать поиск в ширину, чтобы найти степени разделения между актерами. Мой код работает, хотя смотреть на него некрасиво, единственное, что доставляет мне проблемы, - это изменение пути. Я не могу найти решение проблемы, заключающейся в том, что while l oop выполняется только один раз, а не несколько раз, как предполагалось.

Я отметил упомянутое while l oop в коде знаком # @ # в примере кода и Frontier et c. взяты из файла util.py, который я вставил под образцом кода. Результатом функции shorttest_path в настоящее время является одна пара mov ie id и worker_id, тогда как это должно быть несколько пар, в зависимости от степени разделения между двумя действующими лицами, которые вы вводите в начале. 

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.
"""

# TODO

QF = QueueFrontier()

startNode = Node(state=source, parent=None, action=None)

QF.add(startNode)

exploredNodes = set()

while True:

    if QF.empty():

        return None

    else:

        currentNode = QF.remove()

        if currentNode.state not in exploredNodes:

            exploredNodes.add(currentNode.state)

            neighbors = neighbors_for_person(currentNode.state)

            for movie_id, person_id in neighbors:
                if person_id == target:
                    movies = []
                    actors = []
               while currentNode.action is not None:     #@#
                        print("Cycle")
                        movies.append(currentNode.action)
                        actors.append(currentNode.state)
                        currentNode = currentNode.parent
                    movies.reverse()
                    actors.reverse()
                    print(movies)
                    print(actors)
                    path = list(zip(movies, actors))
                    return path
                else:
                    newNode = Node(state=person_id, parent=currentNode, action=movie_id)

                    QF.add(newNode)

util.py: 

class Node():
def __init__(self, state, parent, action):
    self.state = state
    self.parent = parent
    self.action = action


class StackFrontier():
def __init__(self):
    self.frontier = []

def add(self, node):
    self.frontier.append(node)

def contains_state(self, state):
    return any(node.state == state for node in self.frontier)

def empty(self):
    return len(self.frontier) == 0

def remove(self):
    if self.empty():
        raise Exception("empty frontier")
    else:
        node = self.frontier[-1]
        self.frontier = self.frontier[:-1]
        return node


class QueueFrontier(StackFrontier):

def remove(self):
    if self.empty():
        raise Exception("empty frontier")
    else:
        node = self.frontier[0]
        self.frontier = self.frontier[1:]
        return node
...