Funciones Heurísticas

1.1.       INTRODUCCIÓN

Como ya conocemos la inteligencia artificial busca diseñar métodos de búsquedas que permitan encontrar una solución óptima a un problema, es por esto que Newell en el año de 1963 investigo sobre los diferentes tipos de procesos que existen para la resolución de un problema dando, así como resultado la inauguración del primer laboratorio de sistemas expertos dedicado a este tipo de problemas de búsquedas. La función heurística tiene como objetivo encontrar una posible solución a un problema haciendo uso de un conocimiento previo, siguiendo una secuencia de pasos que lo guíen hacia su meta.

A lo largo de esta publicación les daré a conocer que tipos de funciones heurísticas tenemos, como estas funcionan y cuál es el objetivo de las búsquedas informadas que hacen uso de esta función para encontrar una estrategia optima que lo guía hacia una posible solución.

1.2.       OBJETIVO 

Conocer cómo funcionan las funciones heurísticas y en qué tipos de problemas podemos aplicarlas.

MARCO TEÓRICO

Una vez que tenemos en claro que las búsquedas informadas son las más eficientes ya que estas proveen al agente de información previa para encontrar una solución de manera más rápida, tenemos que conocer que hace que este tipo de búsquedas se realizan y esto se debe gracias a la función heurística. 

2.1.       ¿Qué es la Función Heurística?

La función heurística se representa de la siguiente forma h(n), siendo esta función el costo estimado del camino más barato desde el nodo n hasta el nodo objetivo, dependiendo del tipo de búsqueda informada la función heurística se denotara de forma diferente, por ejemplo cuando tenemos un tipo de búsqueda voraz primero el mejor la función heurística será f(n) = h(n) mientras que si tenemos otro tipo de búsqueda por ejemplo búsqueda A* la función heurística será de la siguiente manera f(n) = g(n) + h(n).

Imagen 1: Problema de Puzzle 8

Uno de los primeros problemas en utilizar la función heurística fue el puzzle 8 un juego cuyo objetivo era de deslizar las piezas de manera horizontal y vertical a un espacio vació hasta que se consiga que las piezas queden en el orden establecido. En el puzzle 8 existen 181.440 debido a que el árbol de ramificación de este juego es de 3 debido a que si la ubicación es una esquina existen 2 posibles movimientos, si está en el centro existen 4 posibles movimientos y si se encuentra en el borde de una línea existen 3 posibles movimientos es por eso que se dice que la media será de 3. 

A diferencia del puzzle 8 existen otro tipo de problemas similares entre ellos tenemos al 15 puzzle el cual podemos ver tendrá una cantidad más grande de posibles resultados, pero ¿cómo llevaríamos a cabo un problema como estos? Tendremos que hacer de nuestra función heurística la cual como hemos mencionado es una estrategia para resolver problemas de manera óptima, una posible solución a este problema del 15 puzzle sería contando las piezas que se encuentren en la posición incorrecta y las distancias que tienen se suman hasta llegar a un nodo objetivo.

Imagen 2: Problema de Puzzle 15

2.1.            La Precisión De La Heurística En El Rendimiento

Para conocer si nuestra función heurística es la correcta es necesario evaluar el rendimiento de esta mediante un factor de ramificación eficaz, este factor puede variar según el tipo de problema que encontramos y generalmente es utilizado para problemas de búsquedas complejos, una función heurística adecuada seria aquella que tenga el valor de b* el cual es el factor de ramificación más cerca de uno.

2.2.       Inventar Funciones Heurísticas Admisibles.

Cuando encontramos un problema en donde no tenemos tantas restricciones que le permitan llegar a un estado objetivo se le conoce como un problema relajado, estos problemas cuentan con un costo para la función heurística admisible, en esta ocasión los problemas de 8 puzzle y el 15 puzzle no son de este tipo pese a que estos poseen demasiadas posibles soluciones para llegar a un estado objetivo y que estos cuentan con la restricción de que solo se pueden mover de manera vertical y horizontal dependiendo del espacio que se encuentre vacío.

2.3.       Absolver

Este programa fue diseñado con el fin de generar una función heurística a partir de un problema dado, gracias a este sistema se generó una función heurística para el problema del puzzle 8.

2.4.       Aprendizaje De Heurísticas Desde La Experiencia

Las funciones heurísticas son capaces de percatarse cual será el costo para llegar a una posible solución que comienza desde un nodo n, esto es una forma de aprender que se les presenta a este tipo de problemas ya que gracias a la experiencia que van adquiriendo en cada movimiento los acerca más a una solución óptima, el tipo de aprendizaje de este tipo de problemas heurísticos es inductivo porque solo evalúan el costo de la solución para los estados que pueden surgir a lo largo de la búsqueda de una posible solución. Un ejemplo que podría plantear para entender este tipo de problemas sería el de un agente que se encuentre extraviado y se encuentre un camino con tres posibles soluciones, esa sería una descripción, pero las características de los caminos posibles ya que esta serviría de mucha ayuda para determinar el camino objetivo, permitiéndole analizar la distancia desde donde se encuentra ubicado hasta el final del camino.

CONCLUSIONES
Como podemos comprobar una función heuristica es la que le permite a un agente determinar la secuencia de pasos para llegar a un estado aceptador, estas funciones son de suma importancia en los problemas de búsquedas informadas ya que gracias a estas se puede evaluar el costo de los movimientos de un estado n hacia el objetivo y ademas también del costo del camino.

BIBLIOGRAFIAS

Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España