A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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 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
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 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 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
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 :[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
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 , 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
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
- Nyílt adatstruktúrák – 12.3.2. Szakasz – Mélység első keresése, Pat Morin
- C ++ Boost Graph Library: Mélység első keresése
- Mélység-első keresés animáció (egy irányított grafikonhoz)
- Mélységi és szélességi keresés: magyarázat és kód
- QuickGraph[halott link], mélységi első keresési példa. Háló
- A mélységi keresés algoritmusának illusztrált magyarázata (Java és C ++ implementációk)
- YAGSBPL – Sablon alapú C ++ könyvtár a grafikonkereséshez és a tervezéshez
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.
Analóg multiméterek túlterhelés elleni védelme
Egyenáram
Egyenáram mérése
Egyenirányítós lengőtekercses műszer
Elektromágnes (fizika)
Elektromos feszültség
Elektromos térerősség
Fáziseltolódás
Fázismutató
Fajlagos ellenállás
Feszültséggenerátor
Feszültségváltó
Forgó mágneses tér
Háromfázisú hálózat
Hőelektromosság
Hatásos ellenállás
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.