Matrids Greedy
Matrids Greedy
Matrids Greedy
1. Marco Teorico 2
1.1. Algoritmos Voracez . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Hipotesis 3
3. Aspectos Metodologicos 3
3.1. Tipo de Estudio . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2. Metodo de Investigacion . . . . . . . . . . . . . . . . . . . . . 3
3.3. Fuentes de Informacion . . . . . . . . . . . . . . . . . . . . . . 3
4. Desarrollo 4
4.1. Teoria de Matroids . . . . . . . . . . . . . . . . . . . . . . . . 4
4.2. Relación con los algoritmos greedy . . . . . . . . . . . . . . . 6
4.3. Un problema de programacion de tareas . . . . . . . . . . . . 10
4.4. Otros Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.5. Teoria de Greedoids . . . . . . . . . . . . . . . . . . . . . . . . 12
4.6. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.7. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5. Conclusiones 15
6. Bibliografia 16
1
1. Marco Teorico
1.1. Algoritmos Voracez
Un algoritmo es un metodo efectivo para resolver un problema expre-
sado como una secuencia finita de pasos. Cada algoritmo es una lista de
instrucciones bien definidas para llevar acabo una tarea. Partiendo de un es-
tado inicial, las instrucciones describen un proceso de computo que recorre
una serie bien definida de estados sucesivos, hasta llegar a un estado final.
Hay varias formas de clasificar a los algoritmos, como por ejemplo: por im-
plementacion, por el paradigma de su diseño o por el campo de estudio al
que pertenece.
Dentro de la clasificación por el paradigma de diseño encontramos a los al-
goritmos voracez. Estos algoritmos se rigen por la heuristica de tomar la
eleccion optima local en cada paso, con la esperanza de llegar al final a un
optimo global. En general, un algoritmo voraz(greedy) esta formado por:
1. Un conjunto de candidatos, de los cuales se crea una solucion.
2. Una funcion de seleccion, que escoge el mejor candidato para ser agre-
gado a la solucion.
3. Una funcion de factibilidad, para determinar si un candidato puede ser
usado para contribuir a la solucion.
4. Una funcion objetivo, que asigna valores a la solucion (o a la solucion
parcial).
5. Una funcion de solucion, que nos indicara cuando hemos llegado a una
solucion completa.
Estos algoritmos producen buenas soluciones en algunos problemas, pero no
en otros. Los problemas en los que se llega a soluciones optimas poseen dos
propiedades:
2
Subestructura optima
Un problema tiene esta propiedad si una solucion optima al problema
contiene soluciones optimas a los subproblemas.
2. Hipotesis
No todo algoritmo voraz genera una solucion optima.
3. Aspectos Metodologicos
3.1. Tipo de Estudio
El presente trabajo realizara un estudio descriptivo. Identificaremos ca-
racteristicas del objeto de estudio y presentaremos la teoria de matroids y
greedoids junto con aplicaciones a problemas computacionales concretos.
3
4. Desarrollo
4.1. Teoria de Matroids
Un matroid o estructura de independencia captura la esencia de la
noción de independencia. Formalmente un matroid finito M es un par (E, I),
donde E es un conjunto finito (llamado el conjunto fundamental) e I es
una colección de subconjuntos de E (llamados los conjuntos independien-
tes con las siguientes propiedades:
4
Teorema 1 Si G = (V, A) es un grafo no dirigido, entonces MG = (EG , IG )
es un matroid.
Demostracion Claramente, EG = A es un conjunto finito. Ademas, IG
es hereditario, ya que un subconjunto de un bosque sigue siendo un bosque
(remover aristas de un conjunto aciclico de aristas no puede crear ciclos).
Queda demostrar que MG satisface la propiedad del intercambio. Supon-
gamos que GP = (V, P ) y GQ = (V, Q) son bosques de G y que |Q| > |P |.
Esto es, P y Q son conjuntos aciclicos de aristas y Q contiene mas aristas que
A. Sabemos, por teoria, que un bosque con k aristas y |V | vertices contiene
exactamente |V | − k arboles. Por lo tanto, el bosque GP contiene |V | − |P |
arboles y el bosque GQ contiene |V | − |Q| arboles.
Como el bosque GQ tiene menos arboles que el bosque GP , el bosque GQ
debe contener algun arbol T con un arista (u, v) tal que los vertices u y v
estan en diferentes arboles en el bosque GP . Dado que el arista (u, v) conecta
vertices en dos arboles diferentes en el bosque GP , el arista (u, v) puede
ser agregado al bosque GA sin crear un ciclo. Por lo tanto, MG satisface la
propiedad del intercambio. Esto completa la demostracion de que MG es un
matroid.
5
que conectan todos los vertices de G. Tal arbol es llamado un arbol de
expansion de G.
Decimos que un matroid M = (E, I) esta pesado si existe una funcion de
peso asociada que asigna un peso estrictamente positivo w(x) a cada elemento
x ∈ E. La funcion de peso se extiende a subconjuntos de E mediante
X
w(A) = w(x)
x∈A
6
para cualquier base A, un subconjunto independiente que maximiza la canti-
dad w0 (A) debe minimizar w(A). Por lo tanto, cualquier algoritmo que pueda
encontrar un subconjunto optimo en un matroid cualquiera puede resolver el
problema del arbol de expansion minima.
Existen diversos algoritmos para hallar el arbol de expansion minima,
como por ejemplo el algoritmo de Kruskal o Prim. Sin embargo, usaremos un
algoritmo greedy que es correcto para cualquier matroid pesado. El algoritmo
toma como entrada un matroid pesado M = (E, I) con una funcion de peso
positiva w, y retorna un subconjunto optimo A. En el pseudocodigo que
presentaremos, denotamos los componentes de M mediante E[M ] y I[M ]
y la funcion de peso con w. El algoritmo es greedy porque considera cada
elemento x ∈ E en order decreciente de su peso e inmediatamente lo lo agrega
al conjunto A si A ∪ {x} es independiente.
Algorithm 1 Greedy(M, w)
1: A ← ∅
2: ordenar E[M ] en orden decreciente de acuerdo al peso w
3: for all x ∈ E[M ], tomado en orden decreciente de acuerdo al peso w(x)
do
4: if A ∪ {x} ∈ I[M ] then
5: A ← A ∪ {x}
6: end if
7: end for
8: return A
7
determinar lo anterior toma un tiempo de O(f (n)), el algoritmo Greedy tiene
un tiempo de ejecucion de O(n lg n + n f (n)).
Ahora pasaremos a demostrar que el algoritmo Greedy retorna un sub-
conjunto optimo.
Lema 1 Sea M = (E, I), un matroid pesado con funcion de peso w y con E
ordenado de forma decreciente con respecto al peso. Sea x el primer elemento
de E tal que {x} es independiente, si es que existe tal x. Si x existe, entonces
existe un subconjunto optimo A de E que contiene a x.
8
Demostracion Este corolario es simplemente la contrapositiva del lema
2.
El corolario 1 indica que cualquier elemento que no puede ser usado in-
mediatamente nunca puede ser usado. Por lo tanto, el algoritmo Greedy no
comete un error al ignorar los elementos iniciales de E que no son una ex-
tension de ∅, ya que nunca podran ser usados.
9
a A, todos los pasos restantes pueden ser interpretados como si estuvieran
actuando sobre el matroid M 0 = (E 0 , I 0 ). Por lo tanto, las siguiente operacion
del algoritmo Greedy encontrara un subconjunto optimo para M 0 , y todo el
proceso en si de este algoritmo encontrara un subconjunto optimo para M .
Dada una programacion se dira que una tarea es tardado en una progra-
macion si es que finaliza luego de su tiempo tope, En otro caso se dica que
es temprano en la programacion.
Una programacion siempre es de forma de primer temprano cuando
las tareas tempranas preceden a las tareas tardadas.
10
aj 1 2 3 4 5 6 7
di 4 2 4 3 1 4 6
wi 70 60 50 40 30 20 10
Lemma
Para cualquier conjunto de tareas A , las siguientes afirmaciones
son equivalentes:
1. El conjunto A es independiente.
2. Para t = 0, 1, 2, ..., n tenemos que Nt (A) ≤ t.
3. Si las tareas en A son programadas en orden creciente a sus
tiempos topes entonces no habran tareas tardas.
11
A . Nosotros podemos entonces crear una programacion optima
teniendo las tareas en A como tareas tempranas.
El tiempo de ejecucion es O(n2 ).
La programacion optima final del ejemplo es :
12
Consideremos un greedoid G = (F, E) con E finito. Una base del greedoid
es un conjunto factible maximal (no esta contenido en otro conjunto facti-
ble). Una base de un subconjunto X de E es un conjunto factible maximal
contenido en X.
El rango de un greedoid es el tamaño de una base (pueden haber varias ba-
ses). Gracias a la propiedad del intercambio todas las bases tienen el mismo
tamaño y por lo tanto el rango de un greedoid esta bien definido. El rango
de un subconjunto X de E es el tamaño de una base de X.
Un subconjunto X de E es factible por rango si la mayor interseccion de
X con cualquier conjunto factible tiene tamaño igual al rango de X.
Una funcion w : E → R es R-compatible si {x ∈ E : w(x) ≥ c} es factible
por rango para todo c ∈ R.
Una funcion objetivo f : 2S → R es lineal sobre un conjunto S si, para
todo X ⊆ S, tenemos que f (X) = x∈X w(x) para alguna funcion de peso
P
w : S → R.
Finalmente el siguiente enunciado establece una correspondencia entre la
correctitud de un algoritmo voraz y la teoria de greedoids.
4.6. Ejemplos
Ejemplo 1
Considerar un grafo no dirigido G. Sea el conjunto fundamental las aris-
tas de G y los conjuntos factibles el conjunto de aristas de cada f orest
(una union disjunta de arboles) de G , por ejemplo un subgrafo que no con-
tiene ningun ciclo G. Este sistema de conjuntos es llamado un ciclo matroid.
Un sistema de conjunto es ddicho un matroid grafico si es un ciclo matroid
para algun grafo. (Originalmente los ciclos matroids fueron definidos sobre
circuitos , o minimos conjuntos dependienes.De ahi el nombre ciclo).
Ejemplo 2
COnsiderear un grafo conexo, rooted, dirigido , en el cual cada arista no
dirigida tiene un numero real no negativo como peso, y sus asociados dirgidos
derivan a un greedoid . Entonces , un el camino rapido , que significa el camino
con el minimo total de peso , puede ser obtenido usando directamente el
13
algoritmodeDijkstra . O equivalentemente , podemos aplicar el algoritmo
greedy sobre la suma de los pesos negativos para cada conjunto accesible de
su greedoid asociado.
4.7. Resultados
Estos ejemplos muestran que los matroides son usualmente buenos para
situaciones en las que el orden no importa, asi en un grafo unrooted(sin raiz),
no dirigido . Sin embargo , si el orden es importante , tanto en un grafo roo-
ted o en un grafo dirigido, entonces una estructura parecida a los greedoids
es necesitada. Pero los greedoids tambien , confian en que la funcion objetivo
esta siendo lineal .
14
5. Conclusiones
Los algoritmos greedy operan de una forma sencilla, pero demostrar
que en efecto son correctos no lo es.
15
6. Bibliografia
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clif-
ford Stein. Introduction to Algorithms.
http://info.wlu.ca/ wwwmath/faculty/cameron/matroid.pdf
http://math.fau.edu/locke/Greedy.htm
http://www.math.binghamton.edu/zaslav/Pagano/Matridx.htm
http://userhome.brooklyn.cuny.edu/skingan/matroids/
http://www.cs.umass.edu/ barring/cs611/lecture/4.pdf
16