Sakonera bilaketa

Sakonera bilaketa (ingelesez: DFS edo Depth First Search) 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 $O(b^{m})$ izango da, b bere adarkatze faktorea izanda (nodo bakoitzetik bataz beste ateratzen diren nodo berri kopurua) eta m grafoaren sakonera maximoa.
• Espazio konplexutasuna: $O(b^{d})$ b grafoaren adarkatze faktorea izanda eta d kostu txikieneko soluzioaren sakonera, sortutako nodo guztiak memorian geratzen direlako.

Adibidea

DFS algoritmoaren diagrama

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] ← denbora

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

Kanpo estekak

• Datuak: Q816319
• Multimedia: Depth-first search / Q816319