Šířka první vyhledávání - Breadth-first search - Wikipedia

Šířka první vyhledávání
	Pořadí, ve kterém jsou uzly rozbaleny
Třída	Vyhledávací algoritmus
Datová struktura	Graf
Nejhorší případ výkon
Nejhorší případ složitost prostoru

Animovaný příklad vyhledávání na šířku

Šířka první vyhledávání (BFS) je algoritmus pro procházení nebo hledání strom nebo graf datové struktury. Začíná to na kořen stromu (nebo nějaký libovolný uzel grafu, někdy označovaný jako „vyhledávací klíč“^[1]) a prozkoumá všechny sousední uzly v současné hloubce před přechodem na uzly v další úrovni hloubky.

Používá opačnou strategii hloubkové vyhledávání, který místo toho co nejvíce prozkoumá větev uzlu, než bude nucen ustoupit a rozšířit další uzly.^[2]

BFS a jeho aplikace při hledání připojené komponenty grafů vynalezl v roce 1945 Konrad Zuse, ve svém (zamítnutém) Ph.D. práce na Plankalkül programovací jazyk, ale ten byl publikován až v roce 1972.^[3] To bylo objeveno v roce 1959 Edward F. Moore, který ji použil k nalezení nejkratší cesty z bludiště,^[4]^[5] a později vyvinut C. Y. Lee do a vedení drátu algoritmus (publikováno 1961).^[6]

Pseudo kód

Vstup: Graf $G$ a a počáteční vrchol $vykořenit$ z $G$

Výstup: Stav cíle. The rodič odkazy trasují nejkratší cestu zpět $vykořenit$ ^[7]

 1  postup BFS (G, vykořenit) je 2 nechat Q být štítkem fronty 3 vykořenit jak bylo objeveno 4 Q.zařadit do fronty(vykořenit) 5      zatímco Q není prázdný dělat 6          proti := Q.dequeue () 7 -li proti je cíl pak 8              vrátit se proti 9          pro všechny hrany od proti na w v G.adjacentEdges (proti) dělat10              -li w není označen jako objevený pak11 štítek w jak bylo objeveno12 Q.zařadit do fronty(w)

Více informací

Tato nerekurzivní implementace je podobná nerekurzivní implementaci hloubkové vyhledávání, ale liší se od něj dvěma způsoby:

používá a fronta (First In First Out) místo a zásobník a
kontroluje, zda byl vrchol objeven před zařazením vrcholu, než aby tuto kontrolu odložil, dokud se vrchol nevyřadí z fronty.

Li $G$ je strom, nahrazením fronty tohoto vyhledávacího algoritmu s první šíří hromadou se získá vyhledávací algoritmus s hloubkou první. U obecných grafů by nahrazení zásobníku iterativní implementace vyhledávání do hloubky frontou vytvořilo také algoritmus pro vyhledávání v první šíři, i když poněkud nestandardní.^[8]

The Q fronta obsahuje hranici, po které algoritmus aktuálně prohledává.

Uzly lze označit jako objevené jejich uložením v sadě nebo atributem v každém uzlu, v závislosti na implementaci.

Všimněte si, že slovo uzel je obvykle zaměnitelné se slovem vrchol.

The rodič atribut každého uzlu je užitečný pro přístup k uzlům v nejkratší cestě, například zpětným sledováním od cílového uzlu až k počátečnímu uzlu, jakmile byl spuštěn BFS a byly nastaveny předchůdce uzlů.

Prohledávání na šířku vytváří tzv šíře první strom. Můžete vidět, jak a šíře první strom vypadá v následujícím příkladu.

Příklad

Následuje příklad stromu první šířky získaného spuštěním BFS na Němec města začínající od Frankfurt:

Příklad mapy Jižní Německo s některými spojeními mezi městy

Strom první šířky získaný při spuštění BFS na dané mapě a spuštění v Frankfurt

Analýza

Časová a prostorová složitost

The časová složitost lze vyjádřit jako ${ displaystyle O (| V | + | E |)}$ , protože každý vrchol a každá hrana budou prozkoumány v nejhorším případě. ${ displaystyle | V |}$ je počet vrcholů a ${ displaystyle | E |}$ je počet hran v grafu ${ displaystyle O (| E |)}$ se může lišit ${ displaystyle O (1)}$ a ${ displaystyle O (| V | ^ {2})}$ , v závislosti na tom, jak řídký je vstupní graf.^[9]

Pokud je počet vrcholů v grafu znám předem a další datové struktury se používají k určení, které vrcholy již byly přidány do fronty, složitost prostoru lze vyjádřit jako ${ displaystyle O (| V |)}$ , kde ${ displaystyle | V |}$ je počet vrcholů. To je navíc k požadovanému prostoru pro samotný graf, který se může lišit v závislosti na grafická reprezentace použitý při implementaci algoritmu.

Při práci s grafy, které jsou příliš velké na to, aby je bylo možné explicitně (nebo nekonečně) ukládat, je praktičtější popsat složitost vyhledávání na šířku různými způsoby: najít uzly, které jsou ve vzdálenosti $d$ od počátečního uzlu (měřeno počtem přechodů hran), BFS trvá $Ó (b d + 1)$ čas a paměť, kde $b$ je "větvící faktor "grafu (průměrný vnější stupeň).^[10]^:81

Úplnost

V analýze algoritmů se předpokládá, že vstupem do vyhledávání na šířku je konečný graf, explicitně reprezentovaný jako seznam sousedství, matice sousedství nebo podobné zastoupení. Při aplikaci metod pro procházení grafů v umělá inteligence vstup může být implicitní reprezentace nekonečného grafu. V této souvislosti je vyhledávací metoda popsána jako úplná, pokud je zaručeno nalezení stavu cíle, pokud existuje. Hledání první šířky je dokončeno, ale hledání první hloubky nikoli. Při použití na nekonečné grafy, které jsou implicitně reprezentovány, hledání na šířku nakonec najde stav cíle, ale hledání hloubky na prvním místě se může ztratit v částech grafu, které nemají žádný stav cíle a nikdy se nevrátí.^[11]

Objednávka BFS

Výčet vrcholů grafu je považován za pořadí BFS, pokud je to možný výstup aplikace BFS do tohoto grafu.

Nechat ${ displaystyle G = (V, E)}$ být graf s ${ displaystyle n}$ vrcholy. Odvolej to ${ displaystyle N (v)}$ je soubor sousedů ${ displaystyle v}$ .Pro ${ displaystyle sigma = (v_ {1}, tečky, v_ {m})}$ být seznam odlišných prvků ${ displaystyle V}$ , pro ${ displaystyle v v V setminus {v_ {1}, tečky, v_ {m} }}$ , nechť ${ displaystyle nu _ { sigma} (v)}$ být nejméně ${ displaystyle i}$ takhle ${ displaystyle v_ {i}}$ je soused ${ displaystyle v}$ , pokud takový a ${ displaystyle i}$ existuje a bude ${ displaystyle infty}$ v opačném případě.

Nechat ${ displaystyle sigma = (v_ {1}, tečky, v_ {n})}$ být výčet vrcholů ${ displaystyle V}$ Výčet ${ displaystyle sigma}$ se říká, že je objednávka BFS (se zdrojem ${ displaystyle v_ {1}}$ ) pokud pro všechny ${ displaystyle 1$ , ${ displaystyle v_ {i}}$ je vrchol ${ displaystyle w v V setminus {v_ {1}, tečky, v_ {i-1} }}$ takhle ${ displaystyle nu _ {(v_ {1}, tečky, v_ {i-1})} (w)}$ je minimální. Ekvivalentně ${ displaystyle sigma}$ je objednávka BFS, pokud pro všechny ${ Displaystyle 1 leq já$ s ${ displaystyle v_ {i} v N (v_ {k}) setminus N (v_ {j})}$ existuje soused ${ displaystyle v_ {m}}$ z ${ displaystyle v_ {j}}$ takhle ${ displaystyle m$ .

Aplikace

Vyhledávání na šířku lze použít k řešení mnoha problémů v teorii grafů, například:

Kopírování odvoz odpadu, Cheneyho algoritmus
Nalezení nejkratší cesta mezi dvěma uzly u a proti, s délkou dráhy měřenou počtem hran (výhoda oproti hloubkové vyhledávání )^[12]
(Zpět) Cuthill – McKee číslování ok
Ford-Fulkersonova metoda pro výpočet maximální průtok v toková síť
Serializace / deserializace binárního stromu vs serializace v seřazeném pořadí umožňuje efektivní rekonstrukci stromu.
Stavba selhání funkce z Aho-Corasick vzorovač.
Testování bipartitita grafu.

Viz také

Reference

^ „Specifikace benchmarku Graph500 (hodnocení výkonu superpočítače)“. Graph500.org, 2010. Archivovány od originál dne 26.03.2015. Citováno 2015-03-15.
^ Cormen Thomas H .; et al. (2009). „22,3“. Úvod do algoritmů. MIT Stiskněte.
^ Zuse, Konrad (1972), Der Plankalkül (v němčině), Internetový archiv Konrada Zuse. Viz str. 96–105 propojeného souboru PDF (interní číslování 2,47–2,56).
^ Moore, Edward F. (1959). "Nejkratší cesta bludištěm". Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. str. 285–292. Jak uvádí Cormen, Leiserson, Rivest a Stein.
^ Skiena, Steven (2008). Msgstr "Třídění a vyhledávání". Příručka pro návrh algoritmu. Springer. str. 480. Bibcode:2008adm..book ..... S. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
^ Lee, C. Y. (1961). Msgstr "Algoritmus pro připojení trasy a jeho aplikace". Transakce IRE na elektronických počítačích. doi:10.1109 / TEC.1961.5219222.
^ Cormen, Thomas H. „22.2 Šířka první vyhledávání“. Úvod do algoritmů. ISBN 978-81-203-4007-7. OCLC 1006880283.
^ „Stack-based graph traversal ≠ depth first search“. 11011110.github.io. Citováno 2020-06-10.
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „22.2 Šířka první vyhledávání“. Úvod do algoritmů (2. vyd.). MIT Press a McGraw-Hill. 531–539. ISBN 0-262-03293-7.
^ Russell, Stuart; Norvig, Peter (2003) [1995]. Umělá inteligence: moderní přístup (2. vyd.). Prentice Hall. ISBN 978-0137903955.
^ Coppin, B. (2004). Umělá inteligence osvětlena. Jones & Bartlett Learning. str. 79–80.
^ Aziz, Adnan; Prakash, Amit (2010). "4. Algoritmy na grafech". Algoritmy pro rozhovory. str. 144. ISBN 978-1453792995.

Knuth, Donald E. (1997), The Art of Computer Programming Vol 1. 3. ed., Boston: Addison-Wesley, ISBN 978-0-201-89683-1

externí odkazy

[1] ^ „Specifikace benchmarku Graph500 (hodnocení výkonu superpočítače)“. Graph500.org, 2010. Archivovány od originál dne 26.03.2015. Citováno 2015-03-15.

[2] ^ Cormen Thomas H .; et al. (2009). „22,3“. Úvod do algoritmů. MIT Stiskněte.

[:0-3] ^ Zuse, Konrad (1972), Der Plankalkül (v němčině), Internetový archiv Konrada Zuse. Viz str. 96–105 propojeného souboru PDF (interní číslování 2,47–2,56).

[4] Moore, Edward F. (1959). "Nejkratší cesta bludištěm". Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. str. 285–292. Jak uvádí Cormen, Leiserson, Rivest a Stein.

[skiena-5] Skiena, Steven (2008). Msgstr "Třídění a vyhledávání". Příručka pro návrh algoritmu. Springer. str. 480. Bibcode:2008adm..book ..... S. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.

[6] ^ Lee, C. Y. (1961). Msgstr "Algoritmus pro připojení trasy a jeho aplikace". Transakce IRE na elektronických počítačích. doi:10.1109 / TEC.1961.5219222.

[7] ^ Cormen, Thomas H. „22.2 Šířka první vyhledávání“. Úvod do algoritmů. ISBN 978-81-203-4007-7. OCLC 1006880283.

[8] ^ „Stack-based graph traversal ≠ depth first search“. 11011110.github.io. Citováno 2020-06-10.

[clrs-9] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „22.2 Šířka první vyhledávání“. Úvod do algoritmů (2. vyd.). MIT Press a McGraw-Hill. 531–539. ISBN 0-262-03293-7.

[10] ^ Russell, Stuart; Norvig, Peter (2003) [1995]. Umělá inteligence: moderní přístup (2. vyd.). Prentice Hall. ISBN 978-0137903955.

[coppin-11] ^ Coppin, B. (2004). Umělá inteligence osvětlena. Jones & Bartlett Learning. str. 79–80.

[12] ^ Aziz, Adnan; Prakash, Amit (2010). "4. Algoritmy na grafech". Algoritmy pro rozhovory. str. 144. ISBN 978-1453792995.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Datové struktury a algoritmy
Datové struktury	Pole Asociativní pole Binární vyhledávací strom Fenwick Tree Graf Tabulka hash Halda Spojový seznam Fronta Segmentový strom Zásobník Tětiva Strom Trie
Algoritmy	Backtracking Binární vyhledávání Šířka první vyhledávání Hledání do hloubky Rozděl a panuj Dynamické programování Složit Chamtivý Minimax Rekurze Třídění Streamování Sweep Line Topologické třídění