¿Cuál es la diferencia entre algoritmos y heurística?

Un algoritmo es una rutina que puede ejecutar para encontrar la solución correcta. Funcionará, siempre, y se ha demostrado que lo hace. Sin dudas, sin probabilidades, es la respuesta correcta.

Una heurística es una rutina que puede ejecutar que se aproximará a una solución. Son falibles. Pero, a menudo son mucho, mucho más rápidos que un algoritmo para encontrar lo mismo (si no lo fueran, simplemente usarías el algoritmo). A veces tienen una garantía sólida: la respuesta será casi igual o mayor que la respuesta verdadera, por ejemplo.

Para algunas tareas, una heurística puede ser “lo suficientemente buena”. Una heurística para resolver el problema del vendedor ambulante puede ser capaz de darle una buena ruta, incluso si no es la mejor opción. Otras veces, se puede usar una heurística como parte de otro algoritmo para mejorar su rendimiento. Un * pathfinding es un ejemplo clásico de esto, la heurística le permite adivinar en qué dirección es más probable que se dirija hacia su objetivo y enfocar su búsqueda en esa dirección. Todavía es un algoritmo, encontrará la respuesta correcta cada vez, pero normalmente puede hacerlo más rápido que un enfoque sin una heurística.

Por ejemplo, puede estimar la distancia de un punto dado a la meta calculando su distancia euclidiana al punto. No siempre es correcto, en términos de tiempo de viaje, porque puede que no haya una ruta directa, pero sabes que no puede tomar menos tiempo que eso. Si está tratando de trazar una ruta en un mapa, puede adivinar que el camino que lo lleva hacia el sur es mejor mirar para encontrar Florida que el que se dirige hacia el norte.

Un “algoritmo” es cualquier conjunto de reglas para hacer algo. Lo que quieres decir es un “algoritmo de solución”. Un “algoritmo de solución” garantiza una solución correcta. La “garantía” es la frase clave. El método de eliminación gaussiano que se enseña para resolver un sistema de ecuaciones lineales es un “algoritmo de solución”, ya que garantiza que siempre dará la respuesta correcta. Los algoritmos de solución a un problema pueden ser más rápidos o más lentos, pero todos tienen la misma garantía de ser correctos.

Un “heurístico” es un algoritmo que no garantiza una solución correcta. Una “buena” heurística es aquella que le dará la solución correcta o suficiente la mayor parte del tiempo. Las heurísticas se utilizan cuando no hay un algoritmo de solución conocido o si está interesado en algo más rápido que el algoritmo de solución conocido.

Imagina que ves un conjunto de cajas al otro lado de la habitación y tienes que adivinar cuál es el más pesado. Una heurística justa sería adivinar que la caja más grande es la más pesada. La verdadera respuesta se puede encontrar al pesar las cajas. Sin embargo, puede ser que pesar las cajas sea imposible o que no desee pasar el tiempo para pesar las cajas. En esos casos, usaría la heurística de adivinar que el más grande es el más pesado.

El punto clave sobre una heurística es que no hay forma de saber cuándo la solución que obtienes es incorrecta. Si lo hubiera, podría crear un bucle de autocorrección y obtener la solución correcta, y eso significaría que tiene un algoritmo de solución. Pero al igual que con las cajas, con solo mirarlas, nunca se sabe cuándo la más grande no es la más pesada. Con este heurístico de peso de caja, por lo general, y en muchas condiciones, estaría en lo cierto. Pero con solo mirarlos, nunca se puede saber cuándo el más grande está lleno de almohadas y el más pequeño está lleno de plomo. Nunca sabrías cuándo te equivocaste. Lo mejor que puede hacer en la práctica es hacer un estudio estadístico empírico de la situación típica y la respuesta típica que obtiene.

Tenga en cuenta que es diferente de un “algoritmo de solución aproximada” que garantiza que la solución es correcta hasta cierto punto. Pesar las cajas en una balanza barata es un algoritmo de solución aproximado. Adivinar su peso por su tamaño es una heurística.

Cuando se enfrenta a resolver conjuntos de ecuaciones no lineales, o resolver problemas de NP en general, o resolver problemas como el reconocimiento de caras que están demasiado mal definidos como para ser declarados formalmente como un problema de NP, la única forma de obtener una solución en la práctica es a través de heurística Entonces solo tienes que vivir con el hecho de que nunca sabrás cuándo estás lejos.

Vea la discusión de Herbert Simon y Allen Newell sobre la búsqueda heurística aquí para obtener una explicación intuitiva: Página en utexas.edu

Las heurísticas son una clase de algoritmos que no resuelven exactamente el problema, sino más bien una aproximación de una manera que es más simple que la solución verdadera más simple del problema.