Малого BFS Деталь Разъяснение

Question

Стандартная реализация BFS что-то вроде (любезно Википедия):

Breadth-First-Search(Graph, root): 
    create empty set S 
    create empty queue Q  
    root.parent = NIL 
    Q.enqueue(root)      
    while Q is not empty: 
     current = Q.dequeue() 
     if current is the goal 
      return current 
     for each node n that is adjacent to current: 
      if n is not in S: 
       add n to S 
       n.parent = current 
       Q.enqueue(n) 

мне было интересно, почему проверка, чтобы увидеть, если текущая цель не может быть сделана, глядя через сосед смежных к текущему. Напр. что-то вроде:

Breadth-First-Search(Graph, root): 
    create empty set S 
    create empty queue Q  
    root.parent = NIL 
    if root is the goal 
     return root 
    Q.enqueue(root)      
    while Q is not empty: 
     current = Q.dequeue() 
     for each node n that is adjacent to current: 
      if n is the goal   // check here instead 
        n.parent = current 
        return n 
      if n is not in S: 
       add n to S 
       n.parent = current 
       Q.enqueue(n) 

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

Я понимаю, что это означает необходимость добавления дополнительной проверки перед циклом while, чтобы узнать, является ли корень целью, но кроме этого, есть ли какая-то причина, по которой bfs не реализована так? Это должно быть технически быстрее?

Answer 1

Ваша версия отлично работает, если вы положили чек на корень (вы должны поместить это в вопрос).

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

Обычно разница не значительна, и люди делают это первым способом только потому, что код проще.

Answer 2

Я решил, что реорганизую его еще дальше. Я заметил, что корень не был добавлен непосредственно в S, что означает, что он будет добавлен позже, а затем снова проверен. Я перенесла создание S и Q после раннего возврата корня. Переключилось то, что означает, что корневой каталог не должен быть установлен в Q, а затем проверил Q, чтобы проверить, есть ли в нем корень, а затем вычеркните root. Я переместил проверку in S, чтобы быть первым внутри каждого цикла, потому что эта проверка предотвратит проверку цели один или несколько раз в каждом цикле, проверка цели будет предотвращать только проверку S в один раз. Он также позволяет мне удалить дублирование n.parent = текущего кода, не помогает производительности, но мне не нравится дублирование.

Breadth-First-Search(Graph, root): 
    root.parent = NIL 
    if root is the goal 
     return root 
    create empty set S 
    add root to S 
    create empty queue Q 
    current = root 
    while true 
     for each node n that is adjacent to current: 
      if n in S: 
       continue 
      n.parent = current 
      if n is the goal 
       return n 
      add n to S 
      Q.enqueue(n) 
     if Q empty 
      break 
     current = Q.dequeue()