Šířka první hledání

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. dubna 2021; kontroly vyžadují 3 úpravy .

Breadth-first search ( BFS ) je jednou z metod procházení grafů .  Nechť je dán graf a počáteční vrchol . Algoritmus prohledávání do šířky systematicky prochází všechny hrany , aby „objevil“ všechny vrcholy dosažitelné z , přičemž vypočítává vzdálenost (minimální počet hran) od každého dosažitelného vrcholu. Algoritmus funguje pro řízené i neorientované grafy. [jeden]

Hledání do šířky má tento název, protože v procesu procházení jdeme do šířky, to znamená, že než začneme hledat vrcholy na dálku , projdou se vrcholy na dálku .

Prohledávání šířky je jedním z neinformovaných vyhledávacích algoritmů [2] .

Operace algoritmu

Breadth-First Search funguje tak, že procházíte jednotlivými úrovněmi grafu , počínaje zdrojovým uzlem .

Zvažte všechny hrany vycházející z uzlu . Pokud je další uzel cílovým uzlem, pak hledání skončí; jinak je uzel přidán do fronty . Po kontrole všech hran opouštějících uzel je z fronty odebrán další uzel a proces se opakuje.

Neformální popis

  1. Umístěte uzel, ze kterého vyhledávání začíná, do původně prázdné fronty.
  2. Získejte uzel z hlavy fronty a označte jej jako nasazený.
    • Pokud je uzel cílovým uzlem, ukončete hledání s výsledkem „úspěch“.
    • Jinak jsou všichni následníci uzlu , kteří ještě nejsou nasazeni a nejsou ve frontě, přidáni na konec fronty.
  3. Pokud je fronta prázdná, pak byly naskenovány všechny uzly připojeného grafu , proto je cílový uzel nedosažitelný od počátečního; ukončete hledání s výsledkem "neúspěšné".
  4. Vraťte se k bodu 2.

Poznámka: rozdělení vrcholů na nezavinuté a nerozložené je nutné pro libovolný graf (protože může mít cykly). U stromu tato operace není nutná, protože každý vrchol bude vybrán pouze jednou.

Formální popis

Níže je pseudokód algoritmu pro případ, kdy je potřeba pouze najít cílový uzel. V závislosti na konkrétní aplikaci algoritmu může být vyžadován další kód pro uložení nezbytných informací (vzdálenost od počátečního uzlu, nadřazeného uzlu atd.)

Rekurzivní formulace:

BFS( počáteční_uzel , cíl_uzel ) { return BFS'({ počáteční_uzel }, ∅, uzel_cíle ); } BFS'( okraj , navštíveno , uzel_cíle ) { if ( okraj == ∅) { // Cílový uzel nenalezen vrátit false; } if ( cílový_uzel ∈ okraj ) { return true; } return BFS'({ dítě | x ∈ okraj , dítě ∈ expand( x )} \ navštíveno , navštíveno ∪ okraj , uzel_cíle ); }

Iterativní formulace:

BFS( počáteční_uzel , cílový_uzel ) { pro (všechny uzly i) navštívené [ i ] = false; // zpočátku je seznam navštívených uzlů prázdný fronta .push( start_uzel ); // počínaje od navštíveného zdrojového uzlu [ start_node ] = true; while (! fronta .empty() ) { // dokud není fronta prázdná uzel = fronta .pop(); // vyzvednutí prvního prvku ve frontě if ( node == cíl_uzel ) { return true; // kontrola, zda je aktuální uzel cíl } foreach ( child in expand( node )) { // všichni následníci aktuálního uzlu, ... if (visited[ child ] == false) { // ... které ještě nebyly navštíveny ... fronta .push ( dítě ) ; // ... přidat na konec fronty... navštíveno [ dítě ] = true; // ... a označit jako navštívené } } } vrátit false; // Cílový uzel je nedostupný }

Implementace Pascalu :

funkce BFS ( v : Node ) : Boolean ; begin enqueue ( v ) ; zatímco fronta není prázdná do begin curr : = dequeue () ; if is_goal ( curr ) then begin BFS := true ; výstup ; konec ; značka ( curr ) ; for next in následníky ( curr ) do if not označené ( next ) then begin enqueue ( next ) ; konec ; konec ; BFS := false ; konec ;

Vlastnosti

Označte počet vrcholů a hran v grafu jako resp .

Prostorová složitost

Protože všechny expandované uzly jsou uloženy v paměti, prostorová složitost algoritmu je [2] .

Algoritmus iterativního prohlubování je podobný prohledávání do šířky v tom, že každá iterace prozkoumá celou úroveň nových uzlů před přechodem na další úroveň, ale vyžaduje podstatně méně paměti.

Časová složitost

Protože v nejhorším případě algoritmus navštíví všechny uzly grafu, při ukládání grafu ve formě seznamů sousedství je časová složitost algoritmu [2] [3] .

Úplnost

Pokud má každý uzel konečný počet následníků, je algoritmus kompletní: pokud řešení existuje, algoritmus prohledávání do šířky ho najde, ať už je graf konečný nebo ne. Pokud však řešení neexistuje, hledání nekončí na nekonečném grafu.

Optimality

Pokud jsou délky hran grafu stejné, je optimální prohledávání do šířky, to znamená, že vždy najde nejkratší cestu. V případě váženého grafu najde prohledávání do šířky cestu obsahující minimální počet hran, ale nemusí nutně tu nejkratší.

Cost -first search je zobecněním prohledávání do šířky a je optimální na váženém grafu s nezápornými váhami hran. Algoritmus navštěvuje uzly grafu v pořadí zvyšujících se nákladů na cestu z počátečního uzlu a obvykle používá prioritní frontu .

Historie a aplikace

Hledání do šířky formálně navrhl E. F. Moore v kontextu hledání cesty v bludišti [4] . Lee nezávisle objevil stejný algoritmus v kontextu zapojení PCB [5] [6] [7] .

Breadth-First Search lze použít na problémy související s teorií grafů :

Viz také

Poznámky

  1. ↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmy: konstrukce a analýza. - 3. vyd. - Williams Publishing House, 2013. - S. 630. - 1328 s. - ISBN 978-5-8459-1794-2 (ruština). - ISBN 978-0-2620-3384-8 (anglicky).
  2. ↑ 1 2 3 4 5 6 MAXimal :: algo :: První prohledávání šířky v grafu a jeho aplikace Archivováno 16. září 2013 na Wayback Machine
  3. ↑ 1 2 Struktury NSTU a algoritmy zpracování dat Průchod šířkovým grafem Archivní kopie ze dne 30. prosince 2012 na Wayback Machine
  4. ↑ 1 2 Moore E. F. The shortest path through a blude  // Proceedings of a International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2.–5 April 1957) – Harvard University Press , 1959. – Vol. 2. - S. 285-292. — 345 s. - ( Annals of the Computation Laboratory of Harvard University ; Vol. 30) - ISSN 0073-0750
  5. ↑ 1 2 C. Y. Lee (1961), Algorithm for path connection and its applications . IRE Transactions on Electronic Computers , EC-10(3), str. 346–365
  6. ↑ Cormen a kol ., Úvod do algoritmů, 3. vydání, str. 623
  7. ↑ Mathematics Stack Exchange Původ algoritmu Breadth-First Search

Literatura

  • TH Cormen, CE Leiserson, RL Rivest, C. Stein. Úvod do algoritmů. — 3. vydání. - The MIT Press, 2009. - ISBN 978-0-262-03384-8 . . 2. vydání překlad: Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmy: konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
  • Levitin A. V. Kapitola 5. Metoda redukce velikosti problému: Breadth-First Search // Algorithms. Úvod do vývoje a analýzy - M .: Williams , 2006. - 576 s. — ISBN 978-5-8459-0987-9

Odkazy

 Algoritmy pro vyhledávání grafů
Neinformované metody
Informované metody
Zkratky
Minimální kostra
jiný