Sügavuti otsing

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

Omadused

Sügavuti otsingu ajaline ja ruumi keerukus oleneb selle kasutuse alast. Teoreetilises arvutiteaduses kasutatakse sügavuti otsingut tavaliselt terve graafi läbimiseks ning selle keerukus on O(|V|+|E|). 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 algoritmide 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 heuristilist 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üüsimise 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

Teostame sügavuti otsingu järgmise graafi peal:

Leppime kokku, et vasak alampuu läbitakse enne kui parem alampuu ja peame meeles juba läbitud tippude järjendi. Alustame otsingu tipust 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 tippe C ja G. Iteratiivne süvenemine lubab vältida sellist olukorda.

Sügavuti otsing Pythonis

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 tipu, väljastame selle ja otsime sellest tipu kõik alamtipud.

Kasutusalad

Algoritme, kus on kasutusel sügavuti otsing:

• Ühendatud komponentide leidmine
• Topoloogiline sortimine
• Sillade leidmine
• Kõvasti ühendatud graafi komponentide leidmine
• Planaarsuse kontrollimine
• Puslede lahendamine (näiteks labürindid)
• Labürintide genereerimine
• Kahepoolselt ühendatud graafi leidmine