Mélységi keresés

A mélységi keresés vagy mélységi bejárás egy keresőalgoritmus, amivel bejárhatunk vagy kereshetünk fa vagy gráf adatszerkezetben. Az algoritmus a gyökér csomópontból indul (gráf esetén tetszőleges csomópontot nevezünk ki gyökér csomópontnak), keresési fát balra lefelé tartva járja be. Ha nem tud lefelé menni tovább, visszalép a legalsó elágazásig és a következő ágat választja. Visszalépéskor a sikertelen ág állapotait ejt

A mélységi keresés egy változatát a 19. században a francia matematikus, Charles Pierre Trémaux a labirintusok megoldásának stratégiájaként vizsgálta meg.

Tulajdonságok

A mélységi keresés idő- és térbeli elemzése alkalmazásterületétől függően eltérő. Az elméleti számítástechnikában a mélységi keresést általában egy teljes gráf bejárására használják, és $O(|V|+|E|)$ időbe telik,^[1] a gráf méretében lineáris. Ezekben az alkalmazásokban $O(|V|)$ helyet is igénybe vesz, a legrosszabb esetben annyi csúcsot kell tárolni amennyi az aktuális ösvényen már meglátogatott státuszban szerepel. Így ebben a beállításban az idő- és helyhatárok megegyeznek a szélességi kereséssel, hogy melyik algoritmust válasszuk kevésbé függ azok komplexitásától, és inkább a csúcsrendezés különböző tulajdonságaitól, amelyeket a két algoritmus előállít.

A mélységi keresés adott területeken történő alkalmazásához, például a megoldások kereséséhez a mesterséges intelligenciában vagy a webes feltérképezéshez, a bejárandó gráf gyakran vagy túl nagy ahhoz, hogy teljes egészében bejárhassa, vagy végtelen (a mélységi keresésnél előfordulhat, hogy az algoritmus nem fejeződik be). Ilyen esetekben a keresést csak korlátozott mélységben hajtják végre; a korlátozott erőforrások, például a memória vagy a lemezterület miatt, általában nem használnak adatszerkezeteket az összes korábban meglátogatott csúcs készletének nyomon követésére. Ha a keresést korlátozott mélységre hajtják végre, akkor az idő továbbra is lineáris a kibővített csúcsok és élek száma szempontjából (bár ez a szám nem egyezik meg a teljes grafikon méretével, mivel egyes csúcsokat egyszerre többször is meg lehet látogatni, míg másokat egyáltalán nem), de a mélységi keresés ennek a variánsnak a térbeli bonyolultsága csak a mélységhatárral arányos, és ennek eredményeként sokkal kisebb helyre van szükség, mint az azonos szélességű, ugyanazon a mélységben történő kereséshez, a szélességi kereséssel párhuzamban. Ilyen alkalmazások esetén a mélységi keresés gyakrabban alkalmazza aheurisztikus módszereket a valószínűbb ágak kiválasztása érdekében. Ha a megfelelő mélységkorlát előre nem ismert, akkor az iteratív mélyítést a mélységi keresés ismételten, növekvő határok sorozatával alkalmazza. A mesterséges intelligencia elemzési módjában, egynél nagyobb elágazási tényezővel, az iteratív mélyítés csak egy állandó tényezővel növeli a futási időt abban az esetben, ha a szint mélységének geometriai növekedése miatt a helyes mélységhatár ismert.

A mélységi keresés felhasználható gráfcsomópontok mintájának gyűjtésére is. Ugyanakkor a hiányos mélységi keresés, hasonlóan a hiányos szélességi kereséshez, magas fokú csomópontok felé van torzítva.

Példa

Animált példa a mélységi keresésre

A következő grafikonhoz:

az A-tól kezdődő mélységi keresés, ha feltételezzük, hogy a megjelenített grafikon bal széleit a jobb szélek előtt választottuk meg, és ha a keresés a korábban meglátogatott csomópontokra emlékszik, és nem fogja megismételni őket (mivel ez egy kis gráf), akkor meglátogatja a csomópontokat a következő sorrendben: A, B, D, F, E, C, G. A keresés során áthaladó élek egy Trémaux fát alkotnak, amely szerkezet alkalmazása lényeges a gráfelméletben. Ugyanezen keresés végrehajtása anélkül, hogy a korábban meglátogatott csomópontokra emlékezne, A, B, D, F, E, A, B, D, F, E stb. Körkörösen fogja bejárni az A, B, D, F, E ágat, és soha nem éri el a C vagy G-t.

Az Iteratív mélyítés az egyik módszer a végtelen ciklus elkerülésére, és minden csomópont elérésére.

A mélységi keresés eredménye

A négyféle élt határoz meg egy feszítőfa

A grafikon első mélységű keresésének kényelmes leírása a keresés során elért csúcsok feszítő fája alapján történik. Ezen feszítő fa alapján az eredeti gráf éleit három osztályra lehet csoportosítani: előlre él, amelyek a fa csomópontjától az egyik leszármazottjáig mutat, a hátra él, amely egy csomóponttól az ősei egyikéhez vezetnek, és keresztirányú élek, amelyek egyik irányba sem vezetnek. Időnként a fa élek, a szélek, amelyek magába a feszítő fához tartoznak, külön osztályozzák az előlre élektől. Ha az eredeti gráf nem irányított, akkor annak összes éle fa vagy hátsó él.

Mélységikeresés-rendezés

A grafikon csúcsainak felsorolását mélységikeresés-rendezésnek tekintik, ha ez a mélységi keresés alkalmazásának lehetséges kimenete erre a gráfra.

Legyen $G=(V,E)$ egy gráf a $n$ csúccsal. mivel $\sigma =(v_{1},\dots ,v_{m})$ az csúcsok listái $V$ , mert $v\in V\setminus \{v_{1},\dots ,v_{m}\}$ , legyen $\nu _{\sigma }(v)$ a legnagyobb $i$ oly módon, hogy $v_{i}$ szomszédja $v$ , ha ilyen $i$ létezik, különben legyen $0$ .

Legyen $\sigma =(v_{1},\dots ,v_{n})$ a csúcsok listája $V$ . A felsorolás $\sigma$ mélységikeresés-rendezése (a forrással $v_{1}$ ) ha, minden $1<i\leq n$ , $v_{i}$ a csúcs $w\in V\setminus \{v_{1},\dots ,v_{i-1}\}$ oly módon, hogy $\nu _{(v_{1},\dots ,v_{i-1})}(w)$ maximális. Újrahívva $N(v)$ a szomszédok halmaza $v$ . egyenértékűen $\sigma$ egy mélységikeresés-rendezés, ha, mindennek $1\leq i<j<k\leq n$ val vel $v_{i}\in N(v_{k})\setminus N(v_{j})$ , létezik egy szomszéd $v_{m}$ nak,-nek $v_{j}$ oly módon, hogy $i<m<j$ .

Csúcs rendezés

Lehetőség van arra is, hogy a mélység szerinti keresést gráf vagy fa csúcsainak lineáris sorrendjére rendezzük. Ennek négy lehetséges módja van:

Az előrendezés a csúcsok listája abban a sorrendben, amelyben először bejárták a mélységi keresési algoritmussal. Ez egy kompakt és természetes módszer a haladás leírása előrendezésnél, ahogy már korábban említve volt. A előrendezés kifejező fánál a kifejezés lengyel jelöléssel történik.
A utórendezés a csúcsok listája abban a sorrendben, ahogyan utoljára bejárták az algoritmust. Egy kifejezési fa utórendezése a fordított lengyel jelölésű kifejezéssel.
A fordított előrendezés az előrendelés fordítottja, azaz a csúcsok felsorolása az első látogatásuk ellentétes sorrendjében történik. Az fordított előrendezés nem ugyanaz, mint az utórendezés.
A fordított utórendezés az utórendezés fordítottja, azaz a csúcsok felsorolása az utolsó látogatásuk ellentétes sorrendjében történik. A fordított utórendezés nem ugyanaz, mint az előrendezés.

A bináris fák esetében ezenkívül van rendezési és fordított rendezési sorrend is.

Például, ha az alábbiakban az A csomóponttól kezdve az irányított gráfon keresi a megoldást, az áthaladások sorrendje vagy ABDBACA vagy ACDCABA (hogy B vagy C legyen az első meglátogatása A-ból azt algoritmustól függ). A vmég mindég van nem bejárt szomszéd, akkor ismétli a bejárást visszalépéssel. Így a lehetséges előrendezés az ABDC és az ACDB, míg a lehetséges utórendezés a DBCA és a DCBA, az esetleges fordított utórendezés az ACBD és az ABC D.

A fordított rendezés bármely irányított körmentes gráf topológiai rendezését eredményezi. Ez a sorrend a kontrolláramlás elemzésében is hasznos, mivel gyakran a kontrolláramok természetes linearizálását képviseli. A fenti grafikon reprezentálhatja a szabályozás folyamatát az alábbi kódrészletben, és természetes, hogy ABDC vagy ACD B sorrendet használjuk.

 ha ( A ) akkor {
  B
} különben {
  C
}
D

Pszeudokód

Bemenet: Egy G gráf és egy v csúcs G

Kimenet : Az összes csúcs elérhető a v feliratú felirattal

A mélységi keresés rekurzív megvalósítása:^[2]

 eljárás mélységi keresés ( G, v ) =
  v felcímkézése felfedezettként
  ciklus v és w közötti irányított élnél , amelyek a G .adjacentEdges ( v ) részben csináld
    ha a w csúcsot nem címkézik felfedezettként, akkor
      rekurzívan hívja a mélységi keresést ( G, w )

A csúcsok ezen algoritmus általi felfedezésének sorrendjét lexikográfiai sorrendnek nevezzük.

A mélységi keresés nem rekurzív megvalósítása, a legrosszabb hely-bonyolultsággal $O(|E|)$ :^[3]

 eljárás mélységikeresés-iteráció ( G, v ) eljárás
  Legyen S verem
  S .push ( v )
  amíg az S nem üres csináld
    v = S .pop ()
    ha a v nem feltüntetett címkével rendelkezik, akkor
      v felcímkézése felfedezettként
      ciklus élét a ''''V-W-G'''' .adjacentEdges (V) csináld 
        S .push ( w )

A mélységi keresés két változata az egyes csúcsok szomszédait egymástól ellentétes sorrendben látogatja meg: a rekurzív variáció által meglátogatott v első szomszédja a szomszédos élek listáján az első, míg az iteratív változatban az első meglátogatott szomszéd az utolsó, a szomszédos élek listáján. A rekurzív megvalósítás a példagráfból a következő sorrendben látogatja meg a csomópontokat: A, B, D, F, E, C, G. A nem rekurzív megvalósítás a csomópontokon ilyen formában járja be: A, E, F, B, D, C, G.

A nem rekurzív megvalósítás hasonló a szélességi kereséshez, de két dologban 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.

Alkalmazások

A labirintus létrehozásához használt véletlenszerű algoritmus, amely hasonló a mélységi kereséshez

Algoritmusok, amelyek építőelemként a mélységi keresést, a következők:

Csatlakoztatott alkatrészek keresése.
Topológiai rendezés.
2- (él vagy csúcs) kapcsolt elemek keresése.
3- (él vagy csúcs) kapcsolt elemek megkeresése.
Megtalálni a hidak egy gráfon.
Generáló szó annak érdekében, hogy a telekkorlát egy csoport.
Erősen összekapcsolt alkatrészek keresése.
Planaritástesztelés.
Rejtvények megoldása csak egy megoldással, például labirintusokkal. (A mélységi keresés úgy adaptálható, hogy minden megoldást megtaláljon a labirintusban, ha csak a meglátogatott halmaz aktuális útvonalán lévő csomópontokat vesz fel.)
A labirintus létrehozása véletlenszerűen elvégzett mélység-előzetes keresést használhat.
Bikonoktivitás keresése gráfokban.

Bonyolultság

A mélységi keresés számítási bonyolultságát John Reif vizsgálta. Pontosabban, adott grafikon $G$ , Legyen $O=(v_{1},\dots ,v_{n})$ egy szabványos rekurzív mélységi keresési algoritmus által kiszámított sorrend. Ezt a megrendelést lexikográfiai mélységi keresési sorrendnek nevezzük. John Reif fontolóra vette a lexikográfiai mélységi keresés sorrendjének kiszámítását, megadva egy gráfot és egy forrást. A probléma döntő változata (annak tesztelése, hogy van-e valamilyen $u$ csúcs valamilyen $v$ csúcs előtt ebben a sorrendben) P-teljes,^[4] ami azt jelenti, hogy „ez egy rémálom a párhuzamos feldolgozáshoz“.^[5]

Az mélységben kereső sorrendje (nem feltétlenül a lexikográfiai sorrend) egy randomizált párhuzamos algoritmussal számítható ki az RNC komplexitási osztályban.^[6] 1997-től nem volt ismert, hogy egy mély-első átjárást lehet-e létrehozni egy determinisztikus párhuzamos algoritmussal, az NC bonyolultsági osztályban.^[7]

Kapcsolódó szócikkek

Szélességi keresés

Irodalom

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.3: Depth-first search, pp. 540–549.
Goodrich, Michael T. & Tamassia, Roberto (2001), Algorithm Design: Foundations, Analysis, and Internet Examples, Wiley, ISBN 0-471-38365-1
Kleinberg, Jon & Tardos, Éva (2006), Algorithm Design, Addison Wesley, pp. 92–94
Knuth, Donald E. (1997), The Art of Computer Programming Vol 1. 3rd ed, Boston: Addison-Wesley, ISBN 0-201-89683-4, OCLC 155842391, <http://www-cs-faculty.stanford.edu/~knuth/taocp.html> Archiválva 2008. szeptember 4-i dátummal a Wayback Machine-ben

Jegyzetek

↑ Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. p.606
↑ Goodrich and Tamassia; Cormen, Leiserson, Rivest, and Stein
↑ Page 93, Algorithm Design, Kleinberg and Tardos
↑ Reif (1985). „Depth-first search is inherently sequential”. Information Processing Letters 20 (5). DOI:10.1016/0020-0190(85)90024-9.
↑ Mehlhorn, Kurt. Algorithms and Data Structures: The Basic Toolbox. Springer (2008)
↑ Aggarwal, A. & Anderson, R. J. (1988), A random NC algorithm for depth first search.
↑ Karger, David R. & Motwani, Rajeev (1997), An NC algorithm for minimum cuts.

Fordítás

Ez a szócikk részben vagy egészben a Depth-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. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

[1] Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. p.606

[2] Goodrich and Tamassia; Cormen, Leiserson, Rivest, and Stein

[3] Page 93, Algorithm Design, Kleinberg and Tardos

[4] Reif (1985). „Depth-first search is inherently sequential”. Information Processing Letters 20 (5). DOI:10.1016/0020-0190(85)90024-9.

[mehlhorn-5] Mehlhorn, Kurt. Algorithms and Data Structures: The Basic Toolbox. Springer (2008)

[6] Aggarwal, A. & Anderson, R. J. (1988), A random NC algorithm for depth first search.

[7] Karger, David R. & Motwani, Rajeev (1997), An NC algorithm for minimum cuts.

[1]

[2]

[3]

[4]

[5]

[6]

[7]