Busqueda Heuristica

Tema 4 búsqueda heurística
4.1 Elementos implicados
Se puede distinguir dos marcos de referencia diferentes que ayudan a concretar los problemas y las soluciones aportadas. Es convenient diferenciar las atribuciones que le corresponden a cada uno de estos:
Dominio del observador:
Los métodos heurístricos tratan de resolver problemas difíciles eficientemente. No garantizan encontrar lasolución óptima, pero sí buentas aproximaciones con menos esfuerzo. El origen de estos métodos está en el análisis del comportamiento humano.
Los problemas que van a ser objeto de esta técnicas pueden ser de dos tipos:
1. Problemas de solución parcialmente conocida, como por ejemplo los casos de diagnostico en medecina
2. problemas intratables de solución conocida. Son los que no pueden resolversecompletamente por la complejidad implicada, pero que sí se conoce el método para resolverlos, como por ejemplo el ajedrez.
Los métodos heurísticos son adecuados para problemas en los que para alcanzar un nivel de principiante no es necesario realizar un proceso excesivamente complejo. Es objetivo del modelo no tiene por que ser exactametne obtener una determinada meta, también puede ser reducir elcoste o el tamaño de la solución.
Dominio propio:
Los métodos heurísticos se utilizaan para obtener soluciones útiles en problemas sujetos al fen´meno de la explosión combinatoria. Estos problemas difíciles pueden ser de dos tipos:
Tijpo P:
Los que pueden ser resueltos mediante un procedimiento de complejidad polinómica (no suele ser elevado).
Tipo PN:
En los que todos los algoritmosconocidos requieren un tiempo exponencial en el peor caso, aunque se conocen algoritmos eficientes no deterministas.
Los ejemplos clásicos son el ajedrez (el número de operaciones necesarias es 10120), el viajante de comercio (la solución depende en forma factorial del número de ciudades implicadas) y el juego del 8-Puzzle (para el caso de 4´4 el espacio de estados lo forman 16! Nodos distintos).Los objetivos declarados en el dominio del observador suelen traducirse en estabglecer las llamadas funciones de evaluación heurística o fev que ayudan a seleccionar el estado más prometedor.
4.1.1 Conocimiento de control
La clave de los procesos heurísticos es ahorrar tiempo y/o espacio de almacenamiento evitando recorrer muchos caminos inútiles.no consiste en eliminar una parte del espacio debúsqueda, sino en introducir información adicional que guíe el recorrido realizado (introduciendo reglas de control heurístico en el proceso de búsqueda).
Reglas de control heurístico
En función del conocimiento reflejado, pueden ser de dos tipos:
- Dependiente del dominio: para seleccionar algunas de las situaciones alcanzadas y también para seleccionar la siguiente acción aplicable sobreaquella.
- Conocimiento general disponible sobre el funcionamiento del solucionador.
Funciones de evaluación heurística (fev)
Son una aplicación del espacio de estados sobre un espacio numérico Ä(estadoj) = nj, siendo nj el valor numérico que refleja en qué grado se considera prometedor un estado en la búsqueda de la solución.
El conocimiento reflejado por las fev si obtiene a través delestablecimiento de modelos simplificados del modelo original. Suelen ser funciones de evaluación estáticas que miden factores que determinan la proximidad al objetivo.
En el caso del 8-Puzzle, si simplificamos el modelo, podemos establecer una medida heurística que se utiliza para determinar la distancia de un nodo cualquiera a la meta (distancia de Manhattan o entre los bloques de edificios).Evidentemente, cuanto mejor indique la fev la cercanía real a la meta, menor será el grafo de búsqueda expandida. Una condición que deben cumplir las fev es que su valor máximo (o mínimo) debe alcanzarse al ser aplicado a un estado meta. A la hora de buscar las fev hay que tener en cuenta el coste que eso conlleva. O sea que sí compensa el coste al hecho de realizar el proceso sin dicho conocimiento o con...