- Funciones de evaluación heurística
- Ejemplo: El problema de las ocho reinas
- Propiedades de las funciones de evaluación heurística
- Bibliografía
Búsqueda Heurística
Los métodos de búsqueda heurísticas (del griego heuriskein, que significa encontrar) están orientados a reducir la cantidad de búsqueda requerida para encontrar una solución. Cuando un problema es presentado como un árbol de búsqueda el enfoque heurístico intenta reducir el tamaño del árbol cortando nodos pocos prometedores. Estos métodos se llaman métodos fuertes porque ellos son más poderosos que los estudiados hasta aquí al incorporar conocimiento heurístico o heurística. Hay una contradicción entre generalidad y potencia en el sentido que los métodos débiles son esencialmente aplicables universalmente mientras que los fuertes son menos universales en su aplicabilidad y el conocimiento o heurística usada en un problema dado puede no ser totalmente aplicable o ser inaplicable en otro dominio o tarea.
Feigenbaum y Feldman definen la heurística como sigue: "Una heurística es una regla para engañar, simplificar o para cualquier otra clase de ardid el cual limita drásticamente la búsqueda de soluciones en grandes espacios de estados". En esencia una heurística es simplemente un conjunto de reglas que evalúan la posibilidad de que una búsqueda va en la dirección correcta. Generalmente los métodos de búsqueda heurísticas se basan en maximizar o minimizar algunos aspectos del problema. Un ejemplo sencillo de heurística es el siguiente:
Un hombre se encuentra en una extensa llanura y tiene sed, en ese momento ha llegado a una pequeña elevación que es la única en esa región y se sube a ella. Desde la elevación el hombre observa el cuadro siguiente:
NORTE: vegetación verde y movimiento de animales
SUR: vegetación amarilla
ESTE: vegetación amarilla
OESTE: vegetación verde
Evidentemente la vegetación verde es un indicio de que hay humedad, luego es muy probable que exista agua en la superficie o subterránea. El movimiento de animales puede indicar que ellos se dirigen allí a beber, lo cual sugiere que el agua está en la superficie. Esta información le dice al hombre que debe dirigirse al norte, constituye una heurística.
La Heurística no garantiza que siempre se tome la dirección de la búsqueda correcta, por eso este enfoque no es óptimo sino suficientemente bueno. Frecuentemente son mejores los métodos heurísticos que los métodos de búsquedas a ciegas. Las desventajas y limitaciones principales de la heurística son:
La flexibilidad inherente de los métodos heurísticos pueden conducir a errores o a manipulaciones fraudulentas.
Ciertas heurísticas se pueden contradecir al aplicarse al mismo problema, lo cual genera confusión y hacen perder credibilidad a los métodos heurísticos.
Soluciones óptimas no son identificadas. Las mejoras locales determinadas por las heurísticas pueden cortar el camino a soluciones mejores por la falta de una perspectiva global. La brecha entre la solución óptima y una generada por heurística puede ser grande.
El significado técnico de la palabra heurística ha variado en la historia de la Inteligencia Artificial. En 1957, George Polya en su libro "How to solve it" usó este término para referirse al estudio de métodos para descubrir e inventar técnicas de solución de problemas.
En otras ocasiones se ha usado como un término opuesto a algorítmico. Por ejemplo, Newell, Shaw y Simón plantearon en 1993 "Un proceso que puede resolver un problema dado, pero no ofrece garantía de hacerlo, es llamado una heurística para ese problema".
Actualmente, la heurística es más frecuentemente usada como un adjetivo para referirse a cualquier técnica que mejore la media del proceso de solución de problemas.
Según Shapiro, uno de los resultados empíricos de los últimos treinta años de la Inteligencia Artificial es que para muchos problemas la relación (balance) entre conocimiento, tiempo de cálculo y calidad de la solución es bastante favorable. Es decir, el uso de una pequeña cantidad de conocimiento específico del problema puede mejorar significativamente la calidad de la solución o el costo del proceso de búsqueda.
Funciones de evaluación heurística
La calidad de un nodo (estado, situación) del espacio de búsqueda se puede estimar de varias formas:
Nivel de dificultad de resolver el subproblema representado por el nodo.
Página siguiente  |