Algorisme de cerca

Un algorisme de cerca és aquell 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 baldosines 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 de emplear 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'un baldosín a un altre i detectar si en el baldosín es troba el llibre.

Fitxer: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

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 pseudocódigo 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

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 ombre màxim de comparacios és

n

{\textstyle \lfloor \log _{2}n+1\rfloor } , on n {} é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 pseudocódigo 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