¿Todos los algoritmos codiciosos tienen estructura matroide?

13

Está bien establecido que por cada matroid M y cualquier función peso w , no sale de un algoritmo GreedyBasis(M,w) que devuelve una base de peso máximo de M . Entonces, ¿la dirección inversa también es verdadera? Es decir, si hay algún algoritmo codicioso, entonces también debe haber alguna estructura matroide.

Jan Johannsen
fuente
El algoritmo de Dijkstra a menudo se considera un algoritmo codicioso (por ejemplo, consulte la Sección 4.4 del "Diseño de algoritmo" de Kleinberg y Tardos). No sé de una interpretación matroide de los caminos más cortos de una sola fuente.
Neal Young
Particionar un conjunto de intervalos reales en un número mínimo de subconjuntos separados por pares tiene un algoritmo codicioso natural (enumere los intervalos por hora de inicio, para cada uno agréguelo a un subconjunto existente si es posible, de lo contrario comience un nuevo subconjunto; vea el Capítulo 4 de Kleinberg y Tardos). ¿Se puede entender este problema como un matroide?
Neal Young el

Respuestas:

12

En realidad, la descripción completa y general de un problema que puede resolverse mediante un algoritmo codicioso es una incrustación matroide , que generaliza tanto el concepto de un matroide como el de un greedoide . La respuesta es no: un problema solucionable mediante un algoritmo codicioso no necesita tener una estructura matroide, pero tendrá la estructura de una incrustación matroide (que, por desgracia, es mucho más complicada).

Un modelo mental para algo de esto podría ser encontrar árboles de expansión mínima. La estructura utilizada por el algoritmo de Kruskal es matroide, pero la utilizada por el algoritmo de Prim (que requiere un nodo de inicio) no lo es. (Sin embargo, es un greedoid y una incrustación matroide).

(S,C)SCS f:2SRS

El algoritmo codicioso, definido en términos de este formalismo, es bastante simple: comienza con el conjunto vacío y agrega sucesivamente un solo elemento hasta llegar a una base, siempre asegurándose de que (i) su conjunto sea factible en cada paso, y ( ii) el elemento que agrega maximiza la función objetivo del resultado resultante, wrt. Todos los elementos alternativos que podría haber agregado. (Es decir, conceptualmente, intentas agregar todas las alternativas posibles y eliges la que tenga el valor objetivo más alto).

Quizás podría argumentar que podría haber otras formas de algoritmo codicioso, pero hay varios libros de texto sobre algoritmos y optimización combinatoria que describen este algoritmo basado en un sistema de conjuntos como el algoritmo codicioso. Eso no te impide describir algo que no encaja, pero que aún podría llamarse codicioso, supongo. (Sin embargo, esto hace la cubierta cualquier cosa que podría tener una estructura matroide, por ejemplo, aunque es mucho más general.)

Lo que Helman et al. hacer es que describen cuándo funcionará este algoritmo. Más específicamente:

  1. Muestran que para las funciones objetivas lineales (donde el valor objetivo es la suma de los pesos de los elementos), el algoritmo codicioso funcionará exactamente en la estructura que definen como una inserción matroide;

  2. Dan una caracterización similar para los llamados objetivos de cuello de botella (donde el valor objetivo de un conjunto es igual al mínimo sobre los pesos de elementos individuales); y

  3. Dan una caracterización exacta de qué funciones objetivas (más allá de las lineales) están optimizadas por el algoritmo codicioso en las incrustaciones matroides.

Magnus Lie Hetland
fuente
3
¿Puedes explicar cuál es su definición de algoritmo codicioso?
Kaveh
1
Expandí mi respuesta para explicar cuál es su formalismo.
Magnus Lie Hetland
11

El algoritmo codicioso no es un concepto formalmente definido. Hay varios modelos que intentan capturar esta noción intuitiva, pero no hay consenso sobre qué es un algoritmo codicioso. A menos que especifique una definición formal de lo que quiere decir con un algoritmo codicioso, la pregunta no puede responderse como sí o no.

Hay una generalización de matroides llamada greedoid que está inspirada en algoritmos codiciosos que es posible que desee ver.

Kaveh
fuente
No se requiere una definición formal si estamos de acuerdo con alguna propiedad de la clase de algoritmos codiciosos. Si, por ejemplo, acordamos que cada algoritmo codicioso tiene una propiedad (formalmente definida) P, y demostramos que cada algoritmo que satisface P puede definirse en un matroide, eso daría una respuesta positiva a la pregunta del OP. De manera similar, si acordamos que cierto algoritmo es codicioso y demostramos que no puede ser el algoritmo codicioso de un matroide, eso daría una respuesta negativa.
Independiente de Laconia el
2

Considere los siguientes problemas: EURO DE CADENA DE MONEDAS: Dada una cantidad infinita de billetes de 1,2,5,10 euros, pague X euros usando la menor cantidad de billetes posible. Esto se puede resolver utilizando un algoritmo codicioso, que toma la mayor nota posible. Pero no hay una estructura matroide en este problema.

COBERTURA DE AGUJERO: Hay agujeros en las posiciones x_1, x_2, ..., x_n. Tienes parche de longitud 10 cm. Parchea los agujeros usando la menor cantidad de parches posible. Una vez más, esto se puede resolver de manera codiciosa (solo coloque el parche lo más correcto posible), pero no hay una estructura matroide.

usamec
fuente
gracias, tenía mis sospechas pero no estaba seguro. Entonces, después de todo, tenemos que buscar un algoritmo codicioso incluso si la estructura matroide no existe.
1
@ user3373748 Normalmente solo busco un programa dinámico. Codicioso es un DP degenerado.
1
(No para ser exigente, pero no hay billetes de 1 o 2 euros; es posible que desee cambiar su conjunto de valores a {5, 10, 20, 50, 100, 200} o reformular ;-))
Anthony Labarre
Tenga en cuenta que el algoritmo de cambio de moneda descrito funciona para {1,2,5,10} pero puede no calcular resultados óptimos para otros valores. Ejemplo: con {1,3,4} la solución óptima para 6 sería [3,3] pero el algoritmo devolvería [4,1,1].
Socowi
1
Hay una estructura matroide para el problema del cambio de monedas: gauss.ececs.uc.edu/Courses/C671/html/Homework/hw5_sol.html
Tushant Mittal