Clases

Búsqueda heurística
Prof. Constantino Malagón

Area de Computación e Inteligencia Artificial

1

Búsqueda heurística
n

n

Los métodos de búsqueda heurística disponen de alguna información sobre la proximidad de cada estado a un estado objetivo, lo que permite explorar en primer lugar los caminos más prometedores. Son características de los métodos heurísticos:
n n

n

Nogarantizan que se encuentre una solución, aunque existan soluciones. Si encuentran una solución, no se asegura que ésta tenga las mejoresas propiedades (que sea de longitud mínima o de coste óptimo). En algunas ocasiones (que, en general, no se podrán determinar a priori), encontrarán una solución (aceptablemente buena) en un tiempo razonable.
Area de Computación e Inteligencia Artificial 2Búsqueda heurística
n

n

n

En general, los métodos heurísticos son preferibles a los métodos no informados en la solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría un tiempo demasiado grande. Esto cubre prácticamente la totalidad de los problemas reales que interesan en Inteligencia Artificial. La información del problema concreto que estamos intentando resolver sesuele expresar por medio de heurísticas. El concepto de heurística es difícil de aprehender. Newell, Shaw y Simon en 1963 dieron la siguiente definición: "Un proceso que puede resolver un problema dado, pero que no ofrece ninguna garantía de que lo hará, se llama una heurística para ese problema".
Area de Computación e Inteligencia Artificial 3

Búsqueda heurística
n

Si nos planteamosseguir concretando como aprovechar la información sobre el problema en sistemas de producción, la siguiente idea consiste en concentrar toda la información heurística en una única función que se denomina función de evaluación heurística. Se trata de una función que asocia a cada estado del espacio de estados una cierta cantidad numérica que evalúa de algún modo lo prometedor que es ese estado paraacceder a un estado objetivo. Habitualmente, se denota esa función por h(e).

Area de Computación e Inteligencia Artificial

4

Función heurística
n

La función heurística puede tener dos interpretaciones. Por una parte, la función puede ser una estimación de lo próximo que se encuentra el estado de un estado objetivo. Bajo esta perspectiva, los estados de menor valor heurístico son lospreferidos. Pero en otros casos puede suceder que lo que convenga sea maximizar esa función.

Area de Computación e Inteligencia Artificial

5

Ejemplos de funciones heurísticas
n

Veamos ejemplos de heurísticas para algunos problemas concretos. Para el problema del 8-puzzle tenemos la siguientes heurísticas:
n

a) La basada en la distancia Manhattan (o distancia taxi). Se asocia a cadacasilla un número que es la suma de las distancias horizontal y vertical a su posición en el tablero objetivo (esto es, la suma de diferencias de sus coordenadas x e y). La función heurística es la suma de las distancias de cada una de las casillas (excluyendo la que se encuentra vacía).
2 1 8 7 6 3 4 5

Fig. 1

H(Ei)=2 (1 de la casilla 1 más 1 de la casilla 8)
Area de Computación eInteligencia Artificial 6

Ejemplos de funciones heurísticas
n

b) Otra heurística, mucho más simple, consiste en contar el número de casillas que están fuera de su sitio (respecto al tablero objetivo). Es una heurística más pobre que la anterior, puesto que no usa la información relativa al esfuerzo (número de movimientos) necesario para llevar una pieza a su lugar.

n

Ejercicio. Otraheurística posible para el 8-puzzle, si el estado objetivo es el recogido en la figura 1, es la siguiente: h(e) = 3 * seq(e), donde seq(e) cuenta 1 si hay un dígito central en e y 2 por cada dígito x no central que no es seguido (en el sentido de la agujas del reloj) por su sucesor x+1 (imponemos por convenio que 8 + 1 = 1).
n

Calcular el valor de esta heurística para los estados que aparecen en la...