Szerkesztő:BalReka/próbalap
(Még szerkesztés alatt)Szélességi bejárás(keresés)[1][szerkesztés]
A szélességi bejárás egy fa vagy gráf adatszerkezet átjárására vagy keresésére szolgáló algoritmus. A fa gyökerénél (vagy egy gráf tetszőleges csomópontjánál használják, amelyet néha "keresési kulcsnak" hívnak), és feltárja az összes szomszédos csomópontot a jelenlegi mélységben, mielőtt a következő csomópontokra lép, a következő mélységi szintre lépne.
A mélységi bejárás az ellenkező stratégiát használja, amely ehelyett a lehető legalsóbb csomópontig feltárja a gráf ágát, mielőtt más csomópontok visszavonására és kiterjesztésére kényszerülne.
A szélességi bejárást és annak alkalmazását gráfok összekapcsolt összetevőinek megtalálására 1945-ben jegyezte fel Konrad Zuse Ph.D. disszertációjában(elutasított), a Plankalkül programozási nyelvről, de ezt 1972-ig nem tették közzé. Majd 1959-ben Edward F. Moore is felfedezte, aki arra használta, hogy megtalálja a labirintusból való legrövidebb utat, majd C. Y. Lee később vezetékes útválasztási algoritmussá fejlesztette ki (1961-ben publikált).
Pszeudo-kód[szerkesztés]
Bemenet: egy gráfdiagram és a gráf kezdőpontja
Kimenet: Célállapot. A szülő hivatkozások visszavezetik a legrövidebb utat a gyökérhez
1 eljárás szélességi keresés(G, start_v) =
2 legyen Q sor
3 v felcímkézése felfedezettként
4 Q.enqueue(start_v)
5 amíg Q nem üres csináld
6 v := Q.dequeue()
7 ha v a cél akkor
8 return v
9 ciklus v és w közötti minden élnél amelyek a G .adjacentEdges ( v ) részben csináld
10 ha a w nem feltüntetett címkével rendelkezik akkor
11 w felcímkézése felfedezettként
12 w.parent := v
13 Q.enqueue(w)További részletek[szerkesztés]
Ez hasonló a mélységi bejárás nem rekurzív megvalósításához, de két pontban különbözik tőle:
- sor helyett vermet használ, és
- késlelteti annak ellenőrzését, hogy felfedezték-e egy csúcsot, amíg a csúcsot fel nem kérik a veremből, ahelyett, hogy ezt az ellenőrzést elvégeznék a csúcs hozzáadása előtt.
A Q sor tartalmazza azt a határt, amelyen az algoritmus jelenleg keres.
A csomópontok felismerhetők lehetnek úgy, hogy egy készletben, vagy egy-egy csomóponton egy attribútumban tárolják őket, a megvalósítástól függően.
Vegye figyelembe, hogy a csomópont általában felcserélhető a csúcs szóval.
Az egyes csomópontok szülőattribútuma hasznos a csomópontok eléréséhez a legrövidebb úton, például a célcsomóponttól a kezdő csomópontig történő visszahúzással, miután a szélességi bejárás lefutott és az előző csomópontok be vannak állítva.
A szélesség első keresés úgynevezett szélességi fát hoz létre. A következő példában láthatja, hogyan néz ki egy szélességi fa.
Példa[szerkesztés]
Az alábbiakban egy példát láthatunk a szélességi fára, amelyet egy szélességi bejárás futtatásával nyerünk német városokban Frankfurtból indulva:
Elemzés[szerkesztés]
Idő és tér összetettsége[szerkesztés]
Feltöltés alatt
Teljesség[szerkesztés]
Az algoritmusok elemzésében a szélességi bejárásba való bemenetet véges gráfnak kell tekinteni, amelyet kifejezetten szomszédsági listaként vagy hasonló ábrázolásként mutatnak be. A gráf-transzverzális módszereknek a mesterséges intelligenciában történő alkalmazása során azonban a bemenet lehet egy végtelen gráf implicit ábrázolása. Ebben az összefüggésben a keresési módszert teljesnek tekintik, ha garantáltan megtalálja a célállapotot, és létezik. A szélességi bejárás teljes, de az első mélységű keresés nem. Az implicit módon ábrázolt végtelen gráfokra történő alkalmazás esetén a szélességi bejárás végül megtalálja a cél állapotát, de a széleségi bejárás elveszítheti a grafikon olyan részeit, amelyeknek nincs cél állapota, és soha nem térnek vissza.
A szélességi bejárás rendezése[szerkesztés]
Feltöltés alatt
Alkalmazása[szerkesztés]
A szélességi bejárás számos probléma megoldására használható a gráfelméletben, például:
Szemétmásolás másolása, Cheney algoritmusa
Két u és v csomópont közötti legrövidebb út megkeresése, az út hosszát az élek számával mérve (előnye a mélység első kereséshez képest) [10]
(Fordított) Cuthill – McKee hálószámozás
A Ford – Fulkerson módszer a maximális áramlás kiszámításához egy áramlási hálózatban
A bináris fa sorosítása / deserializálása a sorba rendezéshez rendezett sorrendben lehetővé teszi a fa hatékony újrakonstruálását.
Az Aho-Corasick mintázatmegfigyelő hibafunkciójának felépítése.
A grafikon kétoldalúságának tesztelése.
Kapcsolódó szócikkek[szerkesztés]
Mélységi keresés[2]
Irodalom[szerkesztés]
"Graph500 benchmark specification (supercomputer performance evaluation)". Graph500.org, 2010. Archived from the original on 2015-03-26. Retrieved 2015-03-15.
Cormen Thomas H.; et al. (2009). "22.3". Introduction to Algorithms. MIT Press.
Zuse, Konrad (1972), Der Plankalkül (in German), Konrad Zuse Internet Archive. See pp. 96–105 of the linked pdf file (internal numbering 2.47–2.56).
Moore, Edward F. (1959). "The shortest path through a maze". Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. pp. 285–292. As cited by Cormen, Leiserson, Rivest, and Stein.
Skiena, Steven (2008). "Sorting and Searching". The Algorithm Design Manual. Springer. p. 480. Bibcode:2008adm..book.....S. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
Lee, C. Y. (1961). "An Algorithm for Path Connections and Its Applications". IRE Transactions on Electronic Computers. doi:10.1109/TEC.1961.5219222.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "22.2 Breadth-first search". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 531–539. ISBN 0-262-03293-7.
Russell, Stuart; Norvig, Peter (2003) [1995]. Artificial Intelligence: A Modern Approach (2nd ed.). Prentice Hall. ISBN 978-0137903955.
Coppin, B. (2004). Artificial intelligence illuminated. Jones & Bartlett Learning. pp. 79–80.
Aziz, Adnan; Prakash, Amit (2010). "4. Algorithms on Graphs". Algorithms for Interviews. p. 144. ISBN 978-1453792995.
Knuth, Donald E. (1997), The Art of Computer Programming Vol 1. 3rd ed., Boston: Addison-Wesley, ISBN 978-0-201-89683-1
Külső linkek[szerkesztés]
Open Data Structures - Section 12.3.1 - Breadth-First Search, Pat Morin
Simplified Breadth-first Search
Fordítás[szerkesztés]
Ez a szócikk részben vagy egészben a Breadth-first search című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.
- ↑ (2020. április 27.) „Breadth-first search” (angol nyelven). Wikipedia.
- ↑ (2020. május 18.) „Mélységi keresés” (magyar nyelven). Wikipédia.