Пошук у ширину: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
|||
Рядок 22:
# Нехай {x,y} - ребро, у якому номер BFS(у) не визначено. Позначити це ребро потовщеною суцільною лінією, визначити BFS(у) як черговий BFS-номер, включити вершину у у чергу й перейти до кроку 2.
# Виключити вершину х зі черги. Якщо черга порожня, то зупинитись, інакше - перейти до кроку 2.
== Формальний опис алгоритму ==
Нижче наведено [[псевдокод]] алгоритму для випадку, коли необхідно лише знайти цільовий вузол. Залежно від конкретного застосування алгоритму, може знадобитися додатковий код, що забезпечує збереження потрібної інформації (відстань від початкового вузла, вузол-батько і т. п.)
Рекурсивна формулювання:<syntaxhighlight>
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);
}
</syntaxhighlight>Ітеративна формулювання:<syntaxhighlight>
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; // цільовий вузол недосяжний
}
</syntaxhighlight>
== Властивості ==
Позначимо число вершин і ребер в графі як <math> \vert V \vert </math> і <math> \vert E \vert </math> відповідно.
=== Просторова складність ===
Так як в пам'яті зберігаються всі розгорнуті вузли, [[Теорія складності обчислень|просторова складність]] алгоритму становить <math>O(\vert V \vert + \vert E \vert)</math>.
Алгоритм пошуку з ітеративним поглибленням схожий на пошук в ширину тим, що при кожній ітерації перед переходом на наступний рівень досліджується повний рівень нових вузлів, але вимагає значно менше пам'яті.
=== Тимчасова складність ===
Так як в гіршому випадку алгоритм відвідує всі вузли графа, при зберіганні графа у вигляді списків [[Матриця суміжності|суміжності]], [[Теорія складності обчислень|тимчасова складність]] алгоритму становить <math>O(\vert V \vert + \vert E \vert)</math>.
=== Повнота ===
Якщо у кожного вузла є кінцеве число наступників, алгоритм є повним: якщо рішення існує, алгоритм пошуку в ширину його знаходить, незалежно від того, чи є граф кінцевим. Однак якщо рішення не існує, на нескінченному графі пошук не закінчується.
=== Оптимальність ===
Якщо довжини ребер графа рівні між собою, пошук в ширину є оптимальним, тобто завжди знаходить найкоротший шлях. В разі зваженого графа пошук в ширину знаходить шлях, що містить мінімальну кількість ребер, але не обов'язково найкоротший.
Пошук за критерієм вартості є узагальненням пошуку в ширину і оптимальний на зваженому графі з невід'ємними вагами ребер. Алгоритм відвідує вузли графа в порядку зростання вартості шляху з початкового вузла і зазвичай використовує чергу з пріоритетами.
== Джерела інформації ==
| |||