Codicioso

Sistema de conjuntos utilizado en la optimización voraz

En combinatoria , un greedoide es un tipo de sistema de conjuntos . Surge de la noción de matroide , que fue introducida originalmente por Whitney en 1935 para estudiar grafos planares y luego fue utilizada por Edmonds para caracterizar una clase de problemas de optimización que pueden ser resueltos por algoritmos voraces . Alrededor de 1980, Korte y Lovász introdujeron el greedoide para generalizar aún más esta caracterización de algoritmos voraces; de ahí el nombre greedoide. Además de la optimización matemática , los greedoides también se han relacionado con la teoría de grafos , la teoría del lenguaje, la teoría del orden y otras áreas de las matemáticas .

Definiciones

Un sistema de conjuntos ( F , E ) es una colección F de subconjuntos de un conjunto base E (es decir, F es un subconjunto del conjunto potencia de E ). Cuando se considera un greedoide, un miembro de F se denomina conjunto factible . Cuando se considera un matroide , un conjunto factible también se conoce como conjunto independiente .

Un sistema de conjuntos accesible ( F , E ) es un sistema de conjuntos en el que cada conjunto factible no vacío X contiene un elemento x tal que es factible. Esto implica que cualquier sistema de conjuntos accesible, finito y no vacío contiene necesariamente el conjunto vacío ∅. ^[1] ${\displaystyle X\setminus \{x\}}$

Un greedoid ( F , E ) es un sistema de conjuntos accesible que satisface la propiedad de intercambio :

• Para todos los que hay algo así ${\displaystyle X,Y\in F}$ ${\displaystyle |X|>|Y|,}$ ${\displaystyle x\in X\setminus Y}$ ${\displaystyle Y\cup \{x\}\in F.}$

(Nota: Algunas personas reservan el término propiedad de intercambio para una condición basada en un codiciado, y prefieren llamar a la condición anterior “propiedad de aumento”).

Una base de un greedoide es un conjunto factible máximo, es decir , es un conjunto factible pero no está contenido en ningún otro. Una base de un subconjunto X de E es un conjunto factible máximo contenido en X.

El rango de un greedoide es el tamaño de una base. Por la propiedad de intercambio, todas las bases tienen el mismo tamaño. Por lo tanto, la función de rango está bien definida . El rango de un subconjunto X de E es el tamaño de una base de X. Al igual que con los matroides, los greedoides tienen un criptomorfismo en términos de funciones de rango. ^[2] Una función es la función de rango de un greedoide en el conjunto base E si y solo si r es subcardinal , monótono y localmente semimodular , es decir, para cualquier y cualquier tenemos: ${\displaystyle r:2^{E}\to \mathbb {Z} }$ ${\displaystyle X,Y\subseteq E}$ ${\displaystyle e,f\in E}$

• subcardinalidad : ${\displaystyle r(X)\leq |X|}$
• monotonía : siempre que ${\displaystyle r(X)\leq r(Y)}$ ${\displaystyle X\subseteq Y\subseteq E}$
• semimodularidad local : siempre que ${\displaystyle r(X)=r(X\cup \{e,f\})}$ ${\displaystyle r(X)=r(X\cup \{e\})=r(X\cup \{f\})}$

Clases

La mayoría de las clases de greedoids tienen muchas definiciones equivalentes en términos de sistema de conjuntos, lenguaje, conjunto poset, complejo simplicial , etc. La siguiente descripción sigue la ruta tradicional de enumerar solo un par de las caracterizaciones más conocidas.

Un greedoide de intervalo ( F , E ) es un greedoide que satisface la propiedad de intervalo :

• si con entonces, para todos ${\displaystyle A,B,C\in F}$ ${\displaystyle A\subseteq B\subseteq C,}$ ${\displaystyle x\in E\setminus C:}$

$${\displaystyle {\begin{matrix}A\cup \{x\}\in F\\C\cup \{x\}\in F\end{matrix}}\implies B\cup \{x\}\in F.}$$

De manera equivalente, un greedoide de intervalo es un greedoide tal que la unión de dos conjuntos factibles es factible si está contenida en otro conjunto factible.

Un antimatroide ( F , E ) es un greedoide que satisface la propiedad de intervalo sin límites superiores :

• si ⁠ ⁠ ${\displaystyle A,B\in F}$ con ⁠ ⁠ ${\displaystyle A\subseteq B,}$ entonces, para todo ⁠ ⁠ ${\displaystyle x\in E\setminus B,}$ ⁠ ⁠ ${\displaystyle A\cup \{x\}\in F}$ implica ⁠ ⁠ ${\displaystyle B\cup \{x\}\in F.}$

De manera equivalente, un antimatroide es (i) un greedoide con una base única; o (ii) un sistema de conjuntos accesible cerrado bajo unión. Es fácil ver que un antimatroide es también un greedoide de intervalo.

Un matroide ( F , E ) es un greedoide no vacío que satisface la propiedad de intervalo sin límites inferiores :

• si ⁠ ⁠ ${\displaystyle B,C\in F}$ con ⁠ ⁠ ${\displaystyle B\subseteq C,}$ entonces, para todo ⁠ ⁠ ${\displaystyle x\in E\setminus C,}$ ⁠ ⁠ ${\displaystyle C\cup \{x\}\in F}$ implica ⁠ ⁠ ${\displaystyle B\cup \{x\}\in F.}$

Es fácil ver que un matroide es también un greedoide de intervalo.

Ejemplos

• Consideremos un grafo no dirigido G . Sea el conjunto base las aristas de G y los conjuntos factibles el conjunto de aristas de cada bosque (es decir, subgrafo que no contiene ciclos) de G . Este sistema de conjuntos se denomina matroide de ciclos . Se dice que un sistema de conjuntos es un matroide gráfico si es el matroide de ciclos de algún grafo. (Originalmente, el matroide de ciclos se definió en circuitos , o conjuntos dependientes mínimos . De ahí el nombre ciclo).
• Consideremos un grafo finito no dirigido G con raíz en el vértice r . Sea el conjunto base los vértices de G y los conjuntos factibles los subconjuntos de vértices que contienen r que inducen subgrafos conexos de G. Esto se denomina greedoide de búsqueda de vértices y es un tipo de antimatroide.
• Consideremos un grafo finito y dirigido D con raíz en r . Sea el conjunto base las aristas (dirigidas) de D y los conjuntos factibles los conjuntos de aristas de cada subárbol dirigido con raíz en r con todas las aristas apuntando en dirección opuesta a r . Esto se denomina greedoide de búsqueda lineal o greedoide de ramificación dirigida . Es un greedoide de intervalo, pero no un antimatroide ni un matroide.
• Considere una matriz M de m × n . Sea el conjunto base E los índices de las columnas de 1 a n y los conjuntos factibles Esto se llama greedoide de eliminación gaussiana porque esta estructura subyace al algoritmo de eliminación gaussiana . Es un greedoide, pero no un greedoide de intervalo. $${\displaystyle F=\{X\subseteq E:{\text{ submatrix }}M_{\{1,\ldots ,|X|\},X}{\text{ is an invertible matrix}}\}.}$$

Algoritmo codicioso

En general, un algoritmo voraz es simplemente un proceso iterativo en el que se elige una mejor opción local , normalmente una entrada de peso máximo, en cada ronda hasta que se hayan agotado todas las opciones disponibles. Para describir una condición basada en greedoid en la que un algoritmo voraz es óptimo (es decir, obtiene una base de valor máximo), necesitamos algunas terminologías más comunes en la teoría de greedoid. Sin pérdida de generalidad , consideramos un greedoid G = ( F , E ) con E finito.

Un subconjunto X de E es factible por rango si la intersección más grande de X con cualquier conjunto factible tiene un tamaño igual al rango de X. En un matroide, cada subconjunto de E es factible por rango. Pero la igualdad no se cumple para los greedoides en general.

Una función es R -compatible si es factible en rango para todos los números reales c . ${\displaystyle w:E\to \mathbb {R} }$ ${\displaystyle \{x\in E:w(x)\geq c\}}$

Una función objetivo es lineal sobre un conjunto si, para todo, tenemos alguna función de peso ${\displaystyle f:2^{S}\to \mathbb {R} }$ ${\displaystyle S}$ ${\displaystyle X\subseteq S,}$ ${\displaystyle f(X)=\sum _{x\in X}w(x)}$ ${\displaystyle w:S\to \Re .}$

Proposición. Un algoritmo voraz es óptimo para cada función objetivo lineal compatible con R sobre un voraz.

La intuición detrás de esta proposición es que, durante el proceso iterativo, cada intercambio óptimo de peso mínimo es posible gracias a la propiedad de intercambio, y se pueden obtener resultados óptimos a partir de los conjuntos factibles en el greedoid subyacente. Este resultado garantiza la optimalidad de muchos algoritmos conocidos. Por ejemplo, se puede obtener un árbol de expansión mínimo de un grafo ponderado utilizando el algoritmo de Kruskal , que es un algoritmo voraz para el matroide de ciclo. El algoritmo de Prim se puede explicar tomando en su lugar el greedoid de búsqueda de línea.

Véase también

• Matroide
• Polimatroide

Referencias

1. Nótese que la propiedad de accesibilidad es estrictamente más débil que la propiedad hereditaria de un matroide , que requiere que cada subconjunto de un conjunto independiente sea independiente.
2. Björner, Anders ; Ziegler, Günter M. (1992), "8. Introducción a los greedoids", en White, Neil (ed.), Matroid Applications , Enciclopedia de matemáticas y sus aplicaciones, vol. 40, Cambridge: Cambridge University Press, págs. 284–357, doi :10.1017/CBO9780511662041.009, ISBN 0-521-38165-7, MR  1165537, Zbl  0772.05026

• Björner, Anders ; Ziegler, Günter M. (1992), "8. Introducción a los greedoids", en White, Neil (ed.), Matroid Applications , Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge: Cambridge University Press, págs. 284–357, doi :10.1017/CBO9780511662041.009, ISBN 0-521-38165-7, MR  1165537, Zbl  0772.05026
• Edmonds, Jack (1971), "Matroides y el algoritmo voraz", Programación matemática , 1 : 127–136, doi :10.1007/BF01584082, S2CID  5599224, Zbl  0253.90027.
• Helman, Paul; Moret, Bernard ME; Shapiro, Henry D. (1993), "Una caracterización exacta de las estructuras voraces", SIAM Journal on Discrete Mathematics , 6 (2): 274–283, CiteSeerX  10.1.1.37.1825 , doi :10.1137/0406021, Zbl  0798.68061.
• Korte, Bernhard ; Lovász, László (1981), "Estructuras matemáticas subyacentes a algoritmos voraces", en Gecseg, Ferenc (ed.), Fundamentals of Computation Theory: Proceedings of the 1981 International FCT-Conference, Szeged, Hungría, 24-28 de agosto de 1981 , Lecture Notes in Computer Science, vol. 117, Berlín: Springer-Verlag , pp. 205-209, doi :10.1007/3-540-10854-8_22, Zbl  0473.68019.
• Korte, Bernhard; Lovász, László ; Schrader, Rainer (1991), Greedoides , algoritmos y combinatoria, vol. 4, Nueva York, Berlín: Springer-Verlag , ISBN 3-540-18190-3, Zbl0733.05023 ​.
• Oxley, James G. (1992), Teoría de matroides , Oxford Science Publications, Oxford: Oxford University Press , ISBN 0-19-853563-5, Zbl0784.05002 ​.
• Whitney, Hassler (1935), "Sobre las propiedades abstractas de la independencia lineal", American Journal of Mathematics , 57 (3): 509–533, doi :10.2307/2371182, hdl : 10338.dmlcz/100694 , JSTOR  2371182, Zbl  0012.00404.

Enlaces externos

• Introducción a Greedoids
• Teoría de algoritmos voraces Archivado el 4 de marzo de 2016 en Wayback Machine
• Funciones submodulares y optimización
• Emparejamientos, matroides y funciones submodulares