Download - Criterios de Busqueda en I.A
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).