Bredde først søgning

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 26. april 2021; checks kræver 3 redigeringer .

Breadth -first search ( BFS ) er en af ​​grafgennemgangsmetoderne .  Lad grafen være givet og begyndelsespunktet . Bredde-først søgealgoritmen krydser systematisk alle kanter for at "opdage" alle hjørner, der kan nås fra , mens den beregner afstanden (minimum antal kanter) fra til hver nåbar top. Algoritmen fungerer for både rettede og urettede grafer. [en]

Bredth-first-søgning har dette navn, fordi vi i traversalprocessen går i bredden, det vil sige, at før man begynder at søge efter hjørner på afstand , krydses hjørnerne på afstand .

Bredth first search er en af ​​de uinformerede søgealgoritmer [2] .

Algoritmeoperation

Breadth-First Search fungerer ved at gå gennem de individuelle niveauer i grafen , startende ved kildenoden .

Overvej alle kanter udgående fra node . Hvis den næste knude er målknuden, slutter søgningen; ellers føjes noden til køen . Efter at alle de kanter, der forlader noden, er kontrolleret, tages den næste node fra køen , og processen gentages.

Uformel beskrivelse

  1. Sæt den node, hvorfra søgningen begynder, i den oprindeligt tomme kø.
  2. Hent en node fra hovedet af køen , og marker den som implementeret.
    • Hvis noden er målknuden, så afslut søgningen med et "succes" resultat.
    • Ellers tilføjes alle efterfølgere af noden , som endnu ikke er implementeret og ikke er i køen, til slutningen af ​​køen.
  3. Hvis køen er tom, så er alle knudepunkter i den tilsluttede graf blevet scannet, derfor er målknuden ikke tilgængelig fra den oprindelige; afslutte søgningen med resultatet "mislykkedes".
  4. Tilbage til punkt 2.

Bemærk: opdelingen af ​​hjørner i udfoldede og ikke udfoldede er nødvendig for en vilkårlig graf (da den kan have cyklusser). For et træ er denne operation ikke nødvendig, da hvert toppunkt kun vil blive valgt én gang.

Formel beskrivelse

Nedenfor er pseudokoden for algoritmen for det tilfælde, hvor det kun er nødvendigt at finde målknuden. Afhængigt af den specifikke anvendelse af algoritmen kan der være behov for yderligere kode for at gemme den nødvendige information (afstand fra startknudepunktet, overordnet knude osv.)

Rekursiv formulering:

BFS( start_node , goal_node ) { return BFS'({ start_node }, ∅, goal_node ); } BFS'( fringe , visited , goal_node ) { if ( fringe == ∅) { // Målknudepunktet blev ikke fundet returnere falsk; } if ( mål_node ∈ udkant ) { return true; } return BFS'({ barn | x ∈ rand , barn ∈ expand( x )} \ besøgt , besøgt ∪ rand , målknude ); }

Iterativ formulering:

BFS( start_node , goal_node ) { for (alle noder i) besøgte [ i ] = falsk; // indledningsvis er listen over besøgte noder tom kø .push( start_node ); // startende fra kildenoden besøgte [ start_node ] = sand; while (! kø .empty() ) { // indtil køen er tom node = kø .pop(); // hent det første element i køen if ( node == goal_node ) { return true; // tjek om den aktuelle node er målet } foreach ( child in expand( node )) { // alle efterfølgere af den aktuelle node, ... if (visited[ child ] == false) { // ... der endnu ikke er besøgt ... kø .push ( barn ); // ... tilføje til slutningen af ​​køen... besøgt [ barn ] = sand; // ... og marker som besøgt } } } returnere falsk; // Målknudepunktet er ikke tilgængeligt }

Pascal implementering :

funktion BFS ( v : Node ) : Boolean ; start kø ( v ) ; mens køen ikke er tom , skal du begynde curr := dequeue () ; hvis is_goal ( curr ) så start BFS := sand ; udgang ; ende ; mærke ( curr ) ; for næste i efterfølgere ( curr ) gør hvis ikke markeret ( næste ), så start køen ( næste ) ; ende ; ende ; BFS := falsk ; ende ;

Egenskaber

Angiv antallet af hjørner og kanter i grafen som hhv .

Rumlig kompleksitet

Da alle udvidede noder er lagret i hukommelsen, er rumkompleksiteten af ​​algoritmen [2] .

Den iterative uddybningssøgningsalgoritme ligner bredde-først-søgning, idet hver iteration undersøger hele niveauet af nye noder, før det går videre til næste niveau, men kræver væsentligt mindre hukommelse.

Tidskompleksitet

Da algoritmen i værste fald besøger alle grafens noder , er algoritmens tidskompleksitet [2] [3] ved lagring af grafen i form af tilgrænsende lister .

Fuldstændighed

Hvis hver knude har et begrænset antal efterfølgere, er algoritmen komplet: Hvis der findes en løsning, finder bredde-første søgealgoritmen den, uanset om grafen er begrænset eller ej. Men hvis der ikke er nogen løsning, slutter søgningen ikke på den uendelige graf.

Optimalitet

Hvis grafens kantlængder er ens, er bredde-først-søgning optimal, det vil sige, at den altid finder den korteste vej. I tilfælde af en vægtet graf finder bredde-først-søgning en sti, der indeholder det mindste antal kanter, men ikke nødvendigvis den korteste.

Cost -first search er en generalisering af bredde-først søgning og er optimal på en vægtet graf med ikke-negative kantvægte. Algoritmen besøger grafens noder i rækkefølge efter stigende omkostninger for stien fra startknuden og bruger normalt en prioritetskø .

Historie og applikationer

Bredde-første søgning blev formelt foreslået af E. F. Moore i forbindelse med at finde en sti i en labyrint [4] . Lee opdagede uafhængigt den samme algoritme i forbindelse med PCB-ledninger [5] [6] [7] .

Breadth-First Search kan anvendes på problemer relateret til grafteori :

Se også

Noter

  1. ↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion og analyse. - 3. udg. - Williams Publishing House, 2013. - S. 630. - 1328 s. - ISBN 978-5-8459-1794-2 (russisk). - ISBN 978-0-2620-3384-8 (engelsk).
  2. ↑ 1 2 3 4 5 6 MAXimal :: algo :: Bredde første søgning i en graf og dens applikationer Arkiveret 16. september 2013 på Wayback Machine
  3. ↑ 1 2 NSTU -strukturer og databehandlingsalgoritmer Breddegrafgennemgang Arkivkopi dateret 30. december 2012 på Wayback Machine
  4. ↑ 1 2 Moore E. F. Den korteste vej gennem en labyrint  // Proceedings of an 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 ; bind 30) - ISSN 0073-0750
  5. ↑ 1 2 C. Y. Lee (1961), En algoritme for stiforbindelse og dens applikationer . IRE Transactions on Electronic Computers , EC-10(3), pp. 346-365
  6. ↑ Cormen et al ., Introduction to Algorithms, 3. udgave, s. 623
  7. ↑ Mathematics Stack Exchange Oprindelsen af ​​Breadth-First Search-algoritmen

Litteratur

  • TH Cormen, CE Leiserson, RL Rivest, C. Stein. Introduktion til algoritmer. — 3. udgave. - The MIT Press, 2009. - ISBN 978-0-262-03384-8 . . 2. udgave oversættelse: Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
  • Levitin A. V. Kapitel 5. Metode til reduktion af problemstørrelse: Breadth-First Search // Algoritmer. Introduktion til udvikling og analyse - M. : Williams , 2006. - 576 s. — ISBN 978-5-8459-0987-9

Links

 Algoritmer til grafsøgning
Uoplyste metoder
Informerede metoder
Genveje
Minimumspændende træ
Andet