Šířka -první hledání - Breadth-first search

Šířka-první hledání

Pořadí, ve kterém jsou uzly rozbaleny
Třída	Algoritmus vyhledávání
Datová struktura	Graf
Nejhorší výkon	${\ Displaystyle O (| V |+| E |) = O (b^{d})}$
Nejhorší prostorová složitost	${\ Displaystyle O (| V |) = O (b^{d})}$

Animovaný příklad širokého vyhledávání. Černá: prozkoumána, šedá: ve frontě k pozdějšímu prozkoumání

Horní část stromu hry Tic-tac-toe

Breadth-first search ( BFS ) je algoritmus pro vyhledávání stromové datové struktury pro uzel, který splňuje danou vlastnost. Začíná u kořene stromu a prozkoumává všechny uzly v současné hloubce, než přejde k uzlům na další úrovni hloubky. Ke sledování podřízených uzlů, se kterými se setkalo, ale ještě nebyly prozkoumány, je zapotřebí další paměť, obvykle fronta .

Například v šachové koncovce může šachový engine postavit herní strom z aktuální pozice aplikováním všech možných tahů a použít hledání od šířky k nalezení pozice vítězství pro bílého. Implicitní stromy (jako jsou stromy zvěře nebo jiné stromy řešící problémy) mohou mít neomezenou velikost; při hledání do šířky je zaručeno nalezení uzlu řešení, pokud existuje.

Naproti tomu vyhledávání (prosté) hloubky nejprve , které prozkoumává větev uzlu co nejdále před zpětným sledováním a rozšiřováním dalších uzlů, se může ztratit v nekonečné větvi a nikdy se nedostane do uzlu řešení. Iterativní prohloubení hloubkového vyhledávání nejprve vyhne se druhé nevýhodě za cenu zkoumání vrcholných částí stromu znovu a znovu. Na druhou stranu oba algoritmy hloubky nejprve vycházejí bez další paměti.

Prohledávání nejprve do šířky lze zobecnit na grafy , když je výslovně uveden počáteční uzel (někdy označovaný jako 'klíč vyhledávání') a jsou přijata předběžná opatření proti následování vrcholu dvakrát.

BFS a jeho aplikaci při hledání propojených komponent grafů vynalezl v roce 1945 Konrad Zuse ve svém (odmítnutém) Ph.D. práce o programovacím jazyce Plankalkül , ale ta byla vydána až v roce 1972. V roce 1959 ji znovu objevil Edward F. Moore , který ji použil k nalezení nejkratší cesty z bludiště, a později ji CY Lee vyvinul do algoritmu směrování drátu (publikováno 1961).

Pseudo kód

Vstup : Graf G a výchozí vrchol kořen z G

Výstup : Stav cíle. Na mateřské odkazy vystopovat nejkratší cestu zpět do kořenového adresáře

 1  procedure BFS(G, root) is
 2      let Q be a queue
 3      label root as explored
 4      Q.enqueue(root)
 5      while Q is not empty do
 6          v := Q.dequeue()
 7          if v is the goal then
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10              if w is not labeled as explored then
11                  label w as explored
12                  Q.enqueue(w)

Více informací

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

1. používá frontu (First In First Out) namísto zásobníku a
2. kontroluje, zda byl vrchol prozkoumán před zařazením vrcholu, místo aby tuto kontrolu oddaloval, dokud se vrchol nevyřadí z fronty.

Pokud G je strom , nahrazení fronty tohoto vyhledávacího algoritmu šířky prvního zásobníkem poskytne vyhledávací algoritmus hloubky první. V případě obecných grafů by nahrazení hromady iterativní implementace hloubkového vyhledávání první frontou také vedlo k vyhledání algoritmu šířky první, i když poněkud nestandardního.

Q fronta obsahuje hranice, podél níž je algoritmus je v současné době vyhledávání.

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

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

Rodič atributem každý uzel je užitečná pro přístup k uzly v nejkratší cestou, například ústupkem od cílového uzlu až do výchozího uzlu, jakmile BFS je běh, a předchůdci uzly byly nastaveny.

Hledání v první šířce vytváří takzvaný první strom šířky . V následujícím příkladu můžete vidět, jak vypadá první strom šířky .

Příklad

Následuje příklad šířky prvního stromu získaného spuštěním BFS v německých městech od Frankfurtu :

Příklad mapy jižního Německa s určitým spojením mezi městy

Široce první strom získaný spuštěním BFS na dané mapě a startem ve Frankfurtu

Analýza

Časová a prostorová složitost

Složitost času lze vyjádřit , neboť každý vrchol a každá hrana bude prozkoumána v nejhorším případě. je počet vrcholů a počet hran v grafu. Všimněte si, že se může lišit mezi a v závislosti na tom, jak řídký je vstupní graf. ${\ displaystyle O (| V |+| E |)}$${\ displaystyle | V |}$${\ displaystyle | E |}$${\ displaystyle O (| E |)}$${\ displaystyle O (1)}$${\ displaystyle O (| V |^{2})}$

Když je počet vrcholů v grafu znám dopředu a k určení, které vrcholy již byly přidány do fronty, jsou použity další datové struktury, může být složitost prostoru vyjádřena jako , kde je počet vrcholů. To je navíc k prostoru potřebnému pro samotný graf, který se může lišit v závislosti na grafickém znázornění použitém implementací algoritmu. ${\ displaystyle O (| V |)}$${\ displaystyle | V |}$

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 hledání šířky nejprve různými způsoby: najít uzly, které jsou ve vzdálenosti d od počátečního uzlu (měřeno v počtu pohybů hran), BFS trvá O ( b ^{d + 1} ) času a paměti, kde b je „ faktor rozvětvení “ grafu (průměrný stupeň mimo).

Úplnost

Při analýze algoritmů, vstup do prohledávání do šířky se předpokládá, že konečný graf, výslovně reprezentované jako seznam přilehlosti , matice přilehlosti , nebo podobné reprezentace. Při aplikaci metod procházení grafů v umělé inteligenci však může být vstup implicitní reprezentací nekonečného grafu. V této souvislosti je metoda hledání popsána jako úplná, pokud je zaručeno, že najde stav cíle, pokud existuje. Hledání do šířky je úplné, ale hledání do hloubky není. Když je aplikováno na nekonečné grafy reprezentované implicitně, hledání šířky nejprve najde cílový stav, ale hloubkové první hledání se může ztratit v částech grafu, které nemají žádný cílový stav a nikdy se nevrátí.

Objednávka BFS

Výčet vrcholů grafu je považován za uspořádání BFS, pokud je to možný výstup aplikace BFS na tento graf.

Nechť je graf s vrcholy. Připomeňme si, že toto je soubor sousedů . Nechť je seznam zřetelných prvků pro , pro , ať je nejmenší takový, který je sousedem , pokud takový existuje, a je tomu jinak. ${\ displaystyle G = (V, E)}$${\ displaystyle n}$${\ Displaystyle N (v)}$${\ displaystyle v}$${\ Displaystyle \ sigma = (v_ {1}, \ tečky, v_ {m})}$${\ displaystyle V}$${\ Displaystyle v \ v V \ setminus \ {v_ {1}, \ tečky, v_ {m} \}}$${\ displaystyle \ nu _ {\ sigma} (v)}$${\ displaystyle i}$${\ displaystyle v_ {i}}$${\ displaystyle v}$${\ displaystyle i}$${\ displaystyle \ infty}$

Nechť je výčet vrcholů . Výčet je řekl, aby byl BFS uspořádání (s zdroj ) v případě, pro všechny , je vrchol taková, že je minimální. Ekvivalentně, je BFS uspořádání v případě, pro všechny, s existuje souseda z taková, že . ${\ Displaystyle \ sigma = (v_ {1}, \ tečky, v_ {n})}$${\ displaystyle V}$${\ Displaystyle \ sigma}$${\ displaystyle v_ {1}}$${\ Displaystyle 1 <i \ leq n}$${\ displaystyle v_ {i}}$${\ Displaystyle w \ in V \ setminus \ {v_ {1}, \ tečky, v_ {i-1} \}}$${\ Displaystyle \ nu _ {(v_ {1}, \ tečky, v_ {i-1})} (w)}$${\ Displaystyle \ sigma}$${\ Displaystyle 1 \ leq i <j <k \ leq n}$${\ Displaystyle v_ {i} \ v N (v_ {k}) \ setminus N (v_ {j})}$${\ displaystyle v_ {m}}$${\ displaystyle v_ {j}}$${\ Displaystyle m <i}$

Aplikace

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

• Kopírování smetí , Cheneyho algoritmus
• Nalezení nejkratší cesty mezi dvěma uzly u a v , s délkou dráhy měřenou počtem hran (výhoda oproti hledání nejprve hloubkou )
• (Reverse) Cuthill – McKee očíslování ok
• Ford – Fulkersonova metoda pro výpočet maximálního průtoku v tokové síti
• Serializace/deserializace binárního stromu vs serializace v seřazeném pořadí umožňuje efektivní opětovné sestavení stromu.
• Výstavba funkce selhání na Aho-Corasick vzor dohazovač.
• Testování dvojstrannosti grafu .
• Implementace paralelních algoritmů pro výpočet tranzitivního uzavření grafu.

Viz také

• Hledání do hloubky
• Iterativní prohlubování hloubky-první hledání
• Úrovňová struktura
• Lexikografické vyhledávání do šířky
• Paralelní hledání do šířky

Reference

externí odkazy

• Otevřené datové struktury - Oddíl 12.3.1 - Hledání do šířky , Pat Morin
• Zjednodušené vyhledávání nejprve do šířky