Heurística

¿Qué es la Heurísica?

Es la ciencia que estudia los procesos de decisión respecto a un campo de conocimiento concreto, como son las estrategias cognitivas. Su contrapartida formal en computación es el algoritmo. 

La palabra heurística proviene de la palabra griega heuriskein que significa descubrir, encontrar. Por heurística entendemos una estrategia, método, criterio o truco usado para hacer más sencilla la solución de problemas difíciles. El conocimiento heurístico es un tipo especial de conocimiento usado por los humanos para resolver problemas complejos. En este caso el adjetivo heurístico significa medio para descubrir.

Debido a la existencia de algunos problemas importantes con un gran interés práctico difíciles de resolver, comienzan a surgir algoritmos capaces de ofrecer posibles soluciones que aunque no consiguen el resultado óptimo, si que se acercan en un tiempo de cálculo razonable. Estos algoritmos están basados en el conocimiento heurístico y por lo tanto reciben el nombre de algoritmos heurísticos.

Por lo general, los algoritmos heurísticos encuentran buenas soluciones, aunque a veces no hay pruebas de que la solución pueda hallarse en un tiempo razonablemente corto o incluso de que no pueda ser errónea. Frecuentemente pueden encontrarse casos particulares del problema en los que la heurística obtendrá resultados muy malos o que tarde demasiado en encontrar una solución.

Un método heurístico es un conjunto de pasos que deben realizarse para identificar en el menor tiempo posible una solución de alta calidad para un determinado problema. 

Al principio esta forma de resolver problemas no fue bien vista en los círculos académicos, debido fundamentalmente a su escaso rigor matemático. Sin embargo, gracias a su interés práctico para solucionar problemas reales fue abriendo poco a poco las puertas de los métodos heurísticos, sobre todo a partir de los años 60. Actualmente las versiones matemáticas de métodos heurísticos están creciendo en su rango de aplicaciones, así como en su variedad de enfoques. 

Nuevas técnicas heurísticas son utilizadas a diario por científicos de computación, investigadores operativos y profesionales, para resolver problemas que antes eran demasiado complejos o grandes para las anteriores generaciones de este tipo de algoritmos. 

Ejemplo: Problema del Viajante

“Un vendedor tiene una lista de ciudades cada una de las cuales debe visitar solamente una vez; existen carreteras directas entre cada par de ciudades de la lista. Se debe encontrar la ruta que el vendedor debería seguir para que, siguiendo el camino más corto posible, visitara todas las ciudades, comenzando por cualquiera de ellas y volviendo a la misma."

Se puede resolver éste problema explorando el árbol de todos los caminos posibles y eligiendo aquél que tenga la longitud mínima; pero, si existen n ciudades, el número de caminos diferentes entre ellas es (n-1)!, esto significa que el tiempo requerido para resolver el problema es proporcional a n!.

Por lo tanto, si tenemos once ciudades, (11-1)! = 10*9*8*7*6*5*4*3*2*1 = 3, 628,000 rutas son posibles, es decir, se trata de un problema típico de combinatoria en el que es útil aplicar técnicas heurísticas.

Una técnica heurística de propósito general que es útil para resolver problemas combinatorios es el 'algoritmo del vecino más próximo': 

Paso 1. Seleccionar un nodo inicial.
Paso 2. Identificar al nodo más cercano al último agregado,

siempre que no haya sido agregado.
Paso 3. Repetir el paso 2 hasta incluir todos los nodos.

 

Fuente:

Revista: Hiperenciclopédica de divulgación del Saber

Segunda Época, Año IX

Vol. 8, Num. 2: Abril - Junio de 2014