Codicioso

Sistema de configuración utilizado en optimización codiciosa

En combinatoria , un codicioso es un tipo de sistema de conjuntos . Surge de la noción de matroide , que fue introducida originalmente por Whitney en 1935 para estudiar gráficos planos y posteriormente utilizada por Edmonds para caracterizar una clase de problemas de optimización que pueden resolverse mediante algoritmos codiciosos . Alrededor de 1980, Korte y Lovász introdujeron el codicioso para generalizar aún más esta caracterización de algoritmos codiciosos; de ahí el nombre codicioso. Además de la optimización matemática , los greedoids 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 fundamental E (es decir, F es un subconjunto del conjunto potencia de E ). Cuando se considera un codicioso, un miembro de F se llama conjunto factible . Cuando se considera una 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 todo conjunto factible no vacío X contiene un elemento x tal que sea 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 hay algo tal que ${\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 greedoide y prefieren llamar a la condición anterior “propiedad de aumento”.)

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

El rango de un codicioso es del tamaño de una base. Según la propiedad de intercambio, todas las bases tienen el mismo tamaño. Por 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 las matroides, los codiciosos tienen un criptomorfismo en términos de funciones de rango. ^[2] Una función es la función de rango de un codicioso en el conjunto terrestre E si y solo si r es subcardinal , monótono y localmente semimodular , es decir, para cualquiera y cualquiera tenemos: ${\displaystyle r:2^{E}\to \mathbb {Z} }$ ${\displaystyle X,Y\subseteq E}$ ${\displaystyle e,f\in E}$

• subcardinalidad : ${\displaystyle r(X)\leq |X|}$
• monotonicidad : 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, poset, complejo simplicial , etc. La siguiente descripción sigue la ruta tradicional de enumerar sólo un par de las caracterizaciones más conocidas.

Un greedoid de intervalo ( F , E ) es un greedoid que satisface la propiedad del 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 cualesquiera es factible si está contenido en otro conjunto factible.

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

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

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

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

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

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

Ejemplos

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

Algoritmo codicioso

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

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

Una función es compatible con R si su rango es factible 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, por lo demás, 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 codicioso es óptimo para cada función objetivo lineal compatible con R sobre un codicioso.

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 greedoide subyacente. Este resultado garantiza la optimización de muchos algoritmos conocidos. Por ejemplo, se puede obtener un árbol de expansión mínimo de un gráfico ponderado utilizando el algoritmo de Kruskal , que es un algoritmo codicioso para el ciclo matroide. El algoritmo de Prim se puede explicar tomando en su lugar la línea de búsqueda greedoid.

Ver también

• Matroide
• polimatroide

Referencias

1. Tenga en cuenta que la propiedad de accesibilidad es estrictamente más débil que la propiedad hereditaria de una 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 , 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, SEÑOR  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, SEÑOR  1165537, Zbl  0772.05026
• Edmonds, Jack (1971), "Matroides y el algoritmo codicioso", Programación matemática , 1 : 127–136, doi :10.1007/BF01584082, S2CID  5599224, Zbl  0253.90027.
• Helman, Pablo; Moret, Bernard ME; Shapiro, Henry D. (1993), "Una caracterización exacta de estructuras codiciosas", Revista SIAM de Matemáticas Discretas , 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 codiciosos", en Gecseg, Ferenc (ed.), Fundamentos de la teoría de la computación: Actas de la Conferencia Internacional FCT de 1981, Szeged, Hungría, 24 al 28 de agosto de 1981 , Conferencia Notas en Ciencias de la Computación, vol. 117, Berlín: Springer-Verlag , págs. 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, Zbl  0733.05023.
• Oxley, James G. (1992), Teoría matroide , Oxford Science Publications, Oxford: Oxford University Press , ISBN 0-19-853563-5, Zbl  0784.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 los codiciosos
• Teoría de los algoritmos codiciosos
• Funciones submodulares y optimización
• Emparejamientos, matroides y funciones submodulares