Interested Article - Поиск в ширину

Поиск в ширину

Поиск в ширину ( англ. breadth-first search , BFS ) — один из методов обхода графа . Пусть задан граф и выделена исходная вершина . Алгоритм поиска в ширину систематически обходит все ребра для «открытия» всех вершин, достижимых из , вычисляя при этом расстояние (минимальное количество рёбер) от до каждой достижимой из вершины. Алгоритм работает как для ориентированных , так и для неориентированных графов.

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

Поиск в ширину является одним из неинформированных алгоритмов поиска .

Работа алгоритма

Белый — вершина, которая ещё не обнаружена. Серый — вершина, уже обнаруженная и добавленная в очередь. Чёрный — вершина, извлечённая из очереди .

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

Рассмотрим все рёбра , выходящие из узла . Если очередной узел является целевым узлом, то поиск завершается; в противном случае узел добавляется в очередь . После того, как будут проверены все рёбра, выходящие из узла , из очереди извлекается следующий узел , и процесс повторяется.

Неформальное описание

  1. Поместить узел, с которого начинается поиск, в изначально пустую очередь.
  2. Извлечь из начала очереди узел и пометить его как развёрнутый.
    • Если узел является целевым узлом, то завершить поиск с результатом «успех».
    • В противном случае, в конец очереди добавляются все преемники узла , которые ещё не развёрнуты и не находятся в очереди.
  3. Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
  4. Вернуться к п. 2.

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

Формальное описание

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

Рекурсивная формулировка:

BFS(start_node, goal_node) {
  return BFS'({start_node}, ∅, goal_node);
}
BFS'(fringe, visited, goal_node) {
  if(fringe == ∅) {
    // Целевой узел не найден
    return false; 
  }
  if (goal_nodefringe) {
    return true;
  }
  return BFS'({child | xfringe, child ∈ expand(x)} \ visited, visitedfringe, goal_node);
}

Итеративная формулировка:

BFS(start_node, goal_node) {
 for(all nodes i) visited[i] = false; // изначально список посещённых узлов пуст
 queue.push(start_node);              // начиная с узла-источника
 while(! queue.empty() ) {            // пока очередь не пуста
  node = queue.pop();                 // извлечь первый элемент в очереди
  if(node == goal_node) {
   return true;                       // проверить, не является ли текущий узел целевым
  }
  visited[node] = true;               // пометить текущую ноду посещенной
  foreach(child in expand(node)) {    // все преемники текущего узла, ...
   if(visited[child] == false) {      // ... которые ещё не были посещены ...
    queue.push(child);                // ... добавить в конец очереди...
    visited[child] = true;            // ... и пометить как посещённые
   }
  }
 }
 return false;                        // Целевой узел недостижим
}

Реализация на Pascal :

function BFS(v : Node) : Boolean;
begin
  enqueue(v);
  while queue is not empty do
  begin
    curr := dequeue();
    if is_goal(curr) then
    begin
      BFS := true;
      exit;
    end;
    mark(curr);
    for next in successors(curr) do
      if not marked(next) then
      begin
        enqueue(next);
      end;
  end;
  BFS := false;
end;

Свойства

Обозначим число вершин и рёбер в графе как и соответственно.

Пространственная сложность

Так как в памяти хранятся все развёрнутые узлы, пространственная сложность алгоритма составляет .

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

Временная сложность

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

Полнота

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

Оптимальность

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

Поиск по критерию стоимости является обобщением поиска в ширину и оптимален на взвешенном графе с неотрицательными весами рёбер. Алгоритм посещает узлы графа в порядке возрастания стоимости пути из начального узла и обычно использует очередь с приоритетами .

История и применения

Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте . Ли независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах .

Поиск в ширину может применяться для решения задач, связанных с теорией графов :

См. также

Примечания

  1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. — 3-е изд. — Издательский дом "Вильямс", 2013. — С. 630. — 1328 с. — ISBN 978-5-8459-1794-2 (рус.). — ISBN 978-0-2620-3384-8 (англ.).
  2. MAXimal :: algo :: от 16 сентября 2013 на Wayback Machine
  3. НГТУ Структуры и алгоритмы обработки данных от 30 декабря 2012 на Wayback Machine
  4. Moore E. F. (англ.) // Harvard University Press , 1959. — Vol. 2. — P. 285—292. — 345 p. — ( ; Vol. 30) — ISSN
  5. C. Y. Lee (1961), . IRE Transactions on Electronic Computers , EC-10(3), pp. 346–365
  6. Cormen et al , Introduction to Algorithms, 3rd edition, p. 623
  7. Mathematics Stack Exchange

Литература

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. — 3rd edition. — The MIT Press, 2009. — ISBN 978-0-262-03384-8 . . Перевод 2-го издания: Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М. : , 2006. — С. 1296. — ISBN 0-07-013151-1 .
  • Глава 5. Метод уменьшения размера задачи: Поиск в ширину // М. : , 2006. — 576 с. — ISBN 978-5-8459-0987-9

Ссылки

  • Steven M. Rubin
Источник —

Same as Поиск в ширину