Sakonera bilaketa

Sakonera bilaketa () informazioa erabiltzen ez duen bilaketa algoritmo bat da, zuhaitz (grafo teoria) edo grafo bateko nodo guztiak aztertu ahal izateko era ordenatu baina ez uniforme batean. Algoritmo horrek aurkitzen dituen nodo guztiak hedatzen ditu, era errekurtsiboan, ibilbide zehatz bat jarraituz. Ibilbide horretatik arakatutako nodo gehiago ez direnean geratzen, atzera bueltatzen da (backtracking), eta prozesu berdina errepikatzen du prozesatutako nodoaren anai guztiekin.

 Ebaluazioa 

 Osotasuna: DFS algoritmoak osotasuna bermatzen du arakatzen ari garen grafoa finitua bada, kasu honetan nodo guztiak begiratuko direlako.
 Optimaltasuna: DFSek ez du inoiz optimaltasuna bermatzen, soluzio sakonago bat aurki dezakeelako aurrenik eta behin aurkituta ez du gehiago begiratuko.
 Denbora konplexutasuna: kasurik txarrenean  izango da, b bere adarkatze faktorea izanda (nodo bakoitzetik bataz beste ateratzen diren nodo berri kopurua) eta m grafoaren sakonera maximoa.
 Espazio konplexutasuna:  b grafoaren adarkatze faktorea izanda eta d kostu txikieneko soluzioaren sakonera, sortutako nodo guztiak memorian geratzen direlako.

 Adibidea 
Adibide honetan, lehenengo ezkerreko nodoak begiratuko ditu. Beraz, argazkian ikusten dugun grafoan DFS bilaketa algoritmoa erabiltzen badugu lortuko dugun bidea S,A,C,G izango da.

 Sasikodea 
DFS(grafo G)
     BAKOITZERAKO nodo u ∈ V[G] EGIN
             izena[u] ← IKUSI_GABEA
             aita[u] ← NULL
     denbora ← 0
     BAKOITZERAKO nodo u ∈ V[G] EGIN
             BADA izena[u] = IKUSI_GABEA ORDUAN
                     DFS_Begiratu(u,denbora)

  DFS_Begiratu(nodo u, int denbora)
     izena[u] ← IKUSITA
     denbora ← denbora + 1
     d[u] ← denbora
     BAKOITZERAKO v ∈ albokoak[u] EGIN
             BADA izena[v] = IKUSI_GABEA ORDUAN
                     aita[v] ← u
                     DFS_Begiratu(v,denbora)
     denbora[u] ← AMAITU
     denbora ← denbora + 1
     f[u] ← denboraLehenik eta behin nodo guztien izenak ikusi gabe bezala markatuko dira eta nodo hauen aitak nullera hasieratuko dira. Gero, nodo guztiak begizta baten bidez aztertuko ditugu. Nodoa ikusi gabeen zerrenda baldin badago orduan DFS_begiratu azpiprogramari deituko da, nodoa eta denbora pasatuz.

Nodoa begiratu bezala markatuko da eta denbora eguneratuko da. Begizta baten bidez nodoaren seme guztiak begiratuko dira, begiratuta ez badaude.

 Kodea 
def depthFirstSearch(problem):
    hurrengoak = Stack()
    begiratuak = set()
    hasiera = problem.getStartState()
    bukatu = False
    bidea = []
    tupla = (hasiera, bidea)
    hurrengoak.push(tupla)

    while (not hurrengoak.isEmpty()) and (not bukatu):
        tuplaOrain = hurrengoak.pop()
        egoeraOrain = tuplaOrain[0]
        bidea = tuplaOrain[1]
        begiratuak.add(egoeraOrain)
        if problem.isGoalState(egoeraOrain):
            bukatu = True
        else:
            semeak = problem.getSuccessors(egoeraOrain)
            for i in range(len(semeak)):
                egoeraSemea = semeak[i][0]
                norabideaSemea = semeak[i][1]
                if egoeraSemea not in begiratuak:
                    tuplaAux = (egoeraSemea, bidea + [norabideaSemea])
                    hurrengoak.push(tuplaAux)

    if bukatu:
        return bidea
    else:
        return []

Hasteko, hainbat aldagai definituko ditugu. Ondoren, hasierako nodoa sartuko dugu pilan eta begizta bat sortuko dugu. Begizta honetan begiratzen ari garen nodoa problemaren amaiera den begiratzen dugu, horrela bada begiztatik aterako gara. Bestela nodoaren seme guztiak zerrenda batean sartuko ditugu. Behin seme guztiak izanda begiratuta zerrendan dauden konprobatuko dugu. Azkenik, bukatu aldagaia True bada bidea bueltatuko dugu, bestela zerrenda huts bat.

 Erreferentziak 

 Kanpo estekak 

Kategoria:Datu-egitura
Kategoria:Algoritmoak