Mélységi keresés

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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[szerkesztés]

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 időbe telik,[1] a gráf méretében lineáris. Ezekben az alkalmazásokban 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[szerkesztés]

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

A következő grafikonhoz:

Graph.traversal.example.svg

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[szerkesztés]

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[szerkeszté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 egy gráf a csúccsal. mivel az csúcsok listái , mert , legyen a legnagyobb oly módon, hogy szomszédja , ha ilyen létezik, különben legyen .

Legyen a csúcsok listája . A felsorolás mélységikeresés-rendezése (a forrással ) ha, minden , a csúcs oly módon, hogy maximális. Újrahívva a szomszédok halmaza . egyenértékűen egy mélységikeresés-rendezés, ha, mindennek val vel , létezik egy szomszéd nak,-nek oly módon, hogy .

Csúcs rendezés[szerkeszté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.

If-then-else-control-flow-graph.svg

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[szerkesztés]

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  :[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:

  1. sor helyett vermet használ, és
  2. 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[szerkesztés]

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[szerkesztés]

A mélységi keresés számítási bonyolultságát John Reif vizsgálta. Pontosabban, adott grafikon , Legyen 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) <b id="mw_g">P-teljes</b>,[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[szerkesztés]

Irodalom[szerkesztés]

Jegyzetek[szerkesztés]

  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.  
  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.

Fordítás[szerkeszté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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk[szerkesztés]