algorithm - programacion - ¿Cuál es la diferencia entre una heurística y un algoritmo?
programacion heuristica investigacion operaciones (12)
¿Cuál es la diferencia entre una heurística y un algoritmo?
Algoritmo es una secuencia de algunas operaciones que da una entrada que computa algo (una función) y genera un resultado.
Algoritmo puede arrojar valores exactos o aproximados.
También puede calcular un valor aleatorio que tiene una alta probabilidad cerca del valor exacto.
Un algoritmo heurístico utiliza algunos conocimientos sobre los valores de entrada y calcula el valor no exacto (pero puede ser cercano al óptimo). En algunos casos especiales, la heurística puede encontrar la solución exacta.
Creo que Heuristic es más una restricción utilizada en Learning Based Model en Artificial Intelligent ya que los futuros estados de solución son difíciles de predecir.
Pero luego, después de leer las respuestas anteriores, mi duda es "¿Cómo se puede aplicar heurísticamente con éxito las técnicas de optimización estocástica ?, ¿o pueden funcionar como algoritmos completos cuando se utilizan con la optimización estocástica?"
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 algo de "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.
Encuentran una solución suboptimally sin ninguna garantía en cuanto a la calidad de la solución encontrada, es obvio que tiene sentido para el desarrollo de heurística solo polinomio. 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.
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ística es un adjetivo para técnicas basadas en la experiencia que ayudan a resolver problemas, aprender y descubrir. Se utiliza un método heurístico para llegar rápidamente a una solución que se espera que esté cerca de la mejor respuesta posible, 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. La heurística como nombre es otro nombre para los métodos heurísticos.
En términos más precisos, las heurísticas representan estrategias que utilizan información fácilmente accesible, aunque vagamente 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 usadas 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, a la manera de una heurística general, pero para la cual no hay una prueba formal de su corrección.
Los heurísticos son algoritmos, por lo que en ese sentido no hay ninguno, sin embargo, los heurísticos adoptan un enfoque ''adivinar'' para la resolución de problemas, produciendo una respuesta ''suficientemente buena'', en lugar de encontrar la solución ''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, por lo que debe usar una solución lo suficientemente buena basada en un algoritmo heurístico, como encontrar una solución a un problema de vendedor ambulante usando un algoritmo genético.
Un algoritmo es un conjunto de operaciones autónomo paso a paso que se realizará 4 , generalmente interpretado como una secuencia finita de instrucciones (informáticas o humanas) para determinar una solución a un problema como: ¿hay un camino desde A hasta B, o cuál es la ruta más pequeña entre A y B. En este ú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):
- Exact : la solución ha demostrado ser una solución óptima (o exacta ) para el problema de entrada
- Approximation : se ha demostrado que la desviación del valor de la solución nunca está más alejada del valor óptimo que un límite predefinido (por ejemplo, nunca más de un 50% más grande que el valor óptimo)
- Heuristic : no se ha demostrado que el algoritmo sea óptimo, ni dentro de un límite predefinido de la solución óptima
Tenga en cuenta que un algoritmo de aproximación también es una heurística, pero con la propiedad más sólida de que existe una conexión comprobada 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 comprobó 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 las restricciones sobre lo que las computadoras pueden hacer, 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 solución sea enorme (es decir, en el problema de ruta más corta).
La heurística generalmente se aplica 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 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 conoce como el problema P vs NP, y es poco probable que los problemas clasificados como NP-complete y NP-hard 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 parte de la pregunta. Los consideré menos completos y no lo suficientemente precisos, y decidí no editar la respuesta aceptada hecha por @Kriss
Un algoritmo es la descripción de una solución automatizada 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 un 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 educadas): eso es una heurística .
Una heurística sigue siendo una especie de algoritmo, pero que no explorará todos los posibles estados del problema, o comenzará explorando 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, 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 podría no encontrarla si las únicas soluciones están en los estados que decidió no probar.
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.
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 te ayuda a buscar una respuesta. Sus resultados están sujetos al azar porque una heurística te dice solo cómo mirar, no qué buscar. No te dice cómo llegar directamente del punto A al punto B; es posible que ni siquiera sepa dónde están el punto A y el 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 autopista 167 en dirección sur hacia Puy-allup. Tome la salida South Hill Mall y conduzca 4.5 millas cuesta arriba. Gire a la derecha en la luz de la tienda de comestibles, y luego tome la primera a la izquierda. Gire en el camino de entrada de la casa tan grande a la izquierda, en 714 North Cedar.
Aquí hay una heurística para llegar a la casa de alguien: encuentre la última carta que le enviamos por correo. Conduce a la ciudad en la dirección del remitente. Cuando llegues a la ciudad, pregúntale a alguien dónde está nuestra casa. Todos nos conocen, alguien estará encantado de ayudarte. Si no puede encontrar a nadie, llámenos desde un teléfono público, e iremos a buscarlo.
La diferencia entre un algoritmo y una heurística es sutil, y los dos términos se superponen algo. A los fines de este libro, la principal diferencia entre los dos es el nivel de indirección de la solución. Un algoritmo te da las instrucciones directamente. Una heurística te dice cómo descubrir las instrucciones por ti mismo, o al menos dónde buscarlas.
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 Mejora el tiempo de ejecución teórico (notación big-oh) del algoritmo
- Un algoritmo es típicamente determinista y probado para producir un resultado óptimo
- Una heurística no tiene ninguna prueba de corrección, a menudo incluye 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.
Hay algunas superposiciones: "algoritmos genéticos" es un término aceptado, pero estrictamente hablando, esos son heurísticos, no algoritmos.