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

Материал из Поле цифровой дидактики
Версия от 08:09, 26 июля 2022; ru_wikipedia>InternetArchiveBot (Спасено источников — 2, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.8)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Шаблон:Другие значения

Файл:Breadth-First-Search-Algorithm.gif
Поиск в ширину

Поиск в ширину (Шаблон:Lang-en, BFS) — один из методов обхода графа. Пусть задан граф [math]\displaystyle{ G = (V, E) }[/math] и выделена исходная вершина [math]\displaystyle{ s }[/math]. Алгоритм поиска в ширину систематически обходит все ребра [math]\displaystyle{ G }[/math] для «открытия» всех вершин, достижимых из [math]\displaystyle{ s }[/math], вычисляя при этом расстояние (минимальное количество рёбер) от [math]\displaystyle{ s }[/math] до каждой достижимой из [math]\displaystyle{ s }[/math] вершины. Алгоритм работает как для ориентированных, так и для неориентированных графов.<ref>{{#if:Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн|Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Алгоритмы: построение и анализ]]|{{#if:|[{{{ссылка}}} Алгоритмы: построение и анализ]|Алгоритмы: построение и анализ}}}}{{#if:| = {{{оригинал}}} }}{{#if:| / .|{{#if:||.}}}}{{#if:Алгоритмы: построение и анализ|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:3-е изд| — 3-е изд.}}{{#switch:{{#if:|м}}{{#if:Издательский дом "Вильямс"|и}}{{#if:2013|г}} 

 |миг= — {{#if:|{{#switch:|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{  }}|}} }}: Издательский дом "Вильямс", 2013.
 |ми= — {{#if:|{{#switch:|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{  }}|}} }}: Издательский дом "Вильямс".
 |мг= — {{#if:|{{#switch:|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{  }}|}} }}, 2013.
 |иг= — Издательский дом "Вильямс", 2013.
 |м= — {{#if:|{{#switch:|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{  }}|.}} }}
 |и= — Издательский дом "Вильямс".
 |г= — 2013.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:630| — С. 630.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:1328| — 1328 с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:978-5-8459-1794-2 (рус.)| — ISBN 978-5-8459-1794-2 (рус.)}}</ref>

Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии [math]\displaystyle{ k + 1 }[/math], выполняется обход вершин на расстоянии [math]\displaystyle{ k }[/math].

Поиск в ширину является одним из неинформированных алгоритмов поиска<ref name="emaxx" />.

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

Файл:Animated BFS.gif
Белый — вершина, которая ещё не обнаружена. Серый — вершина, уже обнаруженная и добавленная в очередь. Чёрный — вершина, извлечённая из очереди<ref name="nstu" />.

Поиск в ширину работает путём последовательного просмотра отдельных уровней графа, начиная с узла-источника [math]\displaystyle{ u }[/math].

Рассмотрим все рёбра [math]\displaystyle{ (u,v) }[/math], выходящие из узла [math]\displaystyle{ u }[/math]. Если очередной узел [math]\displaystyle{ v }[/math] является целевым узлом, то поиск завершается; в противном случае узел [math]\displaystyle{ v }[/math] добавляется в очередь. После того, как будут проверены все рёбра, выходящие из узла [math]\displaystyle{ u }[/math], из очереди извлекается следующий узел [math]\displaystyle{ u }[/math], и процесс повторяется.

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

  1. Поместить узел, с которого начинается поиск, в изначально пустую очередь.
  2. Извлечь из начала очереди узел [math]\displaystyle{ u }[/math] и пометить его как развёрнутый.
    • Если узел [math]\displaystyle{ u }[/math] является целевым узлом, то завершить поиск с результатом «успех».
    • В противном случае, в конец очереди добавляются все преемники узла [math]\displaystyle{ u }[/math], которые ещё не развёрнуты и не находятся в очереди.
  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_node ∈ fringe) {
    return true;
  }
  return BFS'({child | x ∈ fringe, child ∈ expand(x)} \ visited, visited ∪ fringe, goal_node);
}

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

BFS(start_node, goal_node) {
 for(all nodes i) visited[i] = false; // изначально список посещённых узлов пуст
 queue.push(start_node);              // начиная с узла-источника
 visited[start_node] = true;
 while(! queue.empty() ) {            // пока очередь не пуста
  node = queue.pop();                 // извлечь первый элемент в очереди
  if(node == goal_node) {
   return 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;

Свойства

Обозначим число вершин и рёбер в графе как [math]\displaystyle{ \vert V \vert }[/math] и [math]\displaystyle{ \vert E \vert }[/math] соответственно.

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

Так как в памяти хранятся все развёрнутые узлы, пространственная сложность алгоритма составляет [math]\displaystyle{ O(\vert V \vert + \vert E \vert) }[/math]<ref name="emaxx" />.

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

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

Так как в худшем случае алгоритм посещает все узлы графа, при хранении графа в виде списков смежности, временная сложность алгоритма составляет [math]\displaystyle{ O(\vert V \vert + \vert E \vert) }[/math]<ref name="emaxx" /><ref name="nstu" />.

Полнота

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

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

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

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

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

Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте<ref name="moore1959" />. Ли независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах<ref name="lee1961" /><ref>Cormen et al, Introduction to Algorithms, 3rd edition, p. 623</ref><ref name="se_origin" />.

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

См. также

Шаблон:Wikibooks

Примечания

1 }} 
       | {{#switch: 1
         | узкие = columns reflist-narrow
         | широкие = columns reflist-wide
         | #default = columns
         }}
       | {{#switch: 1
         | 1 = 
         | 2 | 3 = columns
         | #default = columns reflist-narrow
         }}
       }}
     | columns
     }}
   }}" style="{{#if: 
   | column-width:{{{colwidth}}};
   | {{#if: 1
     | {{#iferror: {{#ifexpr: 1 > 1 }}
       | {{#switch: 1
         | узкие | широкие = 
         | #default = column-width:1;
         }}
       }}
     }}
   }} list-style-type: {{#switch: 
   | upper-alpha
   | upper-roman
   | lower-alpha
   | lower-greek
   | lower-roman = {{{group}}}
   | #default = decimal
   }};">

<references group="" responsive="{{#if: 

 | 0
 | {{#if: 1
   | {{#iferror: {{#expr: 1 > 1 }}
     | {{#switch: 1
       | узкие | широкие = 1
       | #default = 0
       }}
     | {{#switch: 1
       | 1 = 0
       | #default = 1
       }}
     }}
   | 1
   }}
 }}"><ref name="emaxx">MAXimal :: algo :: Поиск в ширину в графе и его приложения Шаблон:Wayback</ref>
 <ref name="nstu">НГТУ Структуры и алгоритмы обработки данных Обход графа в ширину Шаблон:Wayback</ref>
 <ref name="moore1959">Шаблон:Source </ref>
 <ref name="lee1961">C. Y. Lee (1961), An algorithm for path connection and its applications. IRE Transactions on Electronic Computers, EC-10(3), pp. 346–365</ref>
<ref name="se_origin">Mathematics Stack Exchange Origin of the Breadth-First Search algorithm</ref></references>

Ошибка скрипта: Модуля «Check for unknown parameters» не существует.

Литература

  • {{#if:T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein|T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Introduction to Algorithms]]|{{#if:|[{{{ссылка}}} Introduction to Algorithms]|Introduction to Algorithms}}}}{{#if:| = {{{оригинал}}} }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Introduction to Algorithms|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:3rd edition| — 3rd edition.}}{{#switch:{{#if:|м}}{{#if:The MIT Press|и}}{{#if:2009|г}}
 |миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: The MIT Press, 2009.
 |ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: The MIT Press.
 |мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2009.
 |иг= — The MIT Press, 2009.
 |м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
 |и= — The MIT Press.
 |г= — 2009.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. {{{страницы}}}.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:978-0-262-03384-8| — ISBN 978-0-262-03384-8}}. Перевод 2-го издания: {{#if:Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн|Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Алгоритмы: построение и анализ]]|{{#if:|[ Алгоритмы: построение и анализ]|Алгоритмы: построение и анализ}}}}{{#if:Introduction to Algorithms| = Introduction to Algorithms }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Алгоритмы: построение и анализ|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:2-е изд| — 2-е изд.}}{{#switch:{{#if:М.|м}}{{#if:«Вильямс»|и}}{{#if:2006|г}} 

 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: «Вильямс», 2006.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: «Вильямс».
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}, 2006.
 |иг= — «Вильямс», 2006.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М..}} }}
 |и= — «Вильямс».
 |г= — 2006.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:1296| — С. 1296.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:0-07-013151-1| — ISBN 0-07-013151-1}}

Ссылки

Шаблон:Навигация

Шаблон:Алгоритмы поиска на графах

Источник — http://digida.mgpu.ru/index.php?title=Поиск_в_ширину&oldid=4658