Экспериментальная реализация первого уровня в Python

Question

Я пытаюсь реализовать BFS в Python, я понимаю, как работает алгоритм, но у меня мало опыта программирования. Я много часов думал о лучшем способе представить все и как быть максимально эффективным. Я не мог понять, как получить путь от моего начального узла до узла цели.

Я потратил много времени на поиски других алгоритмов, но мое приложение несколько отличается, и это меня смущает. Когда люди внедряют BFS, они предполагают, что у них есть график, данный им (как и статья Википедии в BFS). В моей проблеме у меня есть начальное состояние и состояние цели, которые я хочу достичь, но нет графика или дерева, поэтому я создаю узлы, когда я иду.

Например:

def BFS(initial, goal): 

    q = [initial] 
    visited = [] 

    while q: 
     n = q.pop() 
     states = generate_states(n) 

     for state in states: 
      if state == goal: 
       pass #placeholder 
      q.append(state) 
      visited.append(state) 

Это не правильно конкретизированы, потому что у меня возникают проблемы с чем-то, я не уверен, что это конкретно либо ... Если начальная и цель являются узлами, и я напишите класс типа структуры в другом месте моего кода, например:

class node: 
    state = None 
    parent = None 

Я думаю, что это подходящий способ представления узла. Поэтому, когда я вытаскиваю узел из моей очереди, он имеет информацию о том, откуда он был создан, который будет инициализирован функцией generate_states. Затем цикл for добавит каждый из этих новых узлов в очередь, и посещенная очередь, и она будет повторяться под одним из сгенерированных узлов, имеет состояние, которое соответствует моему состоянию цели.

Теперь, когда я нашел узел цели, у меня есть список посещенных узлов, но если я прослежу путь по пути назад от узла цели, разве я не замедляю алгоритм? После того, как цель была найдена, я бы посмотрел на ее родителя, нашел его родителя в посещенном списке, а затем посмотрел на родителя родителя и т. Д., Пока у меня не было пути = [узел, объект узла, ... ] от исходного узла до узла цели.

Это приводит меня к другой проблеме, когда я создаю объект-узел, который длится только для одной итерации цикла while. Как я хотел хранить объекты в массиве, каждому из них нужно уникальное имя, и нет очевидного способа (для меня) сделать это. Это была проблема, о которой я упоминал ранее, о которой я не был уверен. Таким образом, похоже, что я создаю узлы, но потом сохраняю node.state в очереди, что бессмысленно, потому что я требую, чтобы объект узла получал доступ к узлу.parent ...

Почему я нахожу это настолько сложным, я пропускаю что-то очевидное или делаю это слишком сложным?

Спасибо за чтение.

Answer 1

Я не могу комментировать большинство из этого, так как я не совсем понимаю, что вы пытаетесь сделать - как вы говорите, обычно у BFS есть график, и я не уверен, как вы предлагаете построить его, когда идете. Но я должен ответить на этот бит:

Как я имел в виду, чтобы сохранить объекты в массиве, каждый из них будет необходимо уникальное имя

Это, безусловно, ложь. Абсолютно нет необходимости давать что-то имя, если вы просто хотите сохранить его в списке - вы можете просто добавить его. Если вы беспокоитесь о том, что сможете найти его позже, то нормальная вещь, связанная с графиками, просто дает каждому узлу число, через один счетчик, который вы увеличиваете каждый раз, когда вы его определяете. Опять же, если вы просто храните узлы в списке, они автоматически получают уникальный номер: их положение в списке.

Answer 2

Ваш подход выглядит хорошо для меня.

Для получения пути обнаружения вы можете отслеживать каждый родитель узла, например. дайте ему атрибут, который установлен на узел, который его обнаружил. Таким образом, у вас есть связанный список, который отслеживает путь обнаружения. Для идти назад, как только вы достигли цели, которую вы можете сделать

def get_parents(node): 
    if node.parent is None: 
     return [] 

    yield node.parent 
    get_parents(node) 

Для отслеживания узлов сгенерированных (переменная п), просто положить узлы вы обнаружите в списках, а не только государств.

n = q.pop() 
    states = generate_states(n) 

    for state in states: 
     m = node() 
     m.state = state 
     m.parent = n 
     if state == goal: 
      pass #placeholder 
     q.append(m) 
     visited.append(m) 

Answer 3

в общем, у вас все в порядке.

но есть пара замешательств, которые я попытаюсь объяснить. во-первых, вы храните узел в очереди, а не в состоянии. и поскольку узел имеет родителя, вы можете перейти к предыдущим узлам, чтобы вы не потеряли их. во-вторых, отслеживание через родителей - это не то, о чем вам нужно беспокоиться об эффективности - вы делаете это только тогда, когда у вас есть успех (также нет нужды в именах - звучит так, будто вы путаете списки с картами?).

поэтому единственное, чего не хватает в вашем коде, это то, что вы не создаете свои узлы. когда вы получаете состояние, создаете узел и сохраняете узел, а не состояние. то все будет работать.