Zabalera bilaketa

Informatikan, zabalera bilaketa (ingelesez: Breadth-First Search) jakinarazi gabeko bilaketa algoritmo mota bat da, grafoetan (gehienetan zuhaitz motakoak) elementuak bilatzeko erabiltzen dena. Bilaketa algoritmo mota hau errotik bilatzen hasten da (grafoetan edozein elementu erabiliko du erro elementu gisa), eta ondoren erro elementuaren semeak aztertuko ditu bilatutako elementua aurkitu arte. Algoritmo hau informazio gabeko algoritmoen familiakoa da, hau da, ez du estrategia heuristikorik behar.

Algoritmoaren inplementazio ez-errekurtsiboa sakonera bilaketa algoritmoaren inplementazio ez-errekurtsiboarekin nahastu daiteke, oso antzekoak direlako. Lehenengo desberdintasuna bi algoritmoek erabiltzen duten datu egituretan aurkitzen da, zabalera bilaketak Queue (First In First Out arkitektura duena) objektuko lista bat erabiltzen du aztertuko dituen nodoak gordetzeko (muga). Aldiz, sakonera bilaketak Stack (Last In First Out arkitektura duena) motako objektua erabiltzen du. Algoritmoen arteko beste desberdintasuna nodoa aztertuta izan den noiz egiaztatzen den da. Zabalera bilaketa algoritmoak nodoa Queue listan sartu baino lehen egiaztatuko du, eta sakonera bilaketa algoritmoak nodoa Stack listatik ateratzen duenean egiaztatzen du.

Historia

1945. urtean, Konrad Zuse ingeniari alemaniarrak Plankalkül programazio-lengoaiari buruzko tesian (gainditu ez zuena) sortu zuen^[1]. Baina 1959. urtean, Edward F. Moore irakasle estatu batuarrak algoritmoa birsortu zuen, labirinto baten bide motzena aurkitzeko.

Inplementazioa

Sasikodea

Sarrera: Grafo bat.

Irteera: Grafoan bilatzen ari den elementua.

funtzioa ZakoneraBilaketa(grafoa){
    muga Queue() bezala definitu
    erro nodoa bisitatuta bezala markatu
    erro nodoa mugan sartu
    muga hutsik ez dagoen bitartean egin{
        mugatik elementu bat atera eta gorde
        elementua helburua bada{
            elementua bueltatu
        }
        elementua dituen seme guztientzat egin{
            semea bisitatuta bezala markatuta ez badago{
                bisitatuta bezala markatu
                mugan sartu
            }
        }
    }
}

Kodea

Zabalera bilaketa algoritmoarentzako kodea Pythonen:

def zabaleraBilaketa(grafoa):
    muga = Queue()
    bisitatuta = set()
    erroa = grafoa.getErroa()
    bisitatuta.add(erroa)
    muga.push(erroa)
    while (not muga.isEmpty()):
        nodoa = muga.pop()
        if (grafoa.emaitzaDa(nodoa)):
            return nodoa
        semeak = nodoa.getSemeak()
        for i in range(len(semeak)):
            if semeak[i] not in bisitatuta:
                bisitatuta.add(semeak[i])
                muga.push(semeak[i])

Adibidea

Hurrengo adibideak Zabalera bilaketa algoritmoa nola lan egiten duen azaltzen du:

Honako grafoa algoritmoaren sarrera bezala izanda, non hasiera nodoa eta helmuga nodoa 'A' eta 'G' nodoak diren,

Zabalera bilaketa algoritmoak sarrera moduan duen grafo baten adibidea.

zabalera bilaketa algoritmoak honako zuhaitza eraikiko du.

Zabalera bilaketa algoritmoak eraikitzen duen zuhaitza

Algoritmoak sortu duen zuhaitza, hurrengo irudian erakusten den moduan aztertuta izango da:

Zabalera bilaketa algoritmoak zuhaitz bat nola aztertzen duen adibidea (nodoen ezkerraldean dagoen zenbakia nodoak zein ordenetan aztertuak izan diren adieraziz, eta gezi gorriak 'A'-tik 'G'-ra bidea izanda).

Analisia

Kostu konputazionala

Algoritmoaren kostu konputazionala ${\displaystyle O(|V|+|E|)}$ izango da, non ${\displaystyle |V|}$ nodo kopurua eta ${\displaystyle |E|}$ ertz kopurua diren. Kostua horrela kalkulatzen da, kasurik txarrenean algoritmoak nodo eta ertz guztiak aztertuko dituelako.

Memoria kostua

Grafoaren nodo kopurua aldez aurretik ezagutzen dugunean, eta ilaran gehitu diren nodoak zehazteko beste datu egitura bat erabil daitekeenean, memoria kostua ${\displaystyle O(|V|)}$ izango da, ${\displaystyle |V|}$ nodo kopurua izanik.

Osotasuna

Zabalera bilaketa algoritmoa osoa dela esan daiteke (hau da, beti soluzio bat aurkituko duela), baldin eta soilik baldin algoritmoaren sarrera grafoa finitua denean. Algoritmoak grafoa finitua aztertzerakoan, grafoaren elementu guztiak aztertuko ditu irtenbide bat topatu arte.

Adarkatze faktorea

Sarrera grafo bezala erabiltzen den grafoa oso handia izan daiteke kasu batzuetan (edo infinitua), horregatik kasu hauetan komenigarriagoa da adarkatze faktorea erabiltzea algoritmoaren kostu konputazionala deskribatzeko, kostu konputazionala bera baino. Algoritmoaren adarkatze faktorea grafoaren ezaugarrien arabera kalkulatuko da.

Hori aplikatuta, kostu konputazionala deskribatzen duen formula ${\displaystyle O(b^{d+1})}$ da, non ${\displaystyle b}$ grafoaren adarkatze faktorea eta ${\displaystyle d}$ sakonera diren.

Aplikazioak

Zabalera bilaketa algoritmoak lagungarria izan daiteke grafoekin zer ikusia duten arazo hauekin:

Zabor bilketa kopiatzea, Cheneyren algoritmoa.
Bi nodoen tarteko bide laburrena bilatzea (ertza kopurua neurtzeko unitate bezala erabilita).^[2]
Cuthill – McKee sareen alderantzizko zenbaketa.
Ford – Fulkerson metodoa fluxu sare bateko fluxu maximoa kalkulatzeko.
Grafo baten aldebikotasuna probatzeko.
Eta adimen artifizialaren saileko hainbeste arazoetarako.

Erreferentziak

↑ (Alemanez) , 96-105 or..
↑ Aziz, Adnan.. (2010). Algorithms for interviews : a problem solving approach. Algorithmsforinterviews.com ISBN 1-4537-9299-6. PMC 696214313. (Noiz kontsultatua: 2020-12-18).