Sügavuti otsing

Allikas: Vikipeedia
Jump to navigation Jump to search

Sügavuti otsing (ingl Depth-first search) on algoritm, mis on mõeldud graafi- või puukujulise andmestruktuuri läbimiseks. Algoritmi alguspunkt on juurtipp (graafi puhul valitakse juhuslik punkt) ning algtippust alustades läbitakse iga tipu alampuu enne järgmisele punktile liikumist. Prantsuse matemaatik Charles Pierre Trémaux uuris 19. sajandil sügavuti otsingu sobilikkust labürintide lahendamiseks.[1][2]

Omadused[muuda | muuda lähteteksti]

Sügavuti otsingu ajaline ja ruumi keerukus oleneb selle kasutuse alast. Teoreetilises arvuti teaduses on sügavuti otsing tavaliselt kasutatud terve graafi läbimiseks ning selle keerukus on O(|V|+|E|).[3] Sellistes tingimustes on algoritmi ruumi keerukus halvemal juhul O(|V|), sest tuleb meeles pidada tippude magasini ja läbitud tippude hulka. Sellisel juhul on ajaline ja ruumi keerukus laiuti ja sügavuti otsingutel sama ning valik kahe algoritmi vahel põhineb tippude järjestusest graafis ja mitte algortmide keerukusest. Teistes valdkondades nagu tehisintellekt, graaf võib olla liiga mahukas selleks, et seda täielikult läbida või isegi lõpmatu. Sellistes juhtudes otsingu teostatakse ainult piiratud sügavusel, mis on lineaarse ajalise keerukusega ning ruumi keerukus on proportsionaalne sügavusele. Sellisel lähenemisel on ruumi keerukus väiksem kui laiuti otsingu ruumi keerukus sarnasel graafil. Suurte andmestruktuuride puhul kasutab sügavuti otsing heruistilist lähenemist suurima tõenäosusega haru valimiseks. Juhul, kui vajalik sügavus on teadmata, kasutatakse iteratiivse süvenemisega sügavuti otsingu (ingl iterative deepening depth-first search), mille põhimõte on iga iteratsiooniga sügavuse suurenemine kuni tulemuseni jõudmiseni. Tehisintellekti analüseerimise puhul ja haru faktoriga suurem kui 1, iteratiivne süvenemine suurendab tööaega ainult püsiva faktori võrra. Aga seda ainult juhul, kui õige sügavuspiir on tippude arv tasemete kaupa geomeetrilise kasvu tõttu teada. Sügavuti otsingu võib kasutada ka tippu järjendi korjamise jaoks.

Näidis[muuda | muuda lähteteksti]

Teostame sügavuti otsingu järgmise graafi peal:

Graph.traversal.example.svg

Leppime kokku, et vasak alampuu läbitakse enne kui parem alampuu ja peame meeles juba läbitud tippude järjendi. Alustame otsingu tippust A ja läbime graafi järgmisel järjestusel: A, B, D, F, E, C, G. Kui me ei jäta meelde juba läbitud tippude hulka, siis otsing jääb tsükli sisse A, B, D, F, E, A, B, D, F, E… ja ei läbi kunagi tippud C ja G. Iteratiivne süvenemine lubab vältida sellist olukorda.

Sügavuti otsing Pythonis[muuda | muuda lähteteksti]

Järgnevas Pythoni koodis läbib meetod dfs graafi G alustades tipust s mitte rekursiivse sügavuti otsinguga:

def dfs(graaf, juur_tipp):
    magasin = [juur_tipp]
    kylastatud = set(juur_tipp)
    while magasin:
        v = magasin.pop(len(magasin)-1)
        yield v
        [(magasin.append(u), kylastatud.add(u)) for u in graaf.get(v, []) if u not in kylastatud]

graaf = {'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G', 'H'],
    'D': ['I', 'J'],
    'E': ['K','L', 'M'],
    'F': ['N'],
    'H': ['O', 'P']}

>>> print(list(dfs(graaf, 'A')))
['A', 'C', 'H', 'P', 'O', 'G', 'F', 'N', 'B', 'E', 'M', 'L', 'K', 'D', 'J', 'I']

Antud algoritmi implementatsioon saab sisendiks graafi graaf ja alguspunkti juur_tipp, mis peab sisalduma graafis. Paneme algus punkti magasini sisse ning “läbitud” hulka sisse. Täidame algoritmi nii kaua, kui magasin ei ole tühi. Tsükli sees võtame magasinist viimasena lisatud tippu, väljastame selle ja otsime sellest tippu kõik alamtippud.

Kasutus alad[muuda | muuda lähteteksti]

Algoritmide nimekiri, mis kasutavad sügavuti otsingu:

  • Ühendatud komponentide leidmine
  • Topoloogiline sortimine
  • Sillade leidmine
  • Kõvasti ühendatud graafi komponentide leidmine
  • Planaarsuse kontrollimine[4][5]
  • Puslete lahendamine (näiteks labüritntid)
  • Labürintide genereerimine
  • Kahepoolselt ühendatud graafi leidmine

Viited[muuda | muuda lähteteksti]

  1. Even, Shimon (2011), Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48, ISBN 978-0-521-73653-4.
  2. Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (3rd ed.), Pearson Education, ISBN 978-0-201-36118-6.
  3. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. p.606
  4. Hopcroft, John; Tarjan, Robert E. (1974), "Efficient planarity testing", Journal of the Association for Computing Machinery, 21 (4): 549–568
  5. de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), "Trémaux Trees and Planarity", International Journal of Foundations of Computer Science, 17 (5): 1017–1030