Algorisme de cerca

De Viquipèdia
Salta a la navegació Salta a la cerca

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[modifica]

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.

Grafico.jpg

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[modifica]

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:[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.

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)[modifica]

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 é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 dada
  tam: grandària del vector. Els subíndexs vàlids van des de 0 fins a tam-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
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++
 #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
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
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
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)

Referències[modifica]

  1. «¿Que es un algoritmo?». [Consulta: 29 maig 2017].

Enllaços externs[modifica]