En general, la heurística es una forma de priorizar ciertos caminos de cómputo sobre otros cuando se busca la solución de un problema.
Tu cómputo puede verse como la búsqueda de un camino desde el estado inicial de tu algoritmo hasta el estado final (donde se calcula la solución del problema). En ese camino, hay muchos estados internos y se pasa de uno a otro.
Ahora, ¿cómo saber qué camino elegir si hay múltiples opciones posibles de un estado a otros estados? Idealmente, te gustaría saber exactamente qué estado tienes que elegir para que todo el camino sea óptimo (y si tu algoritmo tiene la propiedad de óptimo local, entonces estás hecho). Pero muchas veces simplemente no lo sabes; estás dando tumbos a ciegas por el espacio de estados con la esperanza de encontrar el estado final, por así decirlo.
En tales situaciones, podrías optar por emplear la heurística. Es decir, eliges el siguiente estado basándote en alguna «conjetura», algún tipo de argumento con apoyo racional, que puede no ser siempre correcto, pero que generalmente aumentará la probabilidad de que te acerques al estado final.
Es difícil explicar la heurística en general, ya que los enfoques difieren bastante dependiendo del problema. Déjeme darle un ejemplo:
Problema del caballo de ajedrez: Dado un tablero de ajedrez de tamaño n por n y una posición inicial [p, q] en el tablero, encuentre un camino de la pieza del caballo a través del tablero de manera que visite cada campo exactamente una vez.
Ahora, tales problemas se resuelven a menudo utilizando el backtracking. Simplemente se movería el caballo, siguiendo un patrón fijo, marcando cada campo por el que pasa y recordando el camino que tomó. Si no puede pasar más allá, «descartas» el movimiento anterior y haces el siguiente en el patrón en su lugar. De este modo, al final probarás todos los caminos posibles. Algunos de ellos pueden ser soluciones válidas al problema.
Ahora, he implementado ese algoritmo en mi 1er año en la Universidad, hace unos 20 años. Lo ejecuté en mi PC 486; una máquina bastante lenta, pero como la cantidad de caminos posibles aumenta muy rápidamente con el aumento de las dimensiones del tablero de ajedrez, los resultados serán aproximadamente aplicables incluso hoy en día. Así, para un tablero de ajedrez de tamaño 5×5, la solución se encontró casi instantáneamente. 6×6, decenas de segundos, si recuerdo bien. 7×7, un par de horas, pero sí… 8×8-una noche y todavía no hay solución.
Así que, vamos a probar algunas heurísticas. El 1er intento que he probado ha sido el de intentar siempre la jugada a partir de la cual había el mayor número de movimientos posibles. Eso tiene sentido, ¿no? Iré donde tenga más posibilidades para continuar… Funcionó para el tablero de 8×8, la solución se encontró en media hora o algo así, pero incluso para el de 9×9, de nuevo, no hubo suerte de la noche a la mañana.
Entonces, probemos algo loco. Intentemos elegir la jugada a partir de la cual haya menos movimientos posibles. No tiene sentido, ¿verdad? Por qué debería preferir el camino que probablemente sea erróneo? Pues bien, resulta que esta heurística funciona brillantemente. En el 486, el tablero de 25×25 no supuso ningún problema, la primera solución se encontró en una fracción de segundo, las demás le siguieron muy rápidamente, el contador no paraba de correr…
¿Por qué? Bueno, al dirigir el caballo a los campos desde los que tenía el menor número de movimientos posibles, redujimos la anchura del subárbol de movimientos que podía hacer desde ese estado. Como la profundidad de ese árbol está limitada (por n veces n, el número de campos del tablero), el número de estados en ese subárbol disminuye rápidamente. Por lo tanto, probará un subárbol estrecho mucho más rápido que uno ancho. Si hay al menos una solución en ese subárbol estrecho, la encontrará rápidamente.
Así que lo que hicimos aquí fue: elegimos deliberadamente preferir ciertos cálculos (los que tienen menos cantidad de estados) frente a otros y los probamos primero. Igual llegábamos a los otros si no se encontraba la solución; al final, se habrían probado todos los caminos posibles. Pero si seleccionamos bien los movimientos locales, podemos evitar muchos callejones sin salida.
Y así es como funciona la heurística.