Explique la diferencia entre los algoritmos "escalar" y "codiciosos".¿Cuál es la diferencia entre los algoritmos de "escalada" y "codiciosos"?
Parece que ambos son similares, y tengo dudas de que "escalar" sea un algoritmo; parece ser una optimización. ¿Es esto correcto?
Los algoritmos de alpinismo y codiciosos son heurísticos que se pueden utilizar para problemas de optimización. En un problema de optimización , generalmente buscamos una combinación u orden óptima de elementos problemáticos. Una combinación dada u orden es una solución. En cualquier caso, se puede evaluar una solución para compararla con otras soluciones.
En una heurística montañosa, comienza con una solución inicial. Genera una o más soluciones vecinas. Elija lo mejor y continúe hasta que no haya mejores soluciones vecinas. Esto generalmente arrojará una solución. Al alpinismo, necesitamos saber cómo evaluar una solución y cómo generar un "vecino".
En una codiciosa heurística, necesitamos saber algo especial sobre el problema en cuestión. Un algoritmo codicioso usa información para producir una solución única.
Un buen ejemplo de un problema de optimización es una mochila 0-1. En este problema, hay una mochila con un cierto límite de peso, y un montón de artículos para poner en la mochila. Cada elemento tiene un peso y un valor. El objetivo es maximizar el valor de los objetos en la mochila mientras se mantiene el peso por debajo del límite.
Un algoritmo ambicioso elegirá objetos de mayor densidad y los colocará hasta que la mochila esté llena. Por ejemplo, en comparación con un ladrillo, un diamante tiene un alto valor y un peso pequeño, así que pondríamos el diamante primero.
Aquí es un ejemplo de que un algoritmo voraz fallaría: Digamos que tiene una mochila con capacidad de 100. Usted tiene los siguientes elementos:
el algoritmo codicioso pondría en el diamante y luego hacerse, dando un valor de 1000. Sin embargo, la solución óptima sería incluir las 5 monedas de oro, dando el valor 1050.
El algoritmo de alpinismo generaría una solución inicial: simplemente elija aleatoriamente algunos elementos (asegúrese de que están por debajo del límite de peso). Luego evalúe la solución, es decir, determine el valor. Genera una solución vecina.Por ejemplo, intente intercambiar un artículo por otro (asegúrese de que todavía está por debajo del límite de peso). Si esto tiene un valor más alto, use esta selección y comience nuevamente.
Hill climbing no es un algoritmo codicioso.
Sí, usted está en lo correcto. La escalada es una técnica general de optimización matemática (ver: http://en.wikipedia.org/wiki/Hill_climbing). Un algoritmo codicioso es cualquier algoritmo que simplemente escoge la mejor opción que ve en el momento y la toma.
Un ejemplo de esto es hacer cambios mientras se minimiza el número de monedas (al menos con USD). Aproveche al máximo la moneda de mayor valor, luego la mayor cantidad de la siguiente, hasta que alcance la cantidad necesaria.
De esta manera, la colina de la escalada es un algoritmo voraz.
Su conclusión puede ser engañosa. El algoritmo codicioso específico que describió construye la solución con avidez, mientras que la heurística de escalada alcanza a un optima local codiciosamente. La única diferencia es que el paso codicioso en el primero implica construir una solución, mientras que el paso codicioso en la escalada implica seleccionar un vecino (búsqueda local codicioso). La escalada es una heurística codiciosa. Si desea distinguir un algoritmo de una heurística, le sugiero que lea la respuesta de Mikola, que es más precisa. –