Algoritmos Gulosos - Estratégias, Exemplos e Agendamento de Intervalos

CAPÍTULO 6 Algoritmos Gulosos Um algoritmo é dito guloso ou cobiçoso se constrói uma solução em pequenos passos tomando uma decisão miope a cada passo para otimizar algum critério relacionado ao problema geralmente não óbvio Quando um algoritmo guloso resolve algum problema não trivial geralmente implica na descoberta de algum padrão útil na estrutura do problema KLEINBERG TARDOS 2005 61 Exemplo de Algoritmos Gulosos 611 Agendamento de Intervalos Considere um conjunto de intervalos Rr1r2rnno qual cada intervalo ri inicia em sri e termina em fri Dizse que dois intervalos são compatíveis se eles não possuem sobreposição de tempo Desejase encontrar um subconjunto de R com o maior número de intervalos compatíveis entre si Pense sobre quais regras naturais poderiam ser empregadas nessa busca como critério simples e imagine como elas trabalham Alguns exemplos simples KLEINBERG TARDOS 2005 Inserir pela ordem de sri Inserir pela ordem de menor intervalo pois quer se selecionar o maior número possível deles Contagem de recursos não compatíveis e utilizar aquele com o menor número de incompatibilidades Nenhum desses critérios levariam a solução ótima para todas as instâncias do problema A Figura 11 ajuda a entender o porquê Utilizando a ordem sri o exemplo presente na Figura 11a a solução seria apenas um intervalo Quanto a ordem pelo menor intervalo a Figura 11b demonstra que apenas um intervalo seria marcado para uma instância cuja solução ótima conta com dois intervalos Ao utilizar o critério a quantidade mínima de intervalos não compatíveis a Figura 11c demonstra uma instância cuja solução ótima seria selecionar os 4 intervalos da primeira linha No entanto com esse último critério iniciariase selecionando o segundo intervalo da segunda linha e depois qualquer outro intevalo não conflitante na esquerda e na direita ou seja no máximo três intervalos Figura 11 Exemplos de Kleinberg e Tardos 2005 para refutar as três regras naturais levantadas anteriormente para o problema de agendamento do maior número de intervalos Para resolver o problema com uma estratégia gulosa Kleinberg e Tardos 2005 utilizam o menor valor de fi Então inicialmente se escolhe o intervalo de menor tempo que termina mais cedo na instância Depois selecionase o próximo intervalo compatível de menor tempo de fim até que não haja mais intervalos compatíveis O Algoritmo 32 exibe o algoritmo guloso sugerido por KLEINBERG TARDOS 2005 Algoritmo 32 Maior número de Intervalos Input O conjunto de intervalos R os valores sri e fri para cada intervalo ri R Criar lista L com os intervalos na ordem crescente de f 1 L sortR f Agora considere que L l1 l2 ln 2 A 3 i 1 4 while i n do 5 A A li 6 j i 1 Busca próximo intervalo compatível 7 while j n slj fli do 8 j j 1 9 i j 10 return A 6111 Complexidade do Problema de Agendamento de Intervalos Analisando a complexidade de tempo computacional para o Algoritmo 32 destacamse duas partes mais significativas do pseudocódigo A primeira é relativa ao algoritmo de ordenação utilizado na linha 1 Sabese que o algoritmo mais eficiente para ordenação demanda Θn log2 n Além dessa parte do algoritmo há o laço de repetição nas linhas 4 à 9 Podese observar que as instruções internas ao laço de repetição da linha 4 serão executadas um número de vezes igual a R Então o algoritmo demanda tempo computacional de ΘR log2 R 6112 Corretude do Problema de Agendamento de Intervalos Lema 611 Considerando que a solução ótima para o problema de agendamento de intervalos éO j1 j2 jm e a solução obtida pelo Algoritmo 32 é A i1 i2 ik têmse fir fjr para todo r k Prova Essa prova será realizada por indução Para r1 a afirmação é claramente verdadeira pois o algoritmo inicia selecionando Agora se analisa os casos nos quais r 1 Assumese a hipótese de que a afirmação é verdadeira para r1 e tentase provar isso para r Desse modo fir1 fjr1 Sabese que fjr1 sjr combinando isso com a hipótese da indução têmse fir1 sjr Então o intervalo jr está no conjunto de intervalos disponíveis quando o algoritmo seleciona ir Como o algoritmo sempre seleciona o intervalo de menor tempo de término têmse fir fjr Isso completa o passo da indução Teorema 612 Algoritmo 32 retorna o conjunto ótimo A Prova Provase por contradição Se A não é ótimo então um conjunto O precisa ter mais intervalos ou seja mk Aplicando o Lema 611 com rk têmse fik fjk Comomkentãoháumintervaloemjk1 emO Esse intervaloiniciadepois que jk termina e depois que ik termina Então depois de passar todos os intervalos incompatíveis linhas 7 e 8 com os intervalos i1 i2 ik haveria ainda um intervalo jk1 Mas o algoritmo guloso parou com o intervalo ik e ele só pára quando não houver mais intervalos em L a analisar ou seja uma contradição 612 Dijkstra O algoritmo de Dijkstra resolve o problema de encontrar um caminho mínimos de fonte única em um grafo GV E w ponderados dirigidos ou não Para esse algoritmo as arestasarcos não devem ter pesos negativos Então a função de pesos é redefinida como wE R A vantagem está em o algoritmo de Dijkstra ser mais eficiente que o do BellmanFord caso uma estrutura de dados adequada seja utilizada CORMEN et al 2012 O algoritmo repetidamente seleciona o vértice de menor custo estimado até então Quando esse vértice é selecionado ele não é mais atualizado e sua distância é propagada para suas adjacências A estrutura de dados C é utilizada no pseudocódigo abaixo para definir se um vértice foi visitado contém true ou não contém false Algoritmo 33 Algoritmo de Dijkstra Input um grafo GV E wE R um vértice de origem s V 1 Dv v V 2 Av null v V 3 Cv false v V 4 Ds 0 5 while v VCv false do 6 u arg minvVDv Cv false 7 Cu true 8 foreach v N u Cv false do 9 if Dv Du wu v then 10 Dv Du wu v 11 Av u 12 return D A 6121 Complexidade de Dijkstra Se o algoritmo de Dijkstra manter uma fila de prioridades mínimas para mapear a distância estimada no lugar de D o algoritmo tornase mais eficiente que o BellmanFord Seria utilizada uma operação do tipo EXTRACTMIN no lugar da que está na linha 6 para encontrar o vértice com a menor distância Ao extraílo da estrutura de prioridade não mais seria necessário Poderiase gravar sua distância mínima em uma estrutura auxiliar e não mais utilizar a estrutura de visitas C Ao atualizar as distâncias poderiase utilizar a operação de DECREASEKEY da fila de prioridades no lugar da operação da linha 10 Para essa fila de prioridades poderia se utilizar um Heap como o Heap Binário no qual a implementação das operações supracitadas tem complexidade de tempo computacional Olog2 n para o DECREASEKEY e Olog2 n para o EXTRACTMIN Para essa aplicação n V Utilizando essa estrutura de dados sabese que no máximo executase E operações de DECREASEKEY e V operações de EXTRACTMIN Então a complexidade computacional seria OVE log2 V Com Heap Fibonacci é possível obter resultados ainda melhores em tempo computacional 6122 Corretude do Algoritmo de Dijkstra Teorema 613 Dado um grafo G V E w E R e um vértice de origem s V o algoritmo de Dijkstra termina com Dv δs v para todo v V Prova Usase a seguinte invariante de laço no início de cada iteração do laço das linhas 5 11 Dv δs v para todo v o qual Cv true Para demonstrar isso dizse que Dv δs v no momento em que v é marcado como visitado ou seja na linha 7 Uma vez demonstrado isso recorrese à propriedade do limite superior Lema 543 para demonstrar que a igualdade é válida em todos os momentos a partir desse Inicialização Inicialmente Cu false para todos u V Então a invariante é trivialmente verdadeiro Manutenção Por contradição seja u o primeiro vértice para o qual Du δs u quando Cu tornase true O vértice u não pode ser s pois Ds δs v 0 nesse momento Como u s deve existir algum caminho de s a u senão Du δs u pela propriedade de inexistência de caminho Lema 544 o que contradiz Du δs u Assumese então que haja um mínimo caminho p de s a u Antes de Cu se tornar true o caminho p conecta um vértice v o qual Cv true a u Decompõese o caminho p em s p1 x y p2 u no qual Cx true e Cy false Afirmase que Dy δs y no momento que Cu se torna true Para provar essa afirmação observase que Cx true Então u foi escolhido como primeiro vértice para o qual Du δs u quando Cu se torna true tinhase Dx δs x quando Cx se tornou true A arestaarco x y foi relaxada naquele momento e a afirmação decorre da propriedade de convergência Lema 545 Agora podese obter uma contradição para provar que Du δs u Como y aparece antes de u em um caminho mínimo de s a u e todos os pesos das arestasarcos são nãonegativos temos δs y δs u e assim Dy δs y δs u Du pela propriedade do limite superior Lema 543 Porém como Cu false e Cy false quando u foi escolhido na linha 6 temse Du Dy Assim as duas desigualdades da Equação 61 são de fato igualdades o que dá Dy δs y δs u Du Consequentemente Du δs u o que contradiz a escolha de u Concluise que Du δs u quando Cu se torna true e que essa igualdade é mantida até o término do algoritmo Término No término quanto para Cv true para todo v V Dv δs v para todo v V Corolário 614 Ao executar algoritmo de Dijkstra Algoritmo 33 sobre o grafo G V E w ponderado orientado ou não sem ciclos de peso negativo para o vértice de origem s V o subgrafo dos predecessores Gπ será uma árvore de caminhos mínimos em s Prova Imediata pelo Teorema 613 e a propriedade do subgrafo dos predecessores Lema 548 613 Árvores Geradoras Mínimas Uma árvore geradora é um subconjunto acíclico uma árvore de todos os vértices de um grafo Dado um grafo ponderado G V E w o problema de encontrar uma arvore geradora mínima é aquele no qual buscase encontrar uma árvore que conecte todos os vértices do grafo G tal que a soma dos pesos das arestas seja o menor possível Seja T uma árvore geradora dizse que o custo da árvore geradora de T é dado por wT ΣuvT wu v Este capítulo apresenta dois métodos para encontrar árvores geradoras mínimas Kruskal e Prim Esses dois algoritmos gulosos se baseiam em um método genérico apresentado por Cormen et al 2012 Dado um grafo nãodirigido e ponderado G V E w esse método genérico encontra uma árvore geradora mínima O Algoritmo 34 apresenta o método genérico para uma árvore geradora mínima para G O método se baseia na seguinte invariante de laço Antes de cada iteração A é um subconjunto de alguma árvore geradora mínima A cada iteração determinase uma aresta que pode ser adicionada a A sem violar a invariante de laço A aresta segura é uma aresta que se adicionada a A mantém a invariante Algoritmo 34 Método Genérico de Cormen et al 2012 Input um grafo G V E w 1 A 2 while A não formar uma árvore geradora do 3 encontrar uma aresta u v que seja segura para A 4 A A u v 5 return A 6131 Propriedades do Método Genérico Teorema 615 Considere um grafo conexo nãodirigido ponderado G V E w Seja A E uma árvore geradora mínima de G Seja S V S qualquer conjunto de corte de G que respeita A e seja u v uma aresta leve¹ que cruza S V S então u v é uma aresta segura para A Prova Seja T uma árvore geradora mínima que inclui A e suponha que T não contenha a aresta leve u v pois se tiver o processo termina Constróise então outra árvore geradora mínima T que inclui A u v usando uma técnica de recortar e colar mostrando assim que u v é uma aresta segura para A Desde que u esteja em S e v em V S a aresta u v forma um ciclo com as arestas de caminho simples p de u a v em T No mínimo uma aresta em T está no caminho simples p e cruza o corte Considere que x y seja essa aresta de corte A aresta x y não está em A pois o corte respeita A Desde que x y está no único caminho de u a v em T removêlo divide T em duas componentes Adicionar u v o reconecta a forma de uma nova árvore geradora T T u v x y Depois mostrase que T é uma árvore geradora mínima Desde que u v é uma aresta leve atravessando S V S e x y também atravessa esse corte wu v wx y Por essa razão wT wT wu v wx y wT Mas T é uma árvore geradora mínima então wT wT Desse modo T precisa ser uma árvore geradora mínima também Falta mostrar que u v é uma aresta segura para A Têmse A T desde que A T e x y A então A u v T Consequentemente desde que T é uma árvore geradora mínima u v é uma aresta segura para A Corolário 616 Considere um grafo conectado nãodirigido e ponderado G V E w Seja A E incluído em alguma árvore geradora mínima de G e seja C VC EC um componente conectado uma árvore na floresta GA V A Se u v é uma aresta leve conectando C a algum outro componente em GA então u v é uma aresta segura ¹ de baixo custo Prova O corte VC VVC respeita A e u v é uma aresta leve para esse corte Por essa razão u v é uma aresta segura para A com base no Teorema 615 6132 Algoritmo de Kruskal O algoritmo de Kruskal inicia com V árvores conjuntos de um vértice cada Ele encontra uma aresta segura e a adiciona a uma floresta que está sendo montada conectando duas árvores na floresta Essa aresta u v é de peso mínimo Suponha que C1 e C2 sejam duas árvores conectadas por uma aresta u v Visto que essa deve ser uma aresta leve o Corolário 616 implica que u v é uma aresta segura para C1 Kruskal é um algoritmo guloso pois ele adiciona à floresta uma aresta de menor peso possível a cada iteração Um pseudocódigo de Kruskal pode ser visualizado no Algoritmo 35 O algoritmo se inicia definindo as V árvores desconectadas cada uma contendo um vértice linhas 2 a 4 Então criase uma lista das arestas E ordenadas por peso linha 5 Depois iterativamente se tenta inserir uma aresta leve em duas árvores que contém nodos não foram conectadas ainda linhas 7 a 9 Quando a inserção ocorre a estrutura de dados Sv que mapeia a árvore de cada vértice v é é atualizada O procedimento se repete até que todas as arestas tenham sido avaliadas no laço Algoritmo 35 Algoritmo de Kruskal Input um grafo G VEw 1 A 2 S V 3 foreach v V do 4 Sv v 5 E lista de arestas ordenadas por ordem crescente de peso 6 foreach u v E do 7 if Su Sv then 8 A A u v 9 x Su Sv 10 foreach w x do 11 Sw x 12 return A Complexidade do Algoritmo de Kruskal A complexidade de tempo do algoritmo de Kruskal depende da estrutura de dados utilizada para implementar o mapeamento das árvores de cada vértice ou seja da estrutura S do Algoritmo 35 Para a implementação mais eficiente verifique as operações de conjuntos disjuntos no Capítulo 21 de Cormen et al 2012 Sabese que para ordenar o conjunto de arestas na linha 5 devese executar um algoritmo de ordenação O mais eficiente conhecido demanda tempo ΘElog2E Desafio Qual estrutura de dado implementa a versão mais eficiente do Algoritmo de Kruskal 6133 Algoritmo de Prim O algoritmo de Prim é também um caso especial do método genérico apresentado no Algoritmo 34 O algoritmo de Prim é semelhante ao algoritmo de Dijkstra como pode ser observado no pseudocódigo do Algoritmo 36 As arestas no vetor A formam uma árvore única Essa árvore tem raízes em um vértice arbitrário r Essa arbitrariedade não gera problemas de corretudo no algoritmo pois uma árvore geradora mínima deve conter todos os vértices do grafo A cada iteração selecionase o vértice que é atingido por uma aresta de custo mínimo linha 7 sendo que o vértice selecionado adiciona suas adjacências e pesos na estrutura de prioridade Q que futuramente selecionará a chave de menor custo ou seja o vértice conectado a árvore que possui o menor custo Pelo Corolário 616 esse comportamento adicionase apenas arestas seguras em A Antes de cada iteração do laço da linha 6 a árvore obtida é dada por v Av v VrQ Os vértices que já participam da solução final são VQ Além disso para todo v Q se Av null então Kv e Kv é o peso de uma resta leve v Av que conecta o vértice v a algum vértice que já está na árvore que está sendo construída As linhas 7 e 8 indentificam um vértice u Q incidente em alguma aresta leve que cruza o corte VQ Q exceto na primeira iteração Ao remover u de Q o mesmo é acrescido ao conjunto VQ na árvore adicionando a aresta u Au na solução Se G é conexo para montar a árvore geradora mínima a partir do vetor resultante A Algoritmo 36 Algoritmo de Prim Input um grafo G V E w 1 r selecionar um vértice arbitrário em V Definindo o vetor dos antecessores A e uma chave para cada vértice K 2 Aν null ν V 3 Kν ν V 4 Kr 0 Definindo a estrutura de prioridade de chave mínima Q 5 Q V K 6 while Q do 7 u arg minvQKν 8 Q Qu 9 foreach ν Nu do 10 if ν Q wu ν Kν then 11 Aν u 12 Kν wu ν 13 return A Complexidade do Algoritmo de Prim Para implementar o algoritmo de Prim de maneira mais eficiente possível devese encontrar uma estrutura de prioridade que realize as operações de extração do valor mínimo e da alteração das chave de maneira rápida Desafio Qual a complexidade em tempo computacional da versão mais eficiente do Algoritmo de Prim 614 Códigos de Huffman Códigos de Huffman comprimem dados efetivamente de 20 a 90 A estratégia utilizada é empregar a frequência em que os caracteres aparecem para reduzir a representação dos mesmos Ao usarse uma tabela de tamanho fixo caracteres frequentes e os demais utilizam a mesma quantidade de bits A ideia de códigos de Huffman é aplicar a frequência na redução de codificação de caracteres mais frequentemente utilizados CORMEN et al 2012 Para o Algoritmo 37 considere que C é um conjunto de nodos de uma árvore binária ou árvore de Huffman no qual cfrequencia Z é a frequência dos caracteres representados em cada c C presentes no nodo e seus descendentes cesquerda null e cdireita null são os ponteiros para os descendentes na árvore de Huffman Algoritmo 37 Huffman Input um conjunto de caracteres C Criando fila de prioridade pela frequência mapeada por f 1 Q C f 2 for i 1 to C 1 do 3 alocar um novo nodo de uma árvore binária r 4 e EXTRACT MINQ 5 d EXTRACT MINQ 6 resquerda e 7 rdireita d 8 rfrequencia efrequencia dfrequencia 9 INSERTQ r 10 return EXTRACT MINQ O Algoritmo 37 retorna a Árvore de Huffman que é utilizada para estabelecer a nova codificação do conjunto de caracteres representados por C Geralmente considerase que cada ramificação para esquerda produz um número 0 e cada para direita produz um número 1 Então as arestas da raiz até um caractere nodo folha estabelece a nova codificação do mesmo 6141 Complexidade Desafio Qual a complexidade de tempo do Algoritmo 37