Простая задача поиска искусственного интеллекта. Ошибка бесконечного цикла в Python ⇐ Python

[Anonymous]

Я работаю над проектом 0 для курса искусственного интеллекта CS50 в Гарварде, и нам нужно было написать функцию shortest_path, которая используется в программе для поиска кратчайшего пути между двумя актерами в базе данных фильмов на основе общих фильмов, над которыми они работали с другими актерами. Я написал функцию, но получаю бесконечный цикл и не могу понять, почему я ее получаю. Я следовал инструкциям из лекции, где говорится, что узел к границе следует добавлять только в том случае, если этот узел не существует на границе, а также не существует в ранее исследованных узлах. Игнорирование этого может привести к бесконечному циклу, но я все еще получаю его. Тестовый пример, который я использовал, — это когда имя исходного актера — Кевин, а целевого актера — Кевин. Я просто выбираю двух разных Кевинов из списка, который предоставляется после ввода Кевина в качестве источника и имени цели. Я публикую свою функцию shortest_path и ссылку, по которой можно загрузить остальные файлы проекта вместе с соответствующими CSV-файлами для данных, используемых для тестирования проекта.
Ссылка на файлы проекта: загрузите код дистрибутива с https://cdn.cs50.net/ai/2020/x/projects/0/grades.zip и разархивируйте его.
Единственной функцией, которую нам пришлось изменить, была функция shortest_path в предоставленный код дистрибутива, так что это все, что я публикую, а также классы для используемого узла и структуры данных Queuefrontier. Остальная часть кода находится в файлах дистрибутива на случай, если вам понадобится посмотреть, как все это вписывается.
Мой код для функции shortest_path:
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.
"""
path = []

# Keep track of number of states explored
num_explored = 0

# Initialize frontier to just the starting position
start = Node(state=source, parent=None, action=None)
frontier = QueueFrontier()
frontier.add(start)

# Initialize an empty explored set
explored = set()

# Keep looping until solution found
counter = 0
while True:
print(counter)
counter = counter + 1
# If nothing left in frontier, then no path
if frontier.empty():
return None

# Choose a node from the frontier
node = frontier.remove()
num_explored += 1

# If node is the goal, then we have a solution
if node.state == target:
actions = []
cells = []
path=[]
while node.parent is not None:
#actions.append(node.action)
#cells.append(node.state)
path.append(node.action,node.state)
node = node.parent
#actions.reverse()
#cells.reverse()
path.reverse()
#solution = (actions, cells)
return path

# Mark node as explored
explored.add(node.state)

# Add neighbors to frontier
for action, state in neighbors_for_person(node.state):
if not frontier.contains_state(state) and state not in explored:
child = Node(state=state, parent=node, action=action)
frontier.add(child)

Код для узла класса и QueueFrontier:
class Node():
def __init__(self, state, parent, action):
self.state = state
self.parent = parent
self.action = action
def toString(self):
print(f"State={self.state}, Parent={self.parent}")

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