TIPOS DE BUSQUEDA

Las técnicas de búsqueda son una serie de esquemas de

representación del conocimiento, que mediante diversos algoritmos

nos permite resolver ciertos problemas desde el punto de vista de la

I.A.

• Conjunto de estados: todas las configuraciones posibles en el

dominio.

• Estados iniciales: estados desde los que partimos.

• Estados finales: las soluciones del problema.

• Operadores: se aplican para pasar de un estado a otro.

BUSQUEDA CIEGA

Sólo utiliza información acerca de si un estado es o no objetivo para

guiar su proceso de búsqueda.

Expandir un nodo: obtener los posibles hijos de un nodo a partir de

la aplicación de los distintos operadores sobre él.

Nodo cerrado: Se han aplicado todos los posibles operadores

sobre él, obteniéndose todos sus posibles hijos.

TIPOS DE BÚSQUEDA CIEGA

Búsqueda en amplitud.

Búsqueda en profundidad.

Búsqueda en profundidad progresiva.

Búsqueda bidireccional.

Búsqueda en amplitud

- Procedimientos de búsqueda nivel a nivel.

- Para cada uno de los nodos de un nivel se aplican todos los

posibles operadores.

- No se expande ningún nodo de un nivel antes de haber

expandido todos los del nivel anterior.

- Se implementa con una estructura FIFO.

Búsqueda en profundidad:

• La búsqueda se realiza por una sola rama del árbol hasta encontraruna solución o hasta que se tome la decisión de terminar la búsquedapor esa dirección.

Terminar la búsqueda por una dirección se debe a no haber posiblesoperadores que aplicar sobre el nodo hoja o por haber alcanzado unnivel de profundidad muy grande.

• Si esto ocurre se produce una vuelta atrás (backtracking) y se siguepor otra rama hasta visitar todas las ramas del árbol si es necesario.

Las técnicas de búsqueda heurística usan el conocimiento del

dominio para adaptar el solucionador y, de esta manera, éste sea

más potente y consiga llegar a la solución con mayor rapidez. Por

tanto, estas técnicas utilizan el conocimiento para avanzar

buscando la solución al problema.

Definiciones:

Costo del camino

Costo para hallar la solución

Potencia heurísticaSe conoce cuando un estado no es objetivo, y si es mas

“prometedor” que otro.

Búsqueda bidireccional

• Se llevan a la vez dos búsquedas: una descendente desde el nodo inicial y otra ascendente desde el nodo meta.

• Al menos una de estas dos búsquedas debe ser en anchurapara que el recorrido ascendente y descendente puedanencontrarse en algún momento.

BÚSQUEDA HEURÍSTICA

Estrategias de búsqueda heurística

Primero el mejor:

• Metodología: elegir como siguiente nodo aquel con mayor

función de evaluación.

• Tipo: tentativo.

• Ventajas: no depende en exceso de la función de evaluación.

• Inconvenientes: excesiva complejidad espacial, pues se deben

guardar todos los nodos abiertos.

Búsqueda con Adversos

La búsqueda con adversos (juego contra un oponente) analiza

los problemas en los que existe mas de un adversario modificando

el estado del sistema.

Hay dos operadores:

- el que lleva el problema a la mejor situación (jugada nuestra)

- el que lleva el problema a la peor situación (jugada de nuestro

adversario)

Problema del Laberinto

En el siguiente laberinto, se puede pasar desde una casilla a otra de

las posibles adyacentes (arriba, abajo, izquierda, derecha), salvo si

existe una barrera entre ellas.

Objetivo: ir de I a F