Algoritme de busca

Un algoritme de busca és un conjunt d'instruccions que estan dissenyades per a localisar un element en certes propietats dins d'una estructura de senyes; per eixemple, ubicar el registre corresponent a certa persona en una base de senyes, o el millor moviment en una partida d'escacs.

La variant més simple del problema és la busca d'un número en un vector.

Busca informada vs no informada

Un problema típic de l'inteligència artificial consistix en buscar un estat concret entre un conjunt determinat, al que se li crida espai d'estats. Imaginem, per eixemple, una habitació en baldosines en la que hi ha un llibre. Un robot es desija desplaçar per l'habitació en la finalitat d'aplegar a dit llibre. ¿De quina manera ho farà? En este punt és a on entren en joc les estratègies i els algoritmes de busca.

Quan el sistema agent (en este cas, el robot) posseïx algun tipo d'informació del mig, s'utilisen tècniques de busques informades; no obstant, si carix de coneiximent algun, es deuran amprar algoritmes de busca no informades. En el nostre eixemple, i per a este últim cas, podem imaginar un robot que no posseïxca cap tipo de visió artificial, que únicament siga capaç de moure's en horisontal o vertical d'un baldosín a un atre i detectar si en el baldosín es troba el llibre.

D'esta forma, els algoritmes de busca poden ser:

• Algoritmes no informats o cegos: en general més ineficientes en temps i memòria que atres métodos.
• Algoritmes informats
  • Algoritmes heurístics: destaquen les Busques Primer el Millor (Algoritme voraç o Greedy i Algoritme de busca A*) i de Millora Iterativa (Algoritme Escalada Simple -Hill Climbing- i Escalada per Màxima Pendent)
  • Algoritmes de Busca en adversari: destaquen el Minimax i el Poda alfa-beta.

Busca seqüencial

Consistix en ser comparant l'element a buscar en cada element del vector fins a trobar-ho o fins que s'aplegue al final, açò fa que la busca siga secuencialmente (d'ahí el seu nom). L'existència es pot assegurar quan l'element és localisat, pero no podem assegurar la no existència fins a no haver analisat tots els elements del vector. S'utilisa sense importar si el vector està prèviament ordenat o no. A continuació es mostra el pseudocódigo de l'algoritme:

Senyes d'entrada:
  vec: vector en el que es desija buscar la senya 
  tam: tamany del vector. Els subíndexs vàlits van des de 0 fins a tam-1 inclusivament. Pot representar-se aixina:  vec[0...tam) o vec[0...tam-1].
  senya: element que es vol buscar.

Variables
  pos: posició actual en el vector

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

• C

int busquedaSimple(int  vector[n], int n, int senya) {

    int i;

    for(i=0; i<n; i++){
        if(date==vector[i]) {
            return i;
        }
    }

    return -1;

}