¿Cuál es la diferencia entre una heurística y un algoritmo?

¿Cuál es la diferencia entre una heurística y un algoritmo?

Un algoritmo es la descripción de una solución automatizada a un problema . Lo que hace el algoritmo está definido con precisión. La solución podría ser la mejor posible o no, pero usted sabe desde el principio qué tipo de resultado obtendrá. Implementas el algoritmo usando algún lenguaje de programación para obtener (una parte de) un programa .

Ahora, algunos problemas son difíciles y es posible que no pueda obtener una solución aceptable en un tiempo aceptable. En tales casos, a menudo puede obtener una solución no tan mala mucho más rápido, aplicando algunas opciones arbitrarias (conjeturas fundamentadas): eso es una heurística .

Una heurística sigue siendo una especie de algoritmo, pero uno que no explorará todos los estados posibles del problema, o comenzará por explorar los más probables.

Los ejemplos típicos son de juegos. Al escribir un programa de juego de ajedrez, podría imaginarse probando todos los movimientos posibles a algún nivel de profundidad y aplicando alguna función de evaluación al tablero. Una heurística excluiría las ramas completas que comienzan con movimientos obviamente malos.

En algunos casos, no está buscando la mejor solución, sino cualquier solución que se ajuste a alguna restricción. Una buena heurística ayudaría a encontrar una solución en poco tiempo, pero también puede fallar en encontrar ninguna si las únicas soluciones están en los estados que decidió no intentar.

• Un algoritmo es típicamente determinista y se ha demostrado que produce un resultado óptimo.
• Una heurística no tiene prueba de ser correcta, a menudo involucra elementos aleatorios y puede no producir resultados óptimos.

Muchos problemas para los que no se conoce ningún algoritmo eficiente para encontrar una solución óptima tienen enfoques heurísticos que producen resultados casi óptimos muy rápidamente.

Hay algunas superposiciones: "algoritmos genéticos" es un término aceptado, pero estrictamente hablando, son heurísticas, no algoritmos.

Heurístico, en pocas palabras, es una "suposición educada". Wikipedia lo explica muy bien. Al final, se toma un método de "aceptación general" como una solución óptima al problema especificado.

Heurística es un adjetivo para técnicas basadas en la experiencia que ayudan en la resolución de problemas, el aprendizaje y el descubrimiento. Se utiliza un método heurístico para llegar rápidamente a una solución que se espera esté cerca de la mejor respuesta posible, o "solución óptima". Las heurísticas son "reglas generales", conjeturas fundamentadas, juicios intuitivos o simplemente sentido común. Una heurística es una forma general de resolver un problema. La heurística como sustantivo es otro nombre para los métodos heurísticos.

En términos más precisos, la heurística se refiere a estrategias que utilizan información fácilmente accesible, aunque poco aplicable, para controlar la resolución de problemas en seres humanos y máquinas.

Mientras que un algoritmo es un método que contiene un conjunto finito de instrucciones que se utilizan para resolver un problema. Se ha demostrado que el método funciona matemáticamente o científicamente para resolver el problema. Hay métodos y pruebas formales.

El algoritmo heurístico es un algoritmo que es capaz de producir una solución aceptable a un problema en muchos escenarios prácticos, al estilo de una heurística general, pero para el cual no existe una prueba formal de su corrección.

Un algoritmo es un conjunto autónomo paso a paso de operaciones que se realizarán 4 , normalmente interpretado como una secuencia finita de instrucciones (informáticas o humanas) para determinar una solución a un problema como: ¿hay una ruta de A a B, o cuál es la ruta más pequeña entre A y B. En el último caso, también podría estar satisfecho con una solución alternativa "razonablemente cercana".

Hay ciertas categorías de algoritmos, de los cuales el algoritmo heurístico es uno. Dependiendo de las propiedades (probadas) del algoritmo en este caso, cae en una de estas tres categorías (nota 1):

• Exacto : se ha demostrado que la solución es óptima (osolución exacta ) al problema de entrada
• Aproximación : se ha demostrado que la desviación del valor de la solución nunca se aleja más del valor óptimo que un límite predefinido (por ejemplo, nunca más del 50% más grande que el valor óptimo)
• Heurística : no se ha demostrado que el algoritmo sea óptimo, ni dentro de un límite predefinido de la solución óptima.

Observe que un algoritmo de aproximación también es heurístico, pero con la propiedad más fuerte de que existe un vínculo probado a la solución (valor) que genera.

Para algunos problemas, nadie ha encontrado nunca un algoritmo "eficiente" para calcular las soluciones óptimas (nota 2). Uno de esos problemas es el conocido problema del viajante. El algoritmo de Christophides para el problema del vendedor ambulante, por ejemplo, solía llamarse heurístico , ya que no se probó que estuviera dentro del 50% de la solución óptima. Sin embargo, dado que se ha probado, el algoritmo de Christophides se conoce con mayor precisión como un algoritmo de aproximación.

Debido a las restricciones sobre lo que pueden hacer las computadoras, no siempre es posible encontrar de manera eficiente la mejor solución posible. Si hay suficiente estructura en un problema, puede haber una manera eficiente de atravesar el espacio de la solución, aunque el espacio de la solución sea enorme (es decir, en el problema de la ruta más corta).

La heurística se aplica típicamente para mejorar el tiempo de ejecución de los algoritmos, agregando 'información experta' o 'suposiciones fundamentadas' para guiar la dirección de búsqueda. En la práctica, una heurística también puede ser una subrutina de un algoritmo óptimo para determinar dónde buscar primero .

(nota 1) : Además, los algoritmos se caracterizan por si incluyen elementos aleatorios o no deterministas. Un algoritmo que siempre se ejecuta de la misma manera y produce la misma respuesta se llama determinista.

(nota 2) : Esto se denomina problema P vs NP, y es poco probable que los problemas clasificados como NP-completo y NP-difícil tengan un algoritmo "eficiente". Nota; como @Kriss mencionó en los comentarios, hay incluso tipos de problemas 'peores', que pueden necesitar tiempo o espacio exponencial para calcular.

Hay varias respuestas que responden parte de la pregunta. Los consideré menos completos y no lo suficientemente precisos, y decidí no editar la respuesta aceptada hecha por @Kriss

En realidad, no creo que haya mucho en común entre ellos. Algunos algoritmos usan heurísticas en su lógica (a menudo para hacer menos cálculos o obtener resultados más rápidos). Por lo general, las heurísticas se utilizan en los llamados algoritmos codiciosos.

La heurística es un "conocimiento" que asumimos que es bueno para usar con el fin de obtener la mejor opción en nuestro algoritmo (cuándo se debe tomar una decisión). Por ejemplo ... una heurística en el ajedrez podría ser (siempre toma la reina de los oponentes si puedes, ya que sabes que esta es la figura más fuerte). La heurística no le garantiza que lo llevará a la respuesta correcta, pero (si las suposiciones son correctas) a menudo obtiene respuestas cercanas a las mejores en un tiempo mucho más corto.

Las heurísticas son algoritmos, por lo que en ese sentido no hay ninguno, sin embargo, las heurísticas adoptan un enfoque de "conjetura" para la resolución de problemas, produciendo una respuesta "suficientemente buena", en lugar de encontrar la "mejor solución posible".

Un buen ejemplo es cuando tiene un problema muy difícil (lea NP-completo) para el que desea una solución pero no tiene tiempo para llegar a él, por lo que debe usar una solución suficientemente buena basada en un algoritmo heurístico, como encontrar una solución al problema de un viajante de comercio utilizando un algoritmo genético.

El algoritmo es una secuencia de algunas operaciones que, dada una entrada, calcula algo (una función) y genera un resultado.

El algoritmo puede producir valores exactos o aproximados.

También puede calcular un valor aleatorio con una alta probabilidad cercana al valor exacto.

Un algoritmo heurístico utiliza información sobre los valores de entrada y no calcula el valor exacto (pero puede estar cerca del óptimo). En algunos casos especiales, la heurística puede encontrar una solución exacta.

Un algoritmo es un conjunto de instrucciones claramente definidas para resolver un problema, la heurística implica utilizar un enfoque de aprendizaje y descubrimiento para llegar a una solución.

Entonces, si sabe cómo resolver un problema, utilice un algoritmo. Si necesita desarrollar una solución, entonces es heurística.

Una heurística suele ser una optimización o una estrategia que generalmente proporciona una respuesta suficientemente buena, pero no siempre y rara vez es la mejor respuesta. Por ejemplo, si tuviera que resolver el problema del vendedor ambulante con fuerza bruta, descartar una solución parcial una vez que su costo excede el de la mejor solución actual es una heurística: a veces ayuda, otras veces no, y definitivamente no lo hace. t mejorar el tiempo de ejecución teórico (notación de oh grande) del algoritmo

Creo que la heurística es más una restricción utilizada en el modelo basado en el aprendizaje en inteligencia artificial, ya que los estados de solución futuros son difíciles de predecir.

Pero entonces mi duda después de leer las respuestas anteriores es "¿Cómo se puede aplicar la heurística con éxito usando técnicas de optimización estocástica? ¿O pueden funcionar como algoritmos completos cuando se usan con optimización estocástica?"

http://en.wikipedia.org/wiki/Stochastic_optimization

Una de las mejores explicaciones que he leído proviene del gran libro Code Complete , que ahora cito:

Una heurística es una técnica que le ayuda a buscar una respuesta. Sus resultados están sujetos al azar porque una heurística le dice solo cómo buscar, no qué encontrar. No le dice cómo ir directamente del punto A al punto B; puede que ni siquiera sepa dónde están el punto A y el punto B. En efecto, una heurística es un algoritmo con traje de payaso. Es menos predecible, es más divertido y viene sin una garantía de devolución de dinero de 30 días.

Aquí hay un algoritmo para conducir hasta la casa de alguien: tome la autopista 167 hacia el sur hasta Puy-allup. Tome la salida de South Hill Mall y conduzca 4.5 millas cuesta arriba. Gire a la derecha en el semáforo de la tienda de comestibles y luego tome la primera a la izquierda. Gire en el camino de entrada de la gran casa bronceada a la izquierda, en 714 North Cedar.

Aquí tienes una heurística para llegar a la casa de alguien: busca la última carta que te enviamos. Conduzca hasta la ciudad en la dirección de retorno. Cuando llegues a la ciudad, pregúntale a alguien dónde está nuestra casa. Todos nos conocen, alguien estará encantado de ayudarlo. Si no puede encontrar a nadie, llámenos desde un teléfono público y lo buscaremos.

La diferencia entre un algoritmo y una heurística es sutil, y los dos términos se superponen un poco. Para los propósitos de este libro, la principal diferencia entre los dos es el nivel de desvío de la solución. Un algoritmo le da las instrucciones directamente. Una heurística le dice cómo descubrir las instrucciones por sí mismo, o al menos dónde buscarlas.

Encuentran una solución subóptima sin ninguna garantía en cuanto a la calidad de la solución encontrada, es obvio que tiene sentido para el desarrollo de heurísticas únicamente polinomiales. La aplicación de estos métodos es adecuada para resolver problemas del mundo real o grandes problemas tan incómodos desde el punto de vista computacional que para ellos ni siquiera existe un algoritmo capaz de encontrar una solución aproximada en tiempo polinomial.