Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
По́шук у ширину́ — алгоритм пошуку на графі.
Якщо задано граф G = (V, E) та початкову вершину s, алгоритм пошуку в ширину систематично обходить всі досяжні із s вершини. На першому кроці вершина s позначається, як пройдена, а в список додаються всі вершини, досяжні з s без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаються, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовується черга та принцип FIFO. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений.
Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані k перед тим як пройти вершини на відстані k+1.
Алгоритм
Наведемо кроки алгоритму
- Почати з довільної вершини v. Виконати BFS(v):=1. Включити вершину v у чергу.
- Розглянути вершину, яка перебуває на початку черги; нехай це буде вершина х. Якщо для всіх вершин, суміжних із вершиною х, уже визначено BFS-номери, то перейти до кроку 4, інакше - до кроку 3.
- Нехай {x,y} - ребро, у якому номер BFS(у) не визначено. Позначити це ребро потовщеною суцільною лінією, визначити BFS(у) як черговий BFS-номер, включити вершину у чергу й перейти до кроку 2.
- Виключити вершину х із черги. Якщо черга порожня, то зупинитись, інакше - перейти до кроку 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; // цільовий вузол недосяжний }Властивості
Позначимо число вершин і ребер в графі як 
і 
відповідно.
Просторова складність
Так як в пам'яті зберігаються всі розгорнуті вузли, просторова складність алгоритму становить 
.
Алгоритм пошуку з ітеративним поглибленням схожий на пошук в ширину тим, що при кожній ітерації перед переходом на наступний рівень досліджується повний рівень нових вузлів, але вимагає значно менше пам'яті.
Часова складність
Так як в гіршому випадку алгоритм відвідує всі вузли графу, при зберіганні графу у вигляді [en], тимчасова складність алгоритму становить .
Повнота
Якщо у кожного вузла є кінцеве число наступників, алгоритм є повним: якщо рішення існує, алгоритм пошуку в ширину його знаходить, незалежно від того, чи є граф кінцевим. Однак якщо рішення не існує, на нескінченному графі пошук не закінчується.
Оптимальність
Якщо довжини ребер графу рівні між собою, пошук в ширину є оптимальним, тобто завжди знаходить найкоротший шлях. В разі зваженого графу пошук в ширину знаходить шлях, що містить мінімальну кількість ребер, але не обов'язково найкоротший.
Пошук за критерієм вартості є узагальненням пошуку в ширину і оптимальний на зваженому графі з невід'ємними вагами ребер. Алгоритм відвідує вузли графу в порядку зростання вартості шляху з початкового вузла і зазвичай використовує чергу з пріоритетами.
Джерела інформації
- Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. Розділ 22.2: Пошук вшир. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
Див. також
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Po shuk u shirinu algoritm poshuku na grafi Poryadok obhodu vershin Ilyustraciya poshuku u shirinu Chorni vershini projdeno siri chekayut u cherzi Yaksho zadano graf G V E ta pochatkovu vershinu s algoritm poshuku v shirinu sistematichno obhodit vsi dosyazhni iz s vershini Na pershomu kroci vershina s poznachayetsya yak projdena a v spisok dodayutsya vsi vershini dosyazhni z s bez vidviduvannya promizhnih vershin Na kozhnomu nastupnomu kroci vsi potochni vershini spisku vidmichayutsya yak projdeni a novij spisok formuyetsya iz vershin kotri ye she ne projdenimi susidami potochnih vershin spisku Dlya realizaciyi spisku vershin najchastishe vikoristovuyetsya cherga ta princip FIFO Vikonannya algoritmu prodovzhuyetsya do dosyagnennya shukanoyi vershini abo do togo chasu koli na pevnomu kroci v spisok ne vklyuchayetsya zhodna vershina Drugij vipadok oznachaye sho vsi vershini dostupni z pochatkovoyi uzhe vidmicheni yak projdeni a shlyah do cilovoyi vershini ne znajdenij Algoritm maye nazvu poshuku v shirinu oskilki front poshuku mizh projdenimi ta neprojdenimi vershinami odnomanitno rozshiryuyetsya vzdovzh vsiyeyi svoyeyi shirini Tobto algoritm prohodit vsi vershini na vidstani k pered tim yak projti vershini na vidstani k 1 AlgoritmNavedemo kroki algoritmu Pochati z dovilnoyi vershini v Vikonati BFS v 1 Vklyuchiti vershinu v u chergu Rozglyanuti vershinu yaka perebuvaye na pochatku chergi nehaj ce bude vershina h Yaksho dlya vsih vershin sumizhnih iz vershinoyu h uzhe viznacheno BFS nomeri to perejti do kroku 4 inakshe do kroku 3 Nehaj x y rebro u yakomu nomer BFS u ne viznacheno Poznachiti ce rebro potovshenoyu sucilnoyu liniyeyu viznachiti BFS u yak chergovij BFS nomer vklyuchiti vershinu u chergu j perejti do kroku 2 Viklyuchiti vershinu h iz chergi Yaksho cherga porozhnya to zupinitis inakshe perejti do kroku 2 Formalnij opis algoritmuNizhche navedeno psevdokod algoritmu dlya vipadku koli neobhidno lishe znajti cilovij vuzol Zalezhno vid konkretnogo zastosuvannya algoritmu mozhe znadobitisya dodatkovij kod sho zabezpechuye zberezhennya potribnoyi informaciyi vidstan vid pochatkovogo vuzla vuzol batko i t in Rekursivna formulyuvannya BFS start node goal node return BFS start node goal node BFS fringe visited goal node if fringe cilovij vuzol ne znajdeno return false if goal node fringe return true return BFS child x fringe child expand x visited visited fringe goal node Iterativna formulyuvannya BFS start node goal node for all nodes i visited i false spochatku spisok vidvidanih vuzliv porozhnij queue push start node pochinayuchi z vuzla dzherela visited start node true while queue empty poki cherga ne porozhnya node queue pop vityagti pershij element v cherzi if node goal node return true pereviriti chi ne ye potochnij vuzol cilovim foreach child in expand node vsi nastupniki potochnogo vuzla if visited child false yaki she ne buli vidvidani queue push child dodati v kinec chergi visited child true i poznachiti yak vidvidani return false cilovij vuzol nedosyazhnij VlastivostiPoznachimo chislo vershin i reber v grafi yak V displaystyle vert V vert i E displaystyle vert E vert vidpovidno Prostorova skladnist Tak yak v pam yati zberigayutsya vsi rozgornuti vuzli prostorova skladnist algoritmu stanovit O V E displaystyle O vert V vert vert E vert Algoritm poshuku z iterativnim pogliblennyam shozhij na poshuk v shirinu tim sho pri kozhnij iteraciyi pered perehodom na nastupnij riven doslidzhuyetsya povnij riven novih vuzliv ale vimagaye znachno menshe pam yati Chasova skladnist Tak yak v girshomu vipadku algoritm vidviduye vsi vuzli grafu pri zberiganni grafu u viglyadi en timchasova skladnist algoritmu stanovit O V E displaystyle O vert V vert vert E vert Povnota Yaksho u kozhnogo vuzla ye kinceve chislo nastupnikiv algoritm ye povnim yaksho rishennya isnuye algoritm poshuku v shirinu jogo znahodit nezalezhno vid togo chi ye graf kincevim Odnak yaksho rishennya ne isnuye na neskinchennomu grafi poshuk ne zakinchuyetsya Optimalnist Yaksho dovzhini reber grafu rivni mizh soboyu poshuk v shirinu ye optimalnim tobto zavzhdi znahodit najkorotshij shlyah V razi zvazhenogo grafu poshuk v shirinu znahodit shlyah sho mistit minimalnu kilkist reber ale ne obov yazkovo najkorotshij Poshuk za kriteriyem vartosti ye uzagalnennyam poshuku v shirinu i optimalnij na zvazhenomu grafi z nevid yemnimi vagami reber Algoritm vidviduye vuzli grafu v poryadku zrostannya vartosti shlyahu z pochatkovogo vuzla i zazvichaj vikoristovuye chergu z prioritetami Dzherela informaciyiTomas Kormen Charlz Lejzerson Ronald Rivest Kliford Stajn 2009 1990 Rozdil 22 2 Poshuk vshir Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 Div takozhLeksikografichnij poshuk u shirinu Spisok algoritmiv Obhid dereva Poshuk v glibinu Poshuk za kriteriyem vartosti Dvonapravlenij poshuk Teoriya grafiv