Algoritmo codicioso - Greedy algorithm

Los algoritmos codiciosos determinan la cantidad mínima de monedas para dar mientras se hace el cambio. Estos son los pasos que la mayoría de la gente tomaría para emular un algoritmo codicioso para representar 36 centavos usando solo monedas con valores {1, 5, 10, 20}. La moneda de mayor valor, menor que el cambio restante adeudado, es el óptimo local. (En general, el problema del cambio requiere una programación dinámica para encontrar una solución óptima; sin embargo, la mayoría de los sistemas monetarios, incluidos el euro y el dólar estadounidense, son casos especiales en los que la estrategia codiciosa encuentra una solución óptima).

Un algoritmo codicioso es cualquier algoritmo que sigue la heurística de resolución de problemas de tomar la decisión localmente óptima en cada etapa. En muchos problemas, una estrategia codiciosa no produce una solución óptima, pero una heurística codiciosa puede producir soluciones locales óptimas que se aproximan a una solución globalmente óptima en un período de tiempo razonable.

Por ejemplo, una estrategia codiciosa para el problema del vendedor ambulante (que es de alta complejidad computacional) es la siguiente heurística: "En cada paso del viaje, visite la ciudad no visitada más cercana". Esta heurística no pretende encontrar la mejor solución, pero termina en un número razonable de pasos; encontrar una solución óptima a un problema tan complejo requiere típicamente muchos pasos irrazonablemente. En la optimización matemática, los algoritmos codiciosos resuelven de manera óptima problemas combinatorios que tienen las propiedades de las matroides y dan aproximaciones de factor constante a los problemas de optimización con la estructura submodular.

Detalles específicos

En general, los algoritmos codiciosos tienen cinco componentes:

  1. Un conjunto de candidatos, a partir del cual se crea una solución.
  2. Una función de selección, que elige al mejor candidato para agregar a la solución.
  3. Una función de viabilidad, que se utiliza para determinar si un candidato puede utilizarse para contribuir a una solución.
  4. Una función objetivo, que asigna un valor a una solución, o una solución parcial, y
  5. Una función de solución, que indicará cuándo hemos descubierto una solución completa.

Los algoritmos codiciosos producen buenas soluciones en algunos problemas matemáticos , pero no en otros. La mayoría de los problemas para los que trabajan tendrán dos propiedades:

Propiedad de elección codiciosa
Podemos tomar la decisión que nos parezca mejor en este momento y luego resolver los subproblemas que surjan más tarde. La elección realizada por un algoritmo codicioso puede depender de las elecciones realizadas hasta ahora, pero no de las elecciones futuras o de todas las soluciones al subproblema. De manera iterativa, hace una elección codiciosa tras otra, reduciendo cada problema dado a uno más pequeño. En otras palabras, un algoritmo codicioso nunca reconsidera sus opciones. Ésta es la principal diferencia con la programación dinámica , que es exhaustiva y está garantizada para encontrar la solución. Después de cada etapa, la programación dinámica toma decisiones basadas en todas las decisiones tomadas en la etapa anterior y puede reconsiderar el camino algorítmico de la etapa anterior hacia la solución.
Subestructura óptima
"Un problema presenta una subestructura óptima si una solución óptima al problema contiene soluciones óptimas a los subproblemas".

Casos de fracaso

Ejemplos de cómo un algoritmo codicioso puede fallar en lograr la solución óptima.
A partir de A, un algoritmo codicioso que intenta encontrar el máximo siguiendo la pendiente más grande encontrará el máximo local en "m", ajeno al máximo global en "M".
Para alcanzar la suma más grande, en cada paso, el algoritmo codicioso elegirá lo que parece ser la opción inmediata óptima, por lo que elegirá 12 en lugar de 3 en el segundo paso, y no alcanzará la mejor solución, que contiene 99.

Los algoritmos codiciosos no logran producir la solución óptima para muchos otros problemas e incluso pueden producir la única peor solución posible . Un ejemplo es el problema del viajante de comercio mencionado anteriormente: para cada número de ciudades, hay una asignación de distancias entre las ciudades para las cuales la heurística del vecino más cercano produce el peor recorrido posible único. Para ver otros posibles ejemplos, consulte el efecto horizonte .

Tipos

Los algoritmos codiciosos se pueden caracterizar como "miopes" y también como "no recuperables". Son ideales solo para problemas que tienen una 'subestructura óptima'. A pesar de esto, para muchos problemas simples, los algoritmos más adecuados son codiciosos. Sin embargo, es importante tener en cuenta que el algoritmo codicioso se puede utilizar como un algoritmo de selección para priorizar opciones dentro de una búsqueda o un algoritmo de bifurcación y vinculación. Hay algunas variaciones del algoritmo codicioso:

  • Algoritmos codiciosos puros
  • Algoritmos codiciosos ortogonales
  • Algoritmos codiciosos relajados

Teoría

Los algoritmos codiciosos tienen una larga historia de estudio en optimización combinatoria e informática teórica . Se sabe que las heurísticas codiciosas producen resultados subóptimos en muchos problemas, por lo que las preguntas naturales son:

  • ¿Para qué problemas funcionan de manera óptima los algoritmos codiciosos?
  • ¿Para qué problemas garantizan los algoritmos codiciosos una solución aproximadamente óptima?
  • ¿Para qué problemas se garantiza que el algoritmo codicioso no producirá una solución óptima?

Existe una gran cantidad de literatura que responde a estas preguntas para clases generales de problemas, como matroids , así como para problemas específicos, como la cobertura de conjuntos .

Matroides

Una matroide es una estructura matemática que generaliza la noción de independencia lineal de espacios vectoriales a conjuntos arbitrarios. Si un problema de optimización tiene la estructura de un matroide, entonces el algoritmo codicioso apropiado lo resolverá de manera óptima.

Funciones submodulares

Una función definida en subconjuntos de un conjunto se llama submodular si para cada tenemos eso .

Supongamos que uno quiere encontrar un conjunto que maximice . El algoritmo codicioso, que construye un conjunto agregando incrementalmente el elemento que más aumenta en cada paso, produce como salida un conjunto que es al menos . Es decir, codicioso se desempeña dentro de un factor constante tan bueno como la solución óptima.

Se pueden demostrar garantías similares cuando se imponen restricciones adicionales, como restricciones de cardinalidad, en la salida, aunque a menudo se requieren ligeras variaciones en el algoritmo codicioso. Consulte para obtener una descripción general.

Otros problemas con las garantías

Otros problemas para los que el algoritmo codicioso ofrece una garantía sólida, pero no una solución óptima, incluyen

Muchos de estos problemas tienen límites inferiores coincidentes; es decir, el algoritmo codicioso no funciona mejor que la garantía en el peor de los casos.

Aplicaciones

Los algoritmos codiciosos generalmente (pero no siempre) no logran encontrar la solución óptima globalmente porque generalmente no operan de manera exhaustiva en todos los datos. Pueden comprometerse con ciertas opciones demasiado pronto, lo que les impide encontrar la mejor solución general más adelante. Por ejemplo, todos los algoritmos de coloración codiciosos conocidos para el problema de coloración de gráficos y todos los demás problemas NP-completos no encuentran consistentemente soluciones óptimas. Sin embargo, son útiles porque son rápidos de pensar y, a menudo, dan buenas aproximaciones al óptimo.

Si se puede demostrar que un algoritmo codicioso produce el óptimo global para una clase de problema determinada, normalmente se convierte en el método de elección porque es más rápido que otros métodos de optimización como la programación dinámica . Ejemplos de este tipo de algoritmos codiciosos son el algoritmo de Kruskal y el algoritmo de Prim para encontrar árboles de expansión mínima y el algoritmo para encontrar óptimos árboles de Huffman .

Los algoritmos codiciosos también aparecen en el enrutamiento de la red . Mediante el enrutamiento codicioso, se reenvía un mensaje al nodo vecino que está "más cerca" del destino. La noción de la ubicación de un nodo (y por lo tanto de "cercanía") puede estar determinada por su ubicación física, como en el enrutamiento geográfico utilizado por las redes ad hoc . La ubicación también puede ser una construcción completamente artificial como en el enrutamiento de mundo pequeño y la tabla hash distribuida .

Ejemplos de

Ver también

Referencias

Fuentes

enlaces externos