¿Cuál es la diferencia entre una heurística y un algoritmo?
https://stackoverflow.com/questions/2334225
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cuál es la diferencia entre una heurística y un algoritmo?
Solución
Un algoritmo es la descripción de una solución automatizado a un problema . Lo que hace el algoritmo se define con precisión. La solución podría o no podría ser la mejor posible, sino que saber desde el principio qué tipo de resultado que se obtendrá. Implementar el algoritmo utilizando algún lenguaje de programación para obtener (una parte de) una programa .
Ahora, algunos problemas son difíciles y es posible que no sea capaz de conseguir una solución aceptable en un tiempo aceptable. En tales casos, a menudo se puede obtener un no demasiado mala solución mucho más rápida, mediante la aplicación de algunas decisiones arbitrarias (conjeturas):. Eso es un heurística
Una heurística es todavía una especie de un algoritmo, pero que no va a explorar todos los estados posibles del problema, o se iniciará mediante la exploración de las más probables.
Ejemplos típicos son de juegos. Al escribir un programa de juego de ajedrez que podía imaginar que intenta cada movimiento posible en algún nivel de profundidad y aplicar alguna función de evaluación de la junta. Una heurística excluiría las ramas llenas que comienzan con obviamente malas jugadas.
En algunos casos usted no está buscando la mejor solución, pero para cualquier solución ajustada algún tipo de restricción. Una buena heurística ayudaría a encontrar una solución en un corto tiempo, pero también puede no encontrar ninguna, si las únicas soluciones están en los estados que eligió para no intentarlo.
Otros consejos
- 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 de los problemas para los cuales hay un algoritmo eficiente para encontrar una solución óptima que se sabe tienen heurístico acerca de que los resultados de rendimiento casi óptimas muy rápidamente.
Hay algunas coincidencias: "algoritmos genéticos" es un término aceptado, pero estrictamente hablando, esos heurísticos son, no por algoritmos
.heurístico, en pocas palabras es una "conjetura". Wikipedia lo explica muy bien. Al final, un método de "aceptación general" se toma como una solución óptima al problema especificado.
heurístico es un adjetivo para técnicas basadas en la experiencia que ayuda en la resolución de problemas, el aprendizaje y descubrimiento. Se utiliza un método heurístico para rápidamente llegar a una solución que es la esperanza de estar cerca de la mejor manera posible respuesta, o 'solución óptima'. Heurísticas son "reglas de oro", conjeturas, juicios intuitivos o simplemente sentido común. Una heurística es una forma general de la solución de un problema. Heurística como un sustantivo es otro nombre por métodos heurísticos.
En términos más precisos, heurísticas presentarse a las estrategias que utilizan con facilidad accesibles, aunque sin apretar aplicable, información para el control de la resolución de problemas de seres humanos y máquinas.
Mientras que un algoritmo es un método que contiene conjunto finito de instrucciones que se utilizan para resolver un problema. El método se ha demostrado matemáticamente o científicamente al trabajo para el problema. Hay métodos formales y pruebas.
heurístico algoritmo es un algoritmo que es capaz de producir una solución aceptable para un problema de muchos escenarios prácticos, en el la moda de una heurística general, pero para los que no hay ninguna prueba formal de su corrección.
En realidad no creo que hay mucho en común entre ellos. Algunos utilizan la heurística algoritmo en su lógica (a menudo para hacer menos cálculos o conseguir resultados más rápidos). Por lo general, la heurística se utilizan en los llamados algoritmos codiciosos.
La heurística es un "conocimiento" que suponemos es bueno para su uso con el fin de obtener la mejor elección en nuestro algoritmo (cuando una elección debe ser tomado). Por ejemplo ... una heurística en el ajedrez podría ser (siempre toman la reina de los oponentes si es posible, ya que se sabe que esto es la figura más fuerte). Heurística no le garantizan que le llevará a la respuesta correcta, pero (si las suposiciones son correctas) consiguen a menudo respuesta que están cerca de los mejores de tiempo mucho más corto.
Un algoritmo Es un conjunto autónomo de operaciones paso a paso que se deben realizar. 4, típicamente interpretado como una secuencia finita de instrucciones (computadoras o humanas) para determinar una solución a un problema como:¿Existe 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 conformarse 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, cae en una de estas tres categorías (nota 1):
- Exacto:Se ha demostrado que la solución es óptima (o exacto solución) al problema de entrada
- Aproximación:Se ha demostrado que la desviación del valor de la solución nunca está más alejada del valor óptimo que algún límite predefinido (por ejemplo, nunca más de un 50 % mayor que el valor óptimo).
- Heurístico:No se ha demostrado que el algoritmo sea óptimo, ni esté dentro de un límite predefinido de la solución óptima.
Observe que un algoritmo de aproximación también es una heurística, pero con la propiedad más fuerte de que existe un límite comprobado para 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 viajante, por ejemplo, solía denominarse heurístico, al no comprobarse que estuviera dentro del 50% de la solución óptima.Sin embargo, como está demostrado, el algoritmo de Christophides se denomina más exactamente algoritmo de aproximación.
Debido a las restricciones sobre lo que pueden hacer las computadoras, no siempre es posible eficientemente encuentra el mejor solución 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 la solución sea enorme (es decir,en el problema del camino más corto).
Las heurísticas se suelen aplicar para mejorar el tiempo de ejecución de los algoritmos, añadiendo "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 subrutina para un algoritmo óptimo, para determinar dónde buscar. 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 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 calcularse.
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 de @Kriss.
La heurística son algoritmos, así que en ese sentido no la hay, sin embargo, la heurística adoptar un enfoque 'adivinar' a la resolución de problemas, produciendo una suficientemente buena respuesta, en lugar de encontrar un 'mejor posible' solución.
Un ejemplo bueno es donde se tiene una muy difícil (léase NP-completo) problema que desea una solución para, pero no tienen el tiempo para llegar a ella, por lo que tiene que utilizar una solución lo suficientemente buena basado en un algoritmo heurístico , tales como la búsqueda de una solución a un problema del viajante usando un algoritmo genético.
algoritmo es una secuencia de algunas operaciones que, dada una computa de entrada algo (una función) y da salida a un resultado.
algoritmo puede producir un valores exactos o aproximados.
También puede calcular un valor aleatorio que es con alta probabilidad cerca del valor exacto.
A algoritmo heurístico utiliza una cierta penetración en valores de entrada y no calcula el valor exacto (pero puede estar cerca de óptima). En algunos casos especiales, heurística puede encontrar solución exacta.
Un algoritmo es un conjunto claramente definido de instrucciones para resolver un problema, Heurística implican la utilización de un enfoque de aprendizaje y descubrimiento para llegar a una solución.
Por lo tanto, si usted sabe cómo resolver un problema, entonces utilizar un algoritmo. Si es necesario desarrollar una solución entonces es heurística.
Una heurística es por lo general una optimización o una estrategia que por lo general proporciona una respuesta bastante buena, pero no siempre y rara vez la mejor respuesta. Por ejemplo, si se va a resolver el problema del viajante con la fuerza bruta, descartando una solución parcial una vez que su coste es superior al de la mejor solución actual es una heurística: a veces ayuda, otras veces no lo hace, y que sin duda doesn' t mejorar el (oh gran notación) tiempo teórico de ejecución del algoritmo
Creo heurístico es un factor más limitante utilizado en Aprendizaje Basado en Modelos en Inteligencia Artificial desde los estados de solución futuro son difíciles de predecir.
Pero entonces mi duda después de leer por encima de respuestas es "¿Cómo heurístico se puede aplicar 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?"
Una de las mejores explicaciones que he leído proviene de la gran libro código completo , que ahora cito:
Una heurística es una técnica que le ayuda a buscar una respuesta. Sus Los resultados están sujetos a la casualidad ya que una heurística sólo dice cómo a ver, no lo que encontrar. No te dice cómo llegar directamente desde el punto A al punto B; que ni siquiera podría saber dónde el punto A y punto B son. En efecto, una heurística es un algoritmo en un traje de payaso. Es menos predecibles, que es más divertido, y se trata sin 30 días, la garantía de devolución.
Aquí es un algoritmo para conducir a la casa de alguien: tomar la autopista 167 al sur de Puy-Allup. Tomar la salida South Hill Mall y conducir 4.5 millas hasta la colina. Gire a la derecha en el semáforo por la tienda de comestibles, y luego tomar la primera a la izquierda. Convertirse en el camino de entrada de la casa grande bronceado en la izquierda, en 714 Cedar Norte.
Aquí hay una heurística para llegar a la casa de alguien: Encontrar el último carta que le enviamos por correo. Conducir a la ciudad en la dirección de retorno. Cuando se llega a la ciudad, pregunta a alguien en nuestra casa es. Todo el mundo sabe nosotros, alguien estará encantado de ayudarle. Si no puede encontrar a nadie, llámenos desde un teléfono público, y vamos a buscarte.
La diferencia entre un algoritmo y una heurística es sutil, y el dos términos más vueltas un poco. Para los propósitos de este libro, el principal diferencia entre los dos es el nivel de indirección de la solución. Un algoritmo que da las instrucciones directamente. UNA heurística te dice cómo descubrir las instrucciones para usted mismo, o al menos dónde buscar para ellos.
Se encontró 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 adecuado para resolver los problemas del mundo real o grandes problemas tan difíciles desde el punto de vista computacional que para ellos no hay ni siquiera un algoritmo capaz de encontrar una solución aproximada en tiempo polinómico.
