Algorisme de cerca

Fig.1 Exemple de taula hash : agenda de telèfons

Un algorisme de cerca és un algorisme que està dissenyat per localitzar un element amb certes propietats dins d'una estructura de dades; per exemple, situar el registre corresponent a certa persona en una base 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 un vector.

Cerca informada vs no informada

Un problema típic de la Intel·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. Un robot 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 els algorismes 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:

• Algorismes no informats o cecs: en general més ineficients en temps i memòria que altres mètodes.
• Algorismes informats
  • Algorismes heurístics: destaquen les Cerques Primer el Millor (Algorisme voraç o Greedy i Algorisme de cerca A) i de Millora Iterativa (Algorisme Escalada Simple -Hill Climbing- i Escalada per Màxima Pendent)
  • Algorismes de Cerca amb adversari: destaquen el Minimax i el Poda alfa-beta.

Cerca seqüencial

S'utilitza quan el vector no està ordenat o no pot ser ordenat 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 el pseudocodi de l'algorisme:

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.

Variables
pos: posició actual en el vector

pos = 0
while pos < tam:
if vec[pos] == dada: 
Retorne veritable i/o pos, 
else:
pos = pos + 1
Fi (while)
Retorne fals,

• C

• int busquedaSimple(int vector[n], int n, int dato) {
  
   int i;
  
   for(i=0; i<n; i++){
   if(dato==vector[i]) {
   return i;
   break;
   }
   }
  
   return -1;
  
  }
  

Cerca dicotòmica (binària)

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 disminueix exponencialment el nombre d'iteracions necessàries. En el pitjor dels casos el nombre màxim de comparacions és ${\textstyle \lfloor \log _{2}n+1\rfloor }$é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.${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$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 dada
tam: grandària del vector. Els subíndexs vàlids van des de 0 fins a mida-1 inclusivament.
dada: element que es vol buscar.

Variables
centre: subíndex central de l'interval
inf: límit inferior de l'interval
sup: límit superior de l'interval

inf = 0
sup = tam-1

Mentre inf <= sup:
centre = ((sup - inf) / 2) + inf // Divisió sencera: es trunca la fracció
Si vec[centre] == dato retornar veritable i/o pos, en cas contrari:
Si dada < vec[centre] llavors:
sup = centro - 1
En cas contrari:
inf = centro + 1
Fi (Mentre)
Retornar Fals

• C

int busquedaBinaria(int vector[], int n, int dato) {
 int centro,inf=0,sup=n-1;
 while(inf<=sup){
 centro=((sup-inf)/2)+inf;
 if(vector[centro]==dato) return centro;
 else if(dato < vector[centro]) sup=centro-1;
 else inf=centro+1;
 }
 return -1;
}

Implementació recursiva en C++

• C++

 #include <vector>

 bool busqueda_dicotomica(const vector<int> &v, int principio, int fin, int &x){
 bool res;
 if(principio <= fin){
 int m = ((fin - principio)/2) + principio;
 if(x < v[m]) res = busqueda_dicotomica(v, principio, m-1, x);
 else if(x > v[m]) res = busqueda_dicotomica(v, m+1, fin, x);
 else res = true;
 }else res = false;
 return res;
 }
 /*{Post: Si el troba= true, si no false}*/

Implementació recursiva en Python

• Python

def busquedaBinaria (numeros, inicio, fin, elemento):
 if (inicio == fin): return numeros [inicio] == elemento

 centro = ((fin - inicio) // 2) + inicio

 if (elemento < numeros [centro]):
 return busquedaBinaria (numeros, inicio, centro - 1, elemento)

 elif (elemento > numeros [centro]):
 return busquedaBinaria (numeros, centro + 1, fin, elemento)

 else: return True

def busqueda (numeros, elemento):
 if (numeros == None) or (numeros == []):
 return False

 else: return busquedaBinaria (numeros, 0, len (numeros) - 1, elemento)

Implementació recursiva en Python3

• Python

def bin(a,x,low,hi):
 ans = -1 
 if low==hi: ans = -1
 else: 
 mid = (low+((hi-low)//2)) 
 if x < a[mid]: ans = bin(a,x,low,mid)
 elif x > a[mid]: ans = bin(a,x,mid+1,hi) 
 else: ans = mid
 return ans

# É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)

Implementació iterativa en Python3

• Python

def bin(a, c):
 ans = -1
 if a[0] >= c: ans = -1
 else:
 low, hi = 0, len(a)
 while low+1 != hi:
 mid = low + ((hi-low)//2)
 if a[mid] < c: low = mid
 else: hi = mid
 ans = low 
 return ans

# É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)

Enllaços externs

• ALT: Algorithm Learning Tool. Eina de suport a l'ensenyament d'algorismes que mostra gràficament el seu funcionament. Permet implementar algorismes propis i realitzar una execució dinàmica i interactiva