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

Question

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

Answer 1

Un algoritmo es la descripción de una solución automática para un problema. Lo que hace el algoritmo está definido con precisión. La solución podría ser o no la mejor posible, pero desde el principio se sabe qué tipo de resultado obtendrá. Implementa 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 demasiado mala mucho más rápido, mediante la aplicación de algunas opciones arbitrarias (conjeturas): es heurística.

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

Ejemplos típicos son de juegos. Al escribir un juego de ajedrez, podría imaginarse intentar todos los movimientos posibles en algún nivel de profundidad y aplicar alguna función de evaluación al tablero. Una heurística excluiría ramas completas que comiencen con movimientos obviamente malos.

En algunos casos no está buscando la mejor solución, pero para 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 podría no encontrarla si las únicas soluciones están en los estados que decidió no probar.

Answer 2

En realidad, no creo que haya mucho en común entre ellos. Algún algoritmo usa heurística en su lógica (a menudo para hacer menos cálculos u obtener resultados más rápidos). Por lo general, la heurística se usa en los llamados algoritmos codiciosos.

La heurística es un "conocimiento" que suponemos que es bueno usar para obtener la mejor opción en nuestro algoritmo (cuando 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 lleve a la respuesta correcta, pero (si las suposiciones son correctas) a menudo recibe una respuesta que se acerca a la mejor en mucho menos tiempo.

Answer 3

• Un algoritmo es típicamente determinista y probada para producir un resultado óptimo
• Una heurística no tiene ninguna prueba de la corrección, a menudo implica elementos aleatorios, y puede no dar resultados óptimos.

Muchos problemas para los cuales 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.

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

Answer 4

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

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

En términos más precisos, la heurística soporte para las estrategias que utilizan fácilmente accesible , aunque sin apretar aplicable, información para controlar la resolución de de seres humanos y máquinas problema.

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

algoritmo heurístico es un algoritmo que es capaz de producir una solución aceptable a un problema en muchos escenarios prácticos, en el la moda de una heurística general, pero para el que no hay ninguna prueba formal de es correcto.

Answer 5

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

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

Answer 6

Una heurística suele ser una optimización o una estrategia que generalmente proporciona una respuesta lo suficientemente buena, pero no siempre y rara vez la mejor respuesta. Por ejemplo, si resolvieras el problema del vendedor ambulante con la 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 funciona. t mejorar el tiempo de ejecución teórico (notación big-oh) del algoritmo

Answer 7

Las heurísticas son algoritmos, por lo que en ese sentido no hay ninguno, sin embargo, la heurística adopta un enfoque 'adivinar' para resolver problemas, produciendo un 'suficientemente bueno' respuesta, en lugar de encontrar una solución "lo mejor 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 el tiempo para llegar a ella, entonces tiene que usar una solución suficientemente buena basada en una heurística Algoritmo, como encontrar una solución a un problema de vendedor ambulante utilizando un algoritmo genético.

Answer 8

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

Algoritmo puede arrojar valores exactos o aproximados.

También puede calcular un valor aleatorio que tenga una alta probabilidad cerca del valor exacto.

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

Answer 9

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

Pero entonces mi duda después de leer por encima de respuestas es "¿Cómo heurístico puede ser aplicado con éxito utilizando técnicas de optimización estocástica? O pueden funcionar como algoritmos de pleno derecho cuando se utiliza con optimización estocástica?"

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

Answer 10

Ellos 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 la heurística única polinómicas. 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 hay un algoritmo capaz de encontrar una solución aproximada en tiempo polinomial.

Answer 11

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

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

Aquí hay un algoritmo para conducir a la casa de alguien: tome la carretera 167 hacia el sur hasta Puy-allup. Tome la salida de South Hill Mall y conduzca 4.5 millas al cuesta arriba. Gire a la derecha en la luz de la tienda de comestibles, y luego gire a la izquierda. Gire en el camino de entrada de la casa tan grande en a la izquierda, en 714 North Cedar.

Aquí hay una heurística para llegar a la casa de alguien: encuentre la última carta de que le enviamos por correo. Conduce a la ciudad en la dirección del remitente. Cuando llegue a la ciudad, pregúntele a alguien dónde está nuestra casa. Todo el mundo sabe nosotros, alguien estará encantado de ayudarle. Si no puede encontrar a nadie, llámenos al desde un teléfono público, e iremos a buscarlo.

La diferencia entre un algoritmo y una heurística es sutil, y el dos términos se superponen algo. A los fines de este libro, la diferencia principal entre los dos es el nivel de direccionamiento indirecto de la solución . Un algoritmo te da las instrucciones directamente. Una heurística le indica cómo descubrir las instrucciones, o al menos dónde buscarlas.

Answer 12

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

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

• Exact: la solución ha demostrado ser un óptimo (o exacta solución) al problema de entrada
• Approximation: la desviación del valor de la solución no está nunca más lejos del valor óptimo que un límite predefinido (por ejemplo, nunca más del 50% mayor que el valor óptimo))
• Heuristic: el algoritmo no ha demostrado ser óptima, ni dentro de un pre-definido fijado de la solución óptima

en cuenta que un algoritmo de aproximación es también una heurística, pero con la propiedad más fuerte que existe una probado vinculado a la solución (valor) que genera.

Para algunos problemas, nadie ha encontrado un algoritmo "eficiente" para calcular las soluciones óptimas (nota 2). Uno de esos problemas es el conocido Problema de Vendedor Viajero. El algoritmo de Christophides para el Problema del Viajero Vendedor, por ejemplo, solía llamarse heurística, ya que no se demostró que estuviera dentro del 50% de la solución óptima. Sin embargo, como se ha demostrado, el algoritmo de Christophides se conoce con más precisión como un algoritmo de aproximación.

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

Las heurísticas se suelen aplicar para mejorar el tiempo de ejecución de los algoritmos, al agregar 'información experta' o 'conjeturas fundamentadas' para guiar la dirección de búsqueda. En la práctica, una heurística también puede ser una sub-rutina para un algoritmo óptimo, para determinar dónde mirar primero.

(nota 1): Además, los algoritmos se caracterizan por incluir 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 conoce como el problema P vs NP, y los problemas que se clasifican como NP-completo y NP-difícil es poco probable que tengan un algoritmo "eficiente". Nota; como se menciona en los comentarios de @Kriss, incluso hay "peores" tipos de problemas, que pueden requerir tiempo exponencial o espacio para computar.

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