Unalgorismede cerca és unalgorisme que està dissenyat per localitzar un element amb certes propietats dins d'unaestructura de dades; per exemple, situar el registre corresponent a certa persona en unabase de dades, o el millor moviment en una partida d'escacs.
La variant més simple del problema és la cerca d'un nombre en unvector.
Un problema típic de laIntel·ligència Artificial consisteix a buscar un estat concret entre un conjunt determinat, al que se li crida espai d'estats. Imaginem, per exemple, una habitació amb rajoles en la qual hi ha un llibre. Unrobot es desitja desplaçar per l'habitació amb la finalitat d'arribar a aquest llibre. De quina manera ho farà? En aquest punt és on entren en joc les estratègies i elsalgorismes de cerca.
Quan el sistema agent (en aquest cas, el robot) posseeix algun tipus d'informació del mitjà, s'utilitzen tècniques de cerques informades; no obstant això, si manca de coneixement algun, s'hauran d'utilitzar algorismes de cerca no informades. En el nostre exemple, i per a aquest últim cas, podem imaginar un robot que no posseeixi cap tipus de visió artificial, que únicament sigui capaç de moure's en horitzontal o vertical d'una rajola a un altre i detectar si a la rajola es troba el llibre.
D'aquesta forma, els algorismes de cerca poden ser:
S'utilitza quan el vector no està ordenat o no pot serordenat prèviament. Consisteix a buscar l'element comparant-ho seqüencialment (d'aquí el seu nom) amb cada element del vector fins a trobar-ho, o fins que s'arribi al final. L'existència es pot assegurar quan l'element és localitzat, però no podem assegurar la no existència fins a no haver analitzat tots els elements del vector. A continuació es mostra elpseudocodi de l'algorisme:[1]
Dades d'entrada:vec: vector en el qual es desitja buscar la dada tam: grandària del vector. Els subíndexs vàlids van des de 0 fins a tam-1 inclusivament. Pot representar-se així: vec[0...tam) o vec[0...tam-1].dada: element que es vol buscar.
Variablespos: posició actual en el vector
pos = 0while pos < tam:if vec[pos] == dada: Retorneveritable i/opos, else:pos = pos + 1Fi (while)Retornefals,
intbusquedaSimple(intvector[n],intn,intdato){inti;for(i=0;i<n;i++){if(dato==vector[i]){returni;break;}}return-1;}
S'utilitza quan el vector en el qual volem determinar l'existència d'un element està prèviament ordenat. Aquest algorisme redueix el temps de cerca considerablement, ja que disminueixexponencialment el nombre d'iteracions necessàries. En el pitjor dels casos el nombre màxim de comparacions ésés el nombre dels elements en el vector. Per exemple, en un contenint 50.000.000 elements, l'algorisme realitza com a màxim 26 comparacions. Per implementar aquest algorisme es compara l'element a buscar amb un element qualsevol del vector (normalment l'element central): si el valor d'aquest és major que el de l'element buscat es repeteix el procediment en la part del vector que va des de l'inici d'aquest fins a l'element pres, en cas contrari es pren la part del vector que va des de l'element pres fins al final. D'aquesta manera obtenim intervals cada vegada més petits, fins que s'obtingui un interval indivisible. Si l'element no es troba dins d'aquest últim llavors es dedueix que l'element buscat no es troba en tot el vector.A continuació es presenta el pseudocodi de l'algorisme, prenent com a element inicial l'element central del vector.
Dades d'entrada:vec: vector en el qual es desitja buscar la dadatam: grandària del vector. Els subíndexs vàlids van des de 0 fins a mida-1 inclusivament.dada: element que es vol buscar.
Variablescentre: subíndex central de l'intervalinf: límit inferior de l'intervalsup: límit superior de l'interval
inf = 0sup = tam-1
Mentre inf <= sup:centre = ((sup - inf) / 2) + inf // Divisió sencera: es trunca la fraccióSi vec[centre] == dato retornarveritable i/opos, en cas contrari:Si dada < vec[centre] llavors:sup = centro - 1En cas contrari:inf = centro + 1Fi (Mentre)RetornarFals
intbusquedaBinaria(intvector[],intn,intdato){intcentro,inf=0,sup=n-1;while(inf<=sup){centro=((sup-inf)/2)+inf;if(vector[centro]==dato)returncentro;elseif(dato<vector[centro])sup=centro-1;elseinf=centro+1;}return-1;}
#include<vector>boolbusqueda_dicotomica(constvector<int>&v,intprincipio,intfin,int&x){boolres;if(principio<=fin){intm=((fin-principio)/2)+principio;if(x<v[m])res=busqueda_dicotomica(v,principio,m-1,x);elseif(x>v[m])res=busqueda_dicotomica(v,m+1,fin,x);elseres=true;}elseres=false;returnres;}/*{Post: Si el troba= true, si no false}*/
defbusquedaBinaria(numeros,inicio,fin,elemento):if(inicio==fin):returnnumeros[inicio]==elementocentro=((fin-inicio)//2)+inicioif(elemento<numeros[centro]):returnbusquedaBinaria(numeros,inicio,centro-1,elemento)elif(elemento>numeros[centro]):returnbusquedaBinaria(numeros,centro+1,fin,elemento)else:returnTruedefbusqueda(numeros,elemento):if(numeros==None)or(numeros==[]):returnFalseelse:returnbusquedaBinaria(numeros,0,len(numeros)-1,elemento)
defbin(a,x,low,hi):ans=-1iflow==hi:ans=-1else:mid=(low+((hi-low)//2))ifx<a[mid]:ans=bin(a,x,low,mid)elifx>a[mid]:ans=bin(a,x,mid+1,hi)else:ans=midreturnans# És crida amb: print(bin(Lista, numero_a_buscar, 0, len(Lista)))# Retorna l'índex que coincideix amb 'numero_a_buscar', si no retorna -1# Temps: (log n)
defbin(a,c):ans=-1ifa[0]>=c:ans=-1else:low,hi=0,len(a)whilelow+1!=hi:mid=low+((hi-low)//2)ifa[mid]<c:low=midelse:hi=midans=lowreturnans# És crida amb: print(bin(lista(), numero_a_buscar))# Retorna l'índex que coincideix amb 'numero_a_buscar', si no retorna -1# Temps: (log n)