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

Respuestas:

99

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.

kriss
fuente
3
Otro uso común de la heurística es la detección de virus, donde es posible que no esté seguro de que hay un virus, pero puede buscar atributos clave específicos de un virus.
Dana Holt
Heah, eso es cierto y para descifrar programas
streetparade
1
@kriss, entonces ... una heurística es una especie de algoritmo.
Pacerier
1
@Pacerier: sí. Es un algoritmo que ayuda a navegar en el espacio de solución de un problema en particular. También puede verlo como una estrategia para modificar un algoritmo para hacerlo práctico (un meta-algoritmo). Sigue siendo un algoritmo, todos los métodos lo son, y una heurística es definitivamente un método.
kriss
33
  • 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.

Michael Borgwardt
fuente
2
No diría que se ha demostrado que un algoritmo produce un resultado óptimo: depende del algoritmo con respecto a qué problema.
2016
Producir un resultado óptimo no es la cualidad esencial de los algoritmos, es la precisión, es decir, el resultado exacto, mientras que la heurística le proporciona resultados aproximados.
Marina Dunst
22

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.

Buhake Sindi
fuente
8

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

Joost
fuente
Creo que tu definición de la palabra algoritmo es demasiado restrictiva. ¿El uso de la secuencia de palabras implica no paralelismo? Los algoritmos paralelos están bien e incluso son habituales hoy en día. ¿Qué hay de resolver un problema usando una red neuronal? ¿O una herramienta de propagación de restricciones? Algoritmos ¿Meta-algoritmos?
kriss
El lector tiene la sensación de que los problemas de NP son peores. Eso es falso. Hay problemas realmente difíciles que necesitan algoritmos realmente malos, como exponenciales o peores. Los NP son especiales porque si tenemos una solución es fácil y rápido comprobarla, mientras que es muy difícil encontrarla si no la tenemos. Es fácil comprobar que tenemos las instrucciones correctas para salir de un laberinto, es mucho más difícil encontrar la salida. Por lo tanto, los NP son fáciles y difíciles si pudiéramos probar todas las soluciones posibles al mismo tiempo (de forma no determinista) resolverlo sería muy simple ... pero no podemos.
kriss
¡Gracias por la respuesta! Actualicé ligeramente la redacción y lo abordé de manera diferente. En mi opinión, la propagación de restricciones es una técnica para abordar algo, pero aún no es un algoritmo que describa cómo llegar paso a paso a la solución descrita en propagación de restricciones. Por supuesto, tiene razón sobre las clases de expspace y "peor", también he añadido una nota al respecto. Por cierto: escriba NP-Complete y / o NP-Hard en su totalidad, ya que el subconjunto de NP también contiene problemas que se pueden resolver 'eficientemente', que no son (se supone que son) de la misma clase.
Joost
Por supuesto que tienes razón, debería haber escrito NP-Complete. Culpa mía.
kriss
Es mucho mejor de lo que uno de mis colegas lo llama: NP-ness (que suena horrible y un poco asqueroso ...)
Joost
6

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.

anthares
fuente
4

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.

dsm
fuente
4

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.

Slava
fuente
3

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.

Lázaro
fuente
2

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

IVlad
fuente
2

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

A_tanA
fuente
¡Uy! error de ortografía debería ser "Inteligencia artificial"
A_tanA
2

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.

Edwin Dalorzo
fuente
Afirmar que existe una diferencia entre un algoritmo y una heurística es como afirmar que existe una diferencia entre un pájaro y un pollo. La heurística es un tipo de algoritmo.
Joost
0

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.

kafka
fuente