- 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  |