stringtranslate.com

Algoritmo codicioso

Los algoritmos codiciosos determinan la cantidad mínima de monedas que se deben dar al dar el cambio. Estos son los pasos que la mayoría de las personas seguirían para emular un algoritmo codicioso que represente 36 centavos utilizando solo monedas con valores {1, 5, 10, 20}. La moneda de mayor valor, menor que el cambio restante que se debe, es el óptimo local. (En general, el problema de dar el cambio requiere programación dinámica para encontrar una solución óptima; sin embargo, la mayoría de los sistemas monetarios son casos especiales en los que la estrategia codiciosa sí 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. [1] En muchos problemas, una estrategia codiciosa no produce una solución óptima, pero una heurística codiciosa puede producir soluciones localmente óptimas que se aproximan a una solución globalmente óptima en un tiempo razonable.

Por ejemplo, una estrategia voraz para el problema del viajante de comercio (que es de alta complejidad computacional ) es la siguiente heurística: "En cada paso del viaje, visita 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 para un problema tan complejo normalmente requiere una cantidad irrazonablemente grande de pasos. En optimización matemática, los algoritmos voraces resuelven de manera óptima problemas combinatorios que tienen las propiedades de los matroides y dan aproximaciones de factor constante a problemas de optimización con la estructura submodular.

Detalles específicos

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

Propiedad de elección codiciosa
Se puede elegir la opción que parezca mejor en un momento dado y luego (de forma recursiva) resolver los subproblemas restantes. La elección que hace un algoritmo voraz puede depender de las opciones que se hayan elegido hasta el momento, pero no de las opciones futuras ni de todas las soluciones del subproblema. Iterativamente, toma una opción voraz tras otra, reduciendo cada problema dado a uno más pequeño. En otras palabras, un algoritmo voraz nunca reconsidera sus opciones. Esta es la principal diferencia con la programación dinámica , que es exhaustiva y garantiza 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 exhibe una subestructura óptima si una solución óptima al problema contiene soluciones óptimas a los subproblemas". [2]

Casos de fracaso

Ejemplos de cómo un algoritmo codicioso puede no lograr la solución óptima.

Los algoritmos voraces no logran producir la solución óptima para muchos otros problemas e incluso pueden producir la peor solución posible. Un ejemplo es el problema del viajante 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. [3] Para otros ejemplos posibles, véase el efecto horizonte .

Tipos

Los algoritmos voraces pueden caracterizarse como "poco previsores" y también como "irrecuperables". Son ideales sólo para problemas que tienen una "subestructura óptima". A pesar de esto, para muchos problemas simples, los algoritmos más adecuados son voraces. Sin embargo, es importante señalar que el algoritmo voraz puede usarse como un algoritmo de selección para priorizar opciones dentro de un algoritmo de búsqueda o de ramificación y acotación. Existen algunas variaciones del algoritmo voraz: [4]

Teoría

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

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

Matroides

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

Funciones submodulares

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

Supongamos que se desea encontrar un conjunto que maximice . El algoritmo voraz, que construye un conjunto añadiendo de forma incremental el elemento que aumenta más en cada paso, produce como resultado un conjunto que es al menos . [7] Es decir, el algoritmo voraz funciona dentro de un factor constante de tan bueno como la solución óptima.

Se pueden demostrar garantías similares cuando se imponen restricciones adicionales, como restricciones de cardinalidad, [8] en la salida, aunque a menudo se requieren ligeras variaciones en el algoritmo voraz. Véase [9] para una descripción general.

Otros problemas con las garantías

Otros problemas para los que el algoritmo voraz 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 voraces normalmente (pero no siempre) no logran encontrar la solución globalmente óptima porque no suelen operar exhaustivamente sobre todos los datos. Pueden comprometerse con ciertas opciones demasiado pronto, lo que les impide encontrar la mejor solución global más adelante. Por ejemplo, todos los algoritmos voraces de coloración conocidos para el problema de coloración de grafos y todos los demás problemas NP-completos no encuentran soluciones óptimas de manera consistente. Sin embargo, son útiles porque se les ocurre rápidamente y a menudo brindan buenas aproximaciones al óptimo.

Si se puede demostrar que un algoritmo voraz produce el óptimo global para una clase de problema dada, 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 . Algunos ejemplos de estos algoritmos voraces son el algoritmo de Kruskal y el algoritmo de Prim para encontrar árboles de expansión mínimos y el algoritmo para encontrar árboles de Huffman óptimos .

Los algoritmos voraces también aparecen en el enrutamiento de redes . Mediante el enrutamiento voraz, se reenvía un mensaje al nodo vecino que está "más cerca" del destino. La noción de ubicación de un nodo (y, por lo tanto, de "cercanía") puede determinarse por su ubicación física, como en el enrutamiento geográfico utilizado por 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

Véase también

Referencias

  1. ^ Black, Paul E. (2 de febrero de 2005). "algoritmo voraz". Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología (NIST) de EE. UU . . Consultado el 17 de agosto de 2012 .
  2. ^ Cormen et al. 2001, cap. 16
  3. ^ Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002). "El viajante de comercio no debería ser codicioso: análisis de dominación de heurísticas de tipo codicioso para el TSP". Matemáticas Aplicadas Discretas . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 .
  4. ^ DeVore, RA; Temlyakov, VN (1996-12-01). "Algunas observaciones sobre algoritmos voraces". Avances en Matemática Computacional . 5 (1): 173–187. doi :10.1007/BF02124742. ISSN  1572-9044.
  5. ^ Feige 1998
  6. ^ Papadimitriou y Steiglitz 1998
  7. ^ Nemhauser, Wolsey y Fisher 1978
  8. ^ Buchbinder y otros, 2014
  9. ^ Krause y Golovin 2014
  10. ^ "Lección 5: Introducción a los algoritmos de aproximación" (PDF) . Algoritmos avanzados (2IL45) — Apuntes del curso . TU Eindhoven. Archivado (PDF) desde el original el 2022-10-09.

Fuentes

Enlaces externos