MAC0338   Análise de Algoritmos

Máximo, maximal e guloso

Esta página é uma introdução à estratégia gulosa (ou paradigma guloso) de solução de problemas. Ela define os conceitos de máximo e maximal e discute um protótipo de problema de maximização.

Máximo e maximal

Suponha que S é uma coleção de subconjuntos de {1,..,n}. Um elemento X de S é máximo se não existe Y em S tal que

|Y|   >   |X|

(em outras palavras, |X| >= |Z| para todo Z em S). Um elemento X de S é máximal se não existe Y em S tal que

Y é superconjunto próprio de X

(em outras palavras, não existe Y que inclua X e mais alguma coisa). É evidente que todo máximo é maximal. Mas a recíproca longe está de ser verdadeira.

Exemplo

Suponha que os elemento de S são

{1,2}, {2,3}, {4,5}, {1,2,3}, {1,2,4}, {2,3,4,5} e {1,3,4,5}.

Há dois elemento máximos:  {2,3,4,5} e {1,3,4,5}. Há quatro elementos maximais:  {1,2,3}, {1,2,4}, {2,3,4,5} e {1,3,4,5}.

Um protótipo de problema de maximização

Suponha que n é um número grande e que S é uma enorme coleção de subconjuntos de {1,..,n}.  

PROBLEMA 1: Determinar um elemento máximo de S.
PROBLEMA 2: Determinar um elemento máximal de S.

O problema 1 é muito trabalhoso: é preciso examinar todos os elementos de S.  Já o problema 2 é muito fácil; basta aplicar o seguinte algoritmo "guloso", que abocanha o primeiro k que vê pela frente:

1  2  3  4  5  6  7

N := {1,..,n} X := Ø enquanto N <> Ø faça     escolha qualquer k em N     N := N-{k}     se X+{k} está em S então X := X+{k} devolva X

(A expressão "X+{k}" deve ser entendida como a união dos conjuntos X e {k}.) 

Cuidado! Muita gente confunde os dois problemas. Muita gente pensa que está calculando um máximo quando na verdade está apenas calculando um maximal . . .

Problemas dotados de "estrutura gulosa"

Dizemos que S "tem estrutura gulosa" se todos os seus elementos maximais são máximos. Para esse tipo de coleção, é muito fácil resolver o problema 1: basta executar o algoritmo guloso!

Às vezes a coisa é mais sutil. Para certas coleções S, o algoritmo guloso produz um elemento máximo desde que os elementos de N sejam escolhidos (na linha 4) em uma certa ordem "mágica". Para mostrar que uma certa ordem de escolha -- digamos 1, 2, 3, etc. -- força o algoritmo guloso a produzir um elemento máximo, é preciso verificar que

1. algum elemento máximo de S contém o objeto 1;
2. se X é máximo e contém 1 então X-{1} é um elemento máximo de S/1,
   onde S/1 é a coleção de todos os conjuntos da forma S-{1} tais que S está em S e contém 1.

A primeira propriedade é conhecida como Propriedade da Escolha Gulosa. A segunda, como Propriedade da Subestrutura Ótima.