Utöka första sökningen

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 26 april 2021; kontroller kräver 3 redigeringar .

Bredth-first search ( BFS ) är en av graftraversalmetoderna . Låt grafen ges och det initiala hörnet . Den bredd-första sökalgoritmen korsar systematiskt alla kanter för att "upptäcka" alla hörn som kan nås från , samtidigt som den beräknar avståndet (minsta antal kanter) från till varje nåbar vertex. Algoritmen fungerar för både riktade och oriktade grafer. [ett] $G=(V,E)$ $s$ $G$ $s$ $s$ $s$

Bredth-first search har detta namn eftersom vi i traverseringsprocessen går i bredd, det vill säga innan vi börjar söka efter hörn på avstånd , korsas hörnen på avstånd . $k+1$ $k$

Bredth first search är en av de oinformerade sökalgoritmerna [2] .

Algoritmoperation

Breadth-First Search fungerar genom att gå igenom de individuella nivåerna i grafen , med början vid källnoden . $u$

Betrakta alla kanter som utgår från noden . Om nästa nod är målnoden, avslutas sökningen; annars läggs noden till i kön . Efter att alla kanter som lämnar noden har kontrollerats, tas nästa nod från kön och processen upprepas. $(u,v)$ $u$ $v$ $v$ $u$ $u$

Informell beskrivning

Placera noden från vilken sökningen börjar i den initialt tomma kön.
Hämta en nod från huvudet i kön och markera den som utplacerad. $u$
- Om noden är målnoden, avsluta sedan sökningen med ett "framgångsresultat". $u$
- Annars läggs alla efterföljare till noden som ännu inte är distribuerade och som inte finns i kön i slutet av kön. $u$
Om kön är tom har alla noder i den anslutna grafen skannats, därför är målnoden oåtkomlig från den första; avsluta sökningen med resultatet "misslyckades".
Återgå till punkt 2.

Notera: uppdelningen av hörn i ovikta och ovikta är nödvändig för en godtycklig graf (eftersom den kan ha cykler). För ett träd är denna operation inte nödvändig, eftersom varje vertex endast kommer att väljas en gång.

Formell beskrivning

Nedan finns pseudokoden för algoritmen för det fall då det bara är nödvändigt att hitta målnoden. Beroende på den specifika tillämpningen av algoritmen kan ytterligare kod krävas för att lagra den nödvändiga informationen (avstånd från startnoden, överordnad nod, etc.)

Rekursiv formulering:

BFS( start_node , goal_node ) { return BFS'({ start_node }, ∅, goal_node ); } BFS'( fringe , visited , goal_node ) { if ( fringe == ∅) { // Målnoden hittades inte returnera falskt; } if ( goal_node ∈ fringe ) { return true; } return BFS'({ child | x ∈ frans , child ∈ expand( x )} \ visited , visited ∪ fringe , goal_node ); }

Iterativ formulering:

BFS( start_node , goal_node ) { för (alla noder i) besökte [ i ] = falskt; // initialt är listan över besökta noder tom kö .push( start_node ); // från den besökta källnoden [ start_node ] = sant; while (! kö .empty() ) { // tills kön är tom nod = kö .pop(); // hämta det första elementet i kön if ( nod == goal_node ) { return true; // kontrollera om den aktuella noden är målet } foreach ( barn i expand( node )) { // alla efterföljare av den aktuella noden, ... if (besökt[ barn ] == false) { // ... som ännu inte har besökts ... queue .push ( barn ); // ... lägg till i slutet av kön... besökte [ barn ] = sant; // ... och markera som besökt } } } returnera falskt; // Målnoden går inte att nå }

Pascal implementering :

function BFS ( v : Node ) : Boolean ; börja kö ( v ) ; medan kön inte är tom , börja curr := dequeue () ; om is_goal ( curr ) sedan börja BFS := sant ; avsluta ; slut ; mark ( curr ) ; för nästa i efterföljare ( curr ) gör om det inte är markerat ( nästa ) , börja sedan kö ( nästa ) ; slut ; slut ; BFS := falskt ; slut ;

Egenskaper

Ange antalet hörn och kanter i grafen som respektive . $\vert V\vert$ $\vert E\vert$

Rumslig komplexitet

Eftersom alla expanderade noder är lagrade i minnet är rymdkomplexiteten för algoritmen [2] . $O(\vert V\vert +\vert E\vert )$

Den iterativa fördjupningssökningsalgoritmen liknar bredden-första-sökningen genom att varje iteration undersöker hela nivån av nya noder innan den går vidare till nästa nivå, men kräver betydligt mindre minne.

Tidskomplexitet

Eftersom algoritmen i värsta fall besöker alla noder i grafen, när grafen lagras i form av närliggande listor , är algoritmens tidskomplexitet [2] [3] . $O(\vert V\vert +\vert E\vert )$

Fullständighet

Om varje nod har ett ändligt antal efterföljare är algoritmen komplett: om det finns en lösning hittar algoritmen för bredd-först den, oavsett om grafen är ändlig eller inte. Men om det inte finns någon lösning slutar sökningen inte på den oändliga grafen.

Optimalitet

Om grafens kantlängder är lika, är bredd-först-sökning optimal, det vill säga den hittar alltid den kortaste vägen. I fallet med en viktad graf hittar sökningen med bredd först en bana som innehåller det minsta antalet kanter, men inte nödvändigtvis den kortaste.

Kostnad -först-sökning är en generalisering av bredd-först-sökning och är optimal på en viktad graf med icke-negativa kantvikter. Algoritmen besöker grafens noder i ordning efter ökande kostnad för vägen från startnoden och använder vanligtvis en prioritetskö .

Historik och applikationer

Bredd-första sökning föreslogs formellt av E. F. Moore i samband med att hitta en väg i en labyrint [4] . Lee upptäckte självständigt samma algoritm i samband med PCB-ledningar [5] [6] [7] .

Bredth-First Search kan tillämpas på problem relaterade till grafteori :

Vågalgoritm för att hitta en väg i en labyrint [4]
Vågspårning av kretskort [5]
Hitta anslutningskomponenter i en graf
Hitta den kortaste vägen mellan två noder i en oviktad graf
Sök i tillståndsutrymmet : hitta en lösning på problemet med det minsta antalet drag, om varje tillstånd i systemet kan representeras av en grafvertex, och övergångar från ett tillstånd till ett annat kan representeras av grafkanter [2]
Hitta den kortaste cykeln i en riktad oviktad graf [2]
Hitta alla hörn och kanter som ligger på den kortaste vägen mellan två hörn och [2] $a$ $b$
Utöka sökväg i Ford-Fulkerson-algoritmen ( Edmonds-Karp-algoritmen )

Se även

Djupbegränsad sökning

Anteckningar

↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion och analys. - 3:e uppl. - Williams Publishing House, 2013. - S. 630. - 1328 sid. - ISBN 978-5-8459-1794-2 (ryska). - ISBN 978-0-2620-3384-8 (engelska).
↑ 1 2 3 4 5 6 MAXimal :: algo :: Bred första sökning i en graf och dess tillämpningar Arkiverad 16 september 2013 på Wayback Machine
↑ 1 2 NSTU Strukturer och databearbetningsalgoritmer Breddgrafövergång Arkivkopia daterad 30 december 2012 på Wayback Machine
↑ 1 2 Moore E. F. Den kortaste vägen genom 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 sid. - ( Annals of the Computation Laboratory of Harvard University ; Vol. 30) - ISSN 0073-0750
↑ 1 2 C. Y. Lee (1961), En algoritm för vägförbindelse och dess tillämpningar . IRE Transactions on Electronic Computers , EC-10(3), s. 346–365
↑ Cormen et al , Introduction to Algorithms, 3:e upplagan, sid. 623
↑ Mathematics Stack Exchange Ursprunget till Breadth-First Search-algoritmen

Litteratur

TH Cormen, CE Leiserson, RL Rivest, C. Stein. Introduktion till algoritmer. — 3:e upplagan. - The MIT Press, 2009. - ISBN 978-0-262-03384-8 . . 2:a upplagan översättning: Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Levitin A. V. Kapitel 5. Metod för reduktion av problemstorlek: Bredth-First Search // Algoritmer. Introduktion till utveckling och analys - M. : Williams , 2006. - 576 sid. — ISBN 978-5-8459-0987-9

Länkar

Algoritmer för grafsökning
Oinformerade metoder	Dubbelriktad sökning Strålsökning Lexikografisk bredd första sökning Utöka första sökningen Sök efter kostnadskriterium Djup första sökning Backtracking sökning Sök genom att klättra till toppen Djupbegränsad sökning Djup-första sökning med iterativ fördjupning
Informerade metoder	Alfa beta-klippning Gren och bunden metod Sök efter första bästa matchning A* B* D* Att hitta en övergångspunkt IDA* Rekursiv sökning på den första bästa matchningen SMA*
Genvägar	Vågalgoritm Bellman-Ford algoritm Dijkstras algoritm Johnsons algoritm Levits algoritm Floyd-Warshall algoritm Kantsökning
Minsta spännträd	Boruvkas algoritm Prims algoritm Kruskals algoritm
Övrig	British Museum Algoritm Edmonds algoritm Trädpassering Algoritmen för närmaste granne i problemet med resande säljare