Objetivo temático
Al finalizar la unidad el alumno entenderá el concepto de Búsqueda Heurística y lo aplicará a la resolución de problemas.
Porqué los métodos heurísticos? Por que aunque en un principio se pensó que toda tarea de búsqueda podía ser completada por un computador sin mas que realizar una exploración de todos los caminos que llevan a una solución y una posterior selección del mejor de tales caminos, mas tarde se comprobó que aunque esta suposición era cierta, no era eficaz debido a la explosión combinatoria que aparece en este tipo de problemas.
Los procesos de búsqueda son muy tardados debido a la gran cantidad de combinaciones que se tienen que realizar.
NOTA: En la unidad anterior se vio que es un problema exponencial. Un ejemplo es el juego de las fichas de números (8 puzzle) donde el espacio de estados para este problema es de 9!, es decir 362,880 estados o configuraciones distintas.
Búsqueda Heurística
El conocimiento dependiente del dominio puede ayudar a dirigir el proceso de búsqueda de manera que sean exploraras en primer lugar aquellas trayectorias que parecen más prometedoras a la hora de conducir a un estado solución. La búsqueda inspirada en el razonamiento anterior se denomina heurística.
La eficiencia en la búsqueda puede mejorar si existe una forma de ordenar las selecciones de modo que las más prometedoras se exploren primero. Una forma de ordenarlas es incorporando heurísticas.
En IA se considera la heurística como una técnica que aumenta la eficiencia en un proceso de búsqueda.
Metodología: la principal diferencia entre este tipo de búsqueda respecto a la que no emplea información del dominio (búsqueda exhaustiva) es que ahora a cada nodo se le va a poder asociar un valor que dará idea de lo cerca que se encuentra de un nodo meta. Evidentemente ese valor no será mas que una estimación de la distancia real a la meta.
Ventajas de los métodos:
Los métodos heurísticos no garantizan hallar la solución optima a un problema, pero permiten, de una manera más eficiente desde el punto de vista computacional, aproximarse a tal solución.
2. Normalmente no se necesita una solución óptima, con frecuencia una buena aproximación es adecuada.
3. El intentar comprender porqué funciona una heurística sirve para comprender mejor el problema
Desventajas de los métodos:
1. Probablemente no considere la mejor ruta. Al hablar de heurística estamos hablando de algo probable y no de algo cien por ciento seguro.
2. Es difícil encontrar la heurística adecuada. Las heurísticas se tienen que definir dependiendo del problema que estamos tratando de resolver, a veces los problemas son tan complejos que es difícil encontrar la heurística adecuada.
Al finalizar la unidad el alumno entenderá el concepto de Búsqueda Heurística y lo aplicará a la resolución de problemas.
Porqué los métodos heurísticos? Por que aunque en un principio se pensó que toda tarea de búsqueda podía ser completada por un computador sin mas que realizar una exploración de todos los caminos que llevan a una solución y una posterior selección del mejor de tales caminos, mas tarde se comprobó que aunque esta suposición era cierta, no era eficaz debido a la explosión combinatoria que aparece en este tipo de problemas.
Los procesos de búsqueda son muy tardados debido a la gran cantidad de combinaciones que se tienen que realizar.
NOTA: En la unidad anterior se vio que es un problema exponencial. Un ejemplo es el juego de las fichas de números (8 puzzle) donde el espacio de estados para este problema es de 9!, es decir 362,880 estados o configuraciones distintas.
Búsqueda Heurística
El conocimiento dependiente del dominio puede ayudar a dirigir el proceso de búsqueda de manera que sean exploraras en primer lugar aquellas trayectorias que parecen más prometedoras a la hora de conducir a un estado solución. La búsqueda inspirada en el razonamiento anterior se denomina heurística.
La eficiencia en la búsqueda puede mejorar si existe una forma de ordenar las selecciones de modo que las más prometedoras se exploren primero. Una forma de ordenarlas es incorporando heurísticas.
En IA se considera la heurística como una técnica que aumenta la eficiencia en un proceso de búsqueda.
Metodología: la principal diferencia entre este tipo de búsqueda respecto a la que no emplea información del dominio (búsqueda exhaustiva) es que ahora a cada nodo se le va a poder asociar un valor que dará idea de lo cerca que se encuentra de un nodo meta. Evidentemente ese valor no será mas que una estimación de la distancia real a la meta.
Ventajas de los métodos:
Los métodos heurísticos no garantizan hallar la solución optima a un problema, pero permiten, de una manera más eficiente desde el punto de vista computacional, aproximarse a tal solución.
2. Normalmente no se necesita una solución óptima, con frecuencia una buena aproximación es adecuada.
3. El intentar comprender porqué funciona una heurística sirve para comprender mejor el problema
Desventajas de los métodos:
1. Probablemente no considere la mejor ruta. Al hablar de heurística estamos hablando de algo probable y no de algo cien por ciento seguro.
2. Es difícil encontrar la heurística adecuada. Las heurísticas se tienen que definir dependiendo del problema que estamos tratando de resolver, a veces los problemas son tan complejos que es difícil encontrar la heurística adecuada.
No hay comentarios:
Publicar un comentario