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 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[1] 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 []
[2]
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
- Datuak: Q816319
- Multimedia: Depth-first search / Q816319