Criterios de Búsquedas en I.A

Realizado Por: Silva José M.

C.I.: 20.667.213

UNIVERSIDAD FERMIN TOROFACULTAD DE INGENIERIA

ESCUELA DE COMPUTACION

CABUDARE, MAYO 2016

Los procesos 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.

Elementos de búsqueda 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.

CRITERIOS DE BÚSQUEDA EN I.A

Solucionador: Elemento que nos permite evolucionar de un estado a otro mediante un algoritmo aplicando los siguientes pasos:

a. Elegir el estado a explorar.

b. Establecer un operador que trabaje sobre el estado elegido en el paso 1.

c. Comprobar si el resultado obtenido es un estado final (es una solución del problema). Sino ir al paso1.

CRITERIOS DE BÚSQUEDA EN I.A

Ejemplo con 8-puzzle: Este juego consiste en, dada una matriz de 3x3 elementos, tenemos 8 números que deben de ser ordenados dejando la casilla central vacía.

Para resolverlo usaremos técnicas de búsqueda: El conjunto de estados son todas las combinaciones

posibles de ordenación de las 9 piezas. El estado inicial es el estado en el que nos dan el puzzle,

en desorden. El estado final es el puzzle ordenado. Los operadores son mover una ficha en cualquier

dirección: arriba, abajo, izquierda o derecha.

CRITERIOS DE BÚSQUEDA EN I.A

Ejemplo con 8-puzzle

Un buen solucionador será aquel que ejecute su función a bajo coste según los siguientes parámetros: Complejidad temporal: tiempo empleado en obtener la

solución Complejidad espacial: cantidad de recursos necesarios para

alcanzar la solución. Por ejemplo: memoria. La explosión combinatoria: es un fenómeno que hace que el

problema no se pueda abordar computacionalmente.

TIPOS DE SOLUCIONADORES

BÚSQUEDA CIEGASólo maneja información acerca de si un estado es o no objetivo para guiar su proceso de búsqueda.

Antes de explicar los tipos de búsqueda ciega, convendría dar una serie de definiciones:

Expandir un nodo: Conseguir los posibles hijos de un nodo a partir de la aplicación de los diferentes operadores sobre él.

Nodo cerrado: Se han aplicado todos los posibles operadores sobre él, obteniéndose todos sus posibles hijos.

BÚSQUEDA CIEGA Nodo abierto: no han actuado todos los posibles

operadores, con lo que podrían obtenerse nuevos hijos aplicando los operadores restantes.

TIPOS DE BÚSQUEDA CIEGA:Búsqueda en

amplitud

Búsqueda en profundidad progresiva

Búsqueda bidireccional

Búsqueda en profundidad

BÚSQUEDA CIEGA (TIPOS) 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 transmite ningún nodo de un nivel antes de haber expandido todos los del nivel anterior.Se implementa con una estructura FIFO.

BÚSQUEDA CIEGA (TIPOS)

Ventajas

• Si existe la solución, la encuentra en la menor profundidad posible.

Desventajas

• Explosión combinatoria aparece frecuentemente debido a la alta complejidad espacial y temporal de esta técnica.

BÚSQUEDA CIEGA (TIPOS) Búsqueda en profundidad:

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

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

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

BÚSQUEDA CIEGA (TIPOS)

Ventajas

Tiene menor complejidad espacial que búsqueda en amplitud.

Desventajas

Se pueden encontrar soluciones que están mas alejadas de la raíz que otras. Existe el riesgo de presencia de bucles infinitos.

Búsqueda en profundidad progresivaSe define una profundidad predefinida.Se desarrolla el árbol realizando una búsqueda en profundidad hasta el límite definido en el punto anterior.Si se encuentra la solución FINEn caso contrario, se establece un nuevo límite y volvemos al segundo paso.

BÚSQUEDA CIEGA (TIPOS)

BÚSQUEDA CIEGA (TIPOS) 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 anchura para que el recorrido ascendente y descendente puedan encontrarse en algún momento. Cuando se llegue a un nodo que ya había sido explorado con el otro tipo de búsqueda, el algoritmo acaba. El camino solución es la suma de los caminos hallados por cada búsqueda desde el nodo mencionado hasta el nodo inicial y hasta el nodo meta.

SISTEMAS DE REDUCCIÓN

Su objetivo es reducir un problema en sub problemas más sencillos que el problema original.

Ejemplo: integrales por partes.

Grafos: en un grafo de reducción, cada uno de los nodos representan un sub problema del problema original.

BÚSQUEDA HEURÍSTICALas 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 para hallar la

solución: coste necesario para encontrar el

camino anteriormente

definido.

Potencia heurística:

capacidad de un método de

exploración para obtener la solución con un

coste lo más bajo posible.

Costo del camino: coste necesario para ir del nodo raíz al

nodo meta por dicho camino.

FUNCIÓN DE EVALUACIÓN HEURÍSTICA

Definición: es una aplicación del espacio de estados con el espacio de los números realesF(estado) => nn representa lo cercano que esta el estado con el que se ha aplicado la función de evaluación de la solución final.

Es muy importante mantener un equilibrio entre la eficiencia de la función y su complejidad. No debemos tener una función de evaluación demasiado complicada, ni tampoco una demasiado sencilla pero que no avance prácticamente nada en el problema. En caso de no mantener este equilibrio se podría producir explosión combinatoria.

ESTRATEGIAS DE BÚSQUEDA HEURÍSTICA

Tipos: Estrategias tentativas: aquellas en las que se puede abandonar la exploración de una rama y pasar a explorar otra en cualquier momento del problema

Estrategias irrevocables: aquellas en las que no se puede abandonar la exploración de la rama por la que se comenzó.

Métodos: Gradiente Primero el mejor Búsqueda en haz Algoritmo A

Gradiente: elegir el camino de máxima pendiente, usando para ello la función de evaluación.

Ventajas

Se llega a la solución con poco coste computacional.

Inconvenientes

Puede ser que el problema no sea compatible con este método, y, por lo tanto, no conseguiremos obtener la solución.

ESTRATEGIAS DE BÚSQUEDA HEURÍSTICA

Primero el mejor: Elegir como siguiente nodo aquel con mayor función de evaluación.

Ventajas

No depende en exceso de la función de evaluación.

Inconvenientes

Excesiva complejidad espacial, pues se deben guardar todos los nodos abiertos.

ESTRATEGIAS DE BÚSQUEDA HEURÍSTICA

Búsqueda en haz: elegir un conjunto de nodos como los siguientes a expandir, y hacerlo de forma irrevocable.

Ventajas

Inconvenientes

• Más permisible.

• En caso de que el sistema sea irrevocable, este método no actúa con eficacia.

ESTRATEGIAS DE BÚSQUEDA HEURÍSTICA

Algoritmo A: ponderar a la vez lo cerca que estamos del nodo meta y lo lejos que estamos del nodo inicial.

Ventajas• Soluciones más cercanas a la

raíz.

Inconvenientes• La función de evaluación se

complica.

ESTRATEGIAS DE BÚSQUEDA HEURÍSTICA

BÚSQUEDA CON ADVERSOSLa 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).