Loading AI tools
З Вікіпедії, вільної енциклопедії
По́шук у ширину́ — алгоритм пошуку на графі[1].
Якщо задано граф G = (V, E) та початкову вершину s, алгоритм пошуку в ширину систематично обходить всі досяжні із s вершини. На першому кроці вершина s позначається, як пройдена, а в список додаються всі вершини, досяжні з s без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаються, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовується черга та принцип FIFO. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений.
Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані k перед тим як пройти вершини на відстані k+1.[1]
Наведемо кроки алгоритму
Нижче наведено псевдокод алгоритму для випадку, коли необхідно лише знайти цільовий вузол. Залежно від конкретного застосування алгоритму, може знадобитися додатковий код, що забезпечує збереження потрібної інформації (відстань від початкового вузла, вузол-батько і т. ін.)
Рекурсивна формулювання:
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; // цільовий вузол недосяжний
}Позначимо число вершин і ребер в графі як і відповідно.
Так як в пам'яті зберігаються всі розгорнуті вузли, просторова складність алгоритму становить .
Алгоритм пошуку з ітеративним поглибленням схожий на пошук в ширину тим, що при кожній ітерації перед переходом на наступний рівень досліджується повний рівень нових вузлів, але вимагає значно менше пам'яті.
Так як в гіршому випадку алгоритм відвідує всі вузли графу, при зберіганні графу у вигляді списків суміжності[en], тимчасова складність алгоритму становить .
Якщо у кожного вузла є кінцеве число наступників, алгоритм є повним: якщо рішення існує, алгоритм пошуку в ширину його знаходить, незалежно від того, чи є граф кінцевим. Однак якщо рішення не існує, на нескінченному графі пошук не закінчується.
Якщо довжини ребер графу рівні між собою, пошук в ширину є оптимальним, тобто завжди знаходить найкоротший шлях. В разі зваженого графу пошук в ширину знаходить шлях, що містить мінімальну кількість ребер, але не обов'язково найкоротший.
Пошук за критерієм вартості є узагальненням пошуку в ширину і оптимальний на зваженому графі з невід'ємними вагами ребер. Алгоритм відвідує вузли графу в порядку зростання вартості шляху з початкового вузла і зазвичай використовує чергу з пріоритетами.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
