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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Порядок обходу вершин.
Ілюстрація пошуку у ширину. Чорні вершини пройдено, сірі чекають у черзі

По́шук у ширину́ — алгоритм пошуку на графі.[1]

Якщо задано граф G = (VE) та початкову вершину s, алгоритм пошуку в ширину систематично обходить всі досяжні із s вершини. На першому кроці вершина s позначається, як пройдена, а в список додаються всі вершини, досяжні з s без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаються, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовується черга. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений.

Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані k перед тим як пройти вершини на відстані k+1.[1]

Алгоритм[ред.ред. код]

Наведемо кроки алгоритму

  1. Почати з довільної вершини v. Виконати BFS(v):=1. Включити вершину v у чергу.
  2. Розглянути вершину, яка перебуває на початку черги; нехай це буде вершина х. Якщо для всіх вершин, суміжних із вершиною х, уже визначено BFS-номери, то перейти до кроку 4, інакше - до кроку 3.
  3. Нехай {x,y} - ребро, у якому номер BFS(у) не визначено. Позначити це ребро потовщеною суцільною лінією, визначити BFS(у) як черговий BFS-номер, включити вершину у у чергу й перейти до кроку 2.
  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;                        // цільовий вузол недосяжний
}

Властивості[ред.ред. код]

Позначимо число вершин і ребер в графі як і відповідно.

Просторова складність[ред.ред. код]

Так як в пам'яті зберігаються всі розгорнуті вузли, просторова складність алгоритму становить .

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

Тимчасова складність[ред.ред. код]

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

Повнота[ред.ред. код]

Якщо у кожного вузла є кінцеве число наступників, алгоритм є повним: якщо рішення існує, алгоритм пошуку в ширину його знаходить, незалежно від того, чи є граф кінцевим. Однак якщо рішення не існує, на нескінченному графі пошук не закінчується.

Оптимальність[ред.ред. код]

Якщо довжини ребер графа рівні між собою, пошук в ширину є оптимальним, тобто завжди знаходить найкоротший шлях. В разі зваженого графа пошук в ширину знаходить шлях, що містить мінімальну кількість ребер, але не обов'язково найкоротший.

Пошук за критерієм вартості є узагальненням пошуку в ширину і оптимальний на зваженому графі з невід'ємними вагами ребер. Алгоритм відвідує вузли графа в порядку зростання вартості шляху з початкового вузла і зазвичай використовує чергу з пріоритетами.

Джерела інформації[ред.ред. код]

  1. а б Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). 22.2. Introduction to Algorithms (англ. ) (вид. 2-ге). MIT Press. с. 531. ISBN 0-262-03293-7. 

Див. також[ред.ред. код]