INTRODUCCIÓN
En computación, dos objetivos fundamentales son encontrar algoritmos con buenos tiempos de ejecución y buenas soluciones, usualmente las óptimas. Una heurística es un algoritmo que abandona uno o ambos objetivos; por ejemplo, normalmente encuentran buenas soluciones, aunque no hay pruebas de que la solución no pueda ser arbitrariamente errónea en algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco prueba de que siempre será así. Las heurísticas generalmente son usadas cuando no existe una solución óptima bajo las restricciones dadas (tiempo, espacio, etc.), o cuando no existe del todo.
OBJETIVO
La siguiente clase tiene como objetivo entender que son las funciones heurísticas.
FUNCIONES HEURÍSTICAS
El coste medio de la solución para los casos generados al azar del 8-puzle son aproximadamente 22 pasos. El factor de ramificación es aproximadamente tres. (Cuando la ficha vacía está en el medio, hay cuatro movimientos posibles; cuando está en una es quina hay dos; y cuando está a lo largo de un borde hay tres.) Esto significa que una búsqueda exhaustiva a profundidad 22 miraría sobre 3^33 = 3,1 X 10^10 estados. Manteniendo la pista de los estados repetidos, podríamos reducirlo a un factor de aproximadamente 170.000, porque hay sólo 9 !/2 = 181.440 estados distintos que son alcanzables.
• h1 = número de piezas mal colocadas, las 8 piezas están fuera de su posición, así que el estado inicial tiene h1 = 8. h1 es una heurística admisible, porque está claro que cualquier pieza que está fuera de su lugar debe mover se por lo menos una vez.
• h2 = suma de las distancias de las piezas a sus posiciones en el objetivo. Como las piezas no pueden moverse en diagonal, la distancia que contaremos será la suma de las distancias horizontales y verticales. Esto se llama a veces la distancia en la ciudad o Distancia de Manhatta h2 es también admisible, porque cualquier movimiento que se puede hacer es mover una pieza un paso más cerca del objetivo. Las piezas 1 a 8 en el estado inicial nos dan una distancia de Manhattan de h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
Como era de esperar, ninguna sobrestima el coste solución verdadero, que es 26.
El efecto de la precisión heurística en el rendimiento
Inventar funciones heurísticas admisibles
A un problema con menos restricciones en las acciones se le llama problema relajado
Una ficha puede moverse del cuadrado A al cuadrado B si A es horizontalmente o verticalmente adyacente a B y B es la vacía.
Podemos generar tres problemas relajados quitando una o ambas condiciones:
(a) Una ficha puede moverse del cuadrado A al cuadrado B si A es adyacente a B.
h2
(b) Una ficha puede moverse del cuadrado A al cuadrado B si B es el vacío.
h2
(c) Una ficha puede moverse del cuadrado A al cuadrado B.
h1
CONCLUSIÓN
Las funciones heurísticas son funciones que busque el mejor camino para llegar a un resultado y podemos inventar a partir de las que tenemos definidas.
BIBLIOGRAFÍA
Zambrano, R. 2010. Funciones Heuristicas. (En línea). Disponible en: https://www.cs.us.es/cursos/ia1/temas/tema-04.pdf
Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.
