Aula número 18 - 11/12/2000
Ana Bela Martins n.º 11761
Ensino de Informática
2.2 Matroid de Rank
3. Optimização e Cardinalidade Máxima
Existem vários parâmetros que podem definir os matroids, mas todos têm tipos mais ou menos idênticos de objectos (geralmente para separar esses parâmetros utilizam-se as variantes C-Matroids, B-Matroids, R-Matroids, S-Matroids, etc).
Os matroids são estruturas eficazes em que os algoritmos gulosos (greedy algorithms) trabalham, podemos dizer então, que, qualquer estrutura que pertença à classe Matroid vai ter um algoritmo greedy ou vai ter qualquer coisa de greedy.
Resumo da aula anterior
Vou então recordar a aula anterior e relembrar o que é um algoritmo guloso:
" Um
algoritmo guloso usa-se normalmente em problemas de optimização. O
objectivo é de achar um conjunto de candidatos que
optimizam o valor de uma função objectiva.
Inicialmente, o conjunto é vazio e a cada
passo, o algoritmo selecciona um candidato a
ser acrescentado no conjunto. Ele tenta seleccionar, a cada passo, o
melhor elemento do conjunto de candidatos. Se o
acréscimo desse elemento no conjunto solução for viável, ele será
colocado no conjunto, senão ele será rejeitado e nunca mais será
considerado. Se ele for viável, o algoritmo testa se esse
conjunto é uma solução. Se for, o algoritmo pára e retorna essa solução.
Senão, ele continua:
função
guloso(C: conjunto) : conjunto
{C
é o conjunto de todos os candidatos}
S := {} (Conjunto que constitui a solução, inicialmente vazio)}
Enquanto S não é uma solução e C não vazio
x
:= Melhor elemento de C
C := C - {x}
Se x é viável então S := S U {x}
Se
S é uma solução
retornar
S
Senão
retornar
Não existe uma solução
Esse tipo de algoritmo é dito guloso (greedy) porque ele sempre tenta escolher o melhor pedaço para aquele momento, sem considerar as consequências no futuro. Mas neste algoritmo, para se retornar uma solução óptima, a função de selecção do próximo candidato é crucial, por isso muitas vezes não se encontra a solução óptima."
Podemos considerar matroid também como uma construção matemática, apenas porque um grupo, um campo, ou uma topologia são uma construção. Têm um número grande de operadores associados ou uma colecção especial de subconjuntos, campos, estes podem ser definidos como um matroid.
Definição:
Um matroid M=(S,I) é então um conjunto finito S e um conjunto I dos subconjuntos de S (chamados independentes) tais que:
1. O conjunto vazio ({ }) pertence a I, ou seja, S é um conjunto não vazio (contém { } ) e finito;
2. Se A pertencer a I, então cada subconjunto de A pertence também a I, em que, I é uma família de subconjuntos de conjuntos de subconjuntos de S, isto é, I é um conjunto não vazio de subconjuntos de s.
Podemos definir ainda que, se A estiver dentro do I e B for subconjunto de A, então o B está dentro do I.
I é um subconjunto independente pois a independência é uma propriedade herdada.
3. Se A e B estiverem dentro de I, e o |A| for maior que o |B| (|A|>|B|), então há um elemento X de A\B, tal que B U {X} está dentro (é membro) de I.
Então um conjunto ou, um jogo, é matroid se as 3 condições forem verificadas.
Para os matroids à que considerar vários parâmetros, como eu já referi, vou fazer referência ao B-Matroid, em que uma base de um matroid M=(S,I) é um conjunto independente de máximo, em que se utiliza o B, que satisfazem S, tal que:
B1) Se B1 e B2 pertencem a B e x pertencer a B1\B2, e a seguir existir um elemento y em B2\B1, tal que, B1\{x} U {y} pertence a B. Ou seja, um matroid M=(S,B) é um B-Matroid, pois como referi, utilizou-se para o conjunto B das bases de M, e se B1 e B2 estiverem em B e x estiver em B1\B2, a seguir B1\{x} pertence a I e B2 pertence a I. |B1\{x}|=|B2|-1, em que, se existe um y em B2\(B1\{x})=B2\B1, tal que (B1\{x})U{y} não for máximo, a seguir à um subconjunto B3 com |B3|>B2(um matroid define ainda que (continuação da definição de matroid):
4. Se U e V pertencerem a I, com |U|=|V|+1, então há um x em U\V tal que V U {x} é membro de I);
logo B2 pode ser aumentado, contradizendo o máximo de B, assim, (B1\{x}) U {y} é máximo, e (B1\{x}) U {y} é membro de B.
Para melhor explicar o ponto 4 da definição de matroid, vamos considerar U e V como elementos de I em que |U|=|V|+1. Então, U é um subconjunto de B2 de B e V um subconjunto de B1 de B. Se B1=B2 , então qualquer y de U\V satisfaz a união de V com {y} em I. Assim, supondo que B1 e B2 são distintos e x é elemento de B1\V e não é elemento do B2, há um elemento y em B2\B1 tal que B3=(B1\{x}) U {y} pertence a B. Entretanto, se V é um subconjunto de B3, e U um subconjunto de B2, e a intersecção de B3 com B2 é maior do que a intersecção de B1 com B2, B1\V é subconjunto de B2. Desde que U seja um subconjunto de B2, |B1|=|B2|, (todas as bases em B-Matroid têm a mesma cardinalidade), e y for um elemento de U que se cruza com (B1\V), que é um subconjunto de U\V, a união de V com {y} é um subconjunto do B1 e pertence assim a I. Além desta, e como já verificámos, se o conjunto vazio pertence a I e S é finito, se existir um X que pertence a I e y for subconjunto de X, y é também membro de I, podemos afirmar então que M=(S,I) é um Matroid.
Supondo que M=(S,B) é um B-Matroid. Então:
B2) Se B1 e B2 forem membros de B e y membro de B2\B1, então há um x que pertence a B1\B2 tal que (B1\{x}) U {y} é membro de B.
INICIO
Exemplo 1.
Vamos listar todos os matroids M=(S,I) possíveis, com o máximo de 4 elementos. Fazemos isto, listando as escolhas possíveis para B.
Supondo que S é um conjunto vazio (S={ }); logo a única base possível é: [1] B1={ }
Supondo
S={a}.
As escolhas possíveis para B são:
(1) B1={{a}} e
(2) B2={ }.
Supondo S={a,b}.
As escolhas possíveis para B são:
(1) B1={{a,b}},
(2) B2={{a},{b}},
(3) B3={{a}} e
(4) B4={ }.
Supondo S={a,b,c}.
As escolhas possíveis para B são:
(1) B1={{a,b,c}},
(2)
B2={{a,b},{a,c},{b,c}},
(3) B3={{a,b},{a,c},},
(4) B4={{a,b}},
(5) B5={{a},{b},{c},},
(6) B6={{a},{b}},
(7) B7={{a}}, e
(8) B8={ }.
Supondo S={a,b,c,d}.
As escolhas possíveis para B são:
(1) B1={{a,b,c,d}},
(2) B2={{a,b,c},{a,b,d},{a,c,d},{b,c,d}},
(3) B3={{a,b,c},{a,b,d},{a,c,d}},
(4) B4={{a,b,c},{a,b,d}},
(5) B5={{a,b,c}},
(6) B6={{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}},
(7) B7={{a,b},{a,c},{a,d},{b,c},{b,d}},
(8) B8={{a,c},{a,d},{b,c},{b,d}},
(9) B9={{a,b},{a,c},{b,c}},
(10) B10={{a,b},{a,c},{a,d}},
(11) B11={{a,b},{a,c}},
(12) B12={{a,b}},
(13) B13={{a},{b},{c},{d}},
(14) B14={{a},{b},{c}},
(15) B15={{a},{b}},
(16) B16={{a}}, e
(17) B17={ }.
Exemplo 2.
Existem também matroids de grafos ponderados. Matroids sobre G=(A,V) em que M=(SG,IG).
Sendo o grafo:
M=(SG,IG) SG - conjunto de arcos IG - Conjunto de todos os os subconjuntos de S, sem ciclo.
SG = {1,2,3,4,5,6,7} IG={{1}; {1,2}; {1,2,3}; {1,2,3,4}; {1,6,8,9}; {1,2,3,7,8};{...}; ...}
É um matroid, porque:
1) S é não vazio e tem um conjunto finito de elementos;
2) I é um conjunto não vazio de subconjuntos de S, sem ciclos. Se B é membro de I e A está incluido em B, então A é membro de I;
3) Se A pertence a I e B pertence a I e |A|<|B|=> há pelo menos um x que pertence a B\A, então A U{x} pertence a I;
Se A= {1,2} pertence a I e B= {1,2,3,7,8} pertence a I, e se existe um x=7 que pertence a B e não pertence a A, {x} U A => {1,2,7} que pertence a I, e não tem ciclo.
Além destes, existem outros exemplos de matroids, eu vou mencionar apenas mais três, que são os mais comuns:
Sendo M=(E,I) um matroid, E vai ser o conjunto finito dos vectores de um espaço vectorial e o I vai ser o conjunto de subconjuntos lineares independentes dos vectores de E.
Sendo M=(E,I) um matroid (em que r e n são inteiros não negativos com o r<=n). E vai ser um conjunto de n-elementos e I o conjunto de todos os subconjuntos do E de tamanho r ou menor. É chamado de matroid uniforme de Rank r com n-elementos, e é denotado U(r,n). Por outras palavras, a função Rank de um matroid M=(S,I) é uma função r do conjunto dos subconjuntos de S do conjunto dos inteiros, definido por r(A)=max{|X|:X um subconjunto de A e de X em I}, para cada subconjunto A de S e uma função r do conjunto dos subconjuntos de S do conjunto dos inteiros, tais que, para cada subconjunto X de S e de cada y, z em S, as seguintes condições são satisfeitas:
1. r({ })=0;
2. r(x)<=r(xU{y})<=r(x)+1;
3. Se r(x U {y})=r(x U {z})=r(x), então r(x U {y,z})=r(x).
Em termos geométricos o matroid de Coxeter pode ser definido como um "Polytope do Matroid".
Para definir "Polytope do Matroid" vamos analizar a seguinte figura:
Nesta imagem M é um polytope conexo de dimensão 3, o S é o espelho da simetria da borda AB, de modo a que a reflexão em S troque os pontos A e o polytope M de B. Para que um "cubo" de dimensão n seja polytope do matroid é necessário que todas as reflexões nos espelhos das simetrias de todas as bordas de M deêm origem a um grupo finito. Neste caso, as simetrias das bordas M são simétricas ao cubo C. Mas como o cubo tem simetria finita (48), logo M é um polytope do matroid.
2.3.1 Classe dos matroids de Coxeter
Uma classe dos matroids de Coxeter, tem haver com as propriedades combinatórias das matrizes simétricas e "enviesadas". Considerando a matriz simétrica:
Agora a partir desta matriz, vamos listar os conjuntos dos deslocamentos pré-determinados que correspondem aos valores das diagonais da matriz. Vamos assinalar então, as primeiras e terceiras linha e coluna da matriz representada, formando outra matriz simétrica menor.
Vamos então codificar o conjunto de deslocamentos pré-determinados como 0 e 1, determinando que 1->x; 2->y e 3->z, de forma a que {1,3} corresponda 101 onde 1=x, 0=y e 1=z, como mostra a tabela seguinte:
|
Sets of indeces corresponding to non-zero minors |
0,1-vector
|
|
{1,2}
|
110
|
|
{2,3}
|
011
|
|
{1,3}
|
101
|
|
{1,2,3}
|
111
|
|
vazio |
000
|
Agora depois da tabela criada, vamos juntar todos os 0,1-vectores e construir o conjunto de todos os vértices de um polytope do matroid:
NOTA:
Os matroids também resolvem problemas que contenham penalidades, ou seja, problemas em que temos várias tarefas e no fim de cada tarefa temos uma nova tarefa, mas cada tarefa tem que terminar antes do tempo determinado para cada uma delas, se as tarefas não forem terminadas nesse tempo haverá penalidades. E o que se pretende é minimizar as penalidades.
INICIO
Optimização e Cardinalidade Máxima
O algoritmo de optimização é um algoritmo que tenta procurar um elemento de I contendo o máximo. dos algoritmos que estudámos o Spanning Tree é aquele que nos pode dar o membro máximo de I, ou seja, a cardinalidade máxima, e depois procurar através do Minimum Spanning Tree o elemento com peso mínimo.
Para optimizar utiliza-se o seguinte algoritmo:
Optim (M,m)
A<---- {}
ordenar SM, por oodem decrescente utilizando os m
Para x pertencente a SM
Fazer se A U {x} pertencer a IM
então A<------- A U {x}
return A
Considerando o grafo seguinte, vamos achar a cardinalidade máxima:
S= {A,B,C,D,E,F,G} I= {{A}; {A,B}; {A,B,C}; {A,B,C,D};.......;todos os subconjuntos de S possíveis sem ciclos}
1º Ordenar por ordem decrescente (ordenar SM): {18,16,14,13,12,11}
2º Adicionar cada valor x de SM a A, de modo a que x fique sem ciclo e seja membro de I:
{18}= A---> sem ciclo e membro de I {18,16,14,13}=A ---> sem ciclo e membro de I I {18,16}=A ---> sem ciclo e membro de I { 18,16,14,13,12}=A->sem ciclo e membro de I I {18,16,14}=A->sem ciclo e membro de I {18,16,14,13,12,11}=A--> com ciclo, logo 1 11 não pode pertencer a A
A={A,E,G,C,D,B}
A é o conjunto de cardinalidade máxima.
Um grafo de matroid é ponderado com peso, onde cada x membro de S tem um peso [m(x)].
Para cada membro de S existe um peso, o peso do conjunto A contido em S é a soma de x que é membro de A, ou seja, cada x pertencente a S tem m(x);
SG ={11,12,13,14,16,18} => m(11); m(12); m(13);...
O peso do conjunto A C S é:
W(A) = Sw(x), xi pertence a A
Quando queremos o máximo não há problema, mas neste caso com Minimum Spanning Tree queremos o mínimo. Estamos à procura de um mínimo para optimizar:
Optimizar: - Minimum => x pertence a A => M'i=m0-mi onde m0>Max(mi)
- Max => W normais
A={18,16,14,13,12} Max mi=18 m0>Max(m0), onde Max (m0) = 18, logo logo mo>18 ==> mo=19
mo = 19
M18=19-18=1; M16=19-16=3; M14=19-14=5; M13=19-13=6; M12=19-12=7
O mínimo de A é: 1+3+5+6+7=22.
INICIO
O duplo de um matroid M=(S,B) é a estrutura M*=(S,B*), onde B*={S\X: X em B}, um matroid "cográfico" é o duplo de um matroid gráfico. Tendo um matroid M, em que B é um conjunto das bases e o B* o conjunto das bases de um matroid, usando a mesma teoria que o matroid de M, então o M* é chamado o matroid duplo de m.
INICIO