alg_gul__d99954bf-cdca-4ad5-8a65-d5de13e42ed6

Prévia do material em texto

TEORIA DOS 
GRAFOS E ANÁLISE 
DE ALGORITMOS
OBJETIVOS DE APRENDIZAGEM
 > Reconhecer as características dos algoritmos gulosos.
 > Elaborar exemplos de algoritmos gulosos por meio de grafos.
 > Aplicar os algoritmos gulosos em problemas de otimização.
Introdução
A construção de algoritmos eficientes e capazes de encontrar soluções de qua-
lidade para os problemas em que são aplicados é uma atividade que demanda 
o domínio de múltiplas técnicas e paradigmas de projeto. Além de dar suporte a 
uma avaliação mais precisa do desempenho e da acurácia de um procedimento 
em desenvolvimento, o uso de diferentes estratégias possibilita a ampliação da 
aplicabilidade do algoritmo. De fato, vários são os cenários em que o uso de uma 
dada técnica de projeto de algoritmos se adequa melhor a uma classe de problema 
com características específicas.
Neste capítulo, você vai estudar uma classe de algoritmos conhecida como 
gulosos e vai identificar como eles se diferenciam das demais abordagens de pro-
jetos de algoritmos. Por se adequarem bem a problemas envolvendo modelagens 
baseadas em grafos, alguns desses cenários serão apresentados e a solução via 
algoritmo guloso será detalhada. A versatilidade das estratégias gulosas será 
ainda mais explorada dentro do contexto da otimização combinatória. Por meio 
da análise de várias abordagens aplicadas a uma categoria de problema, você vai 
acompanhar como rejeitar e escolher decisões gulosas para compor um algoritmo 
dessa classe.
Algoritmos gulosos
Thiago Nascimento Rodrigues
Definição de algoritmos gulosos 
Muito da elegância e da análise de algoritmos deriva da interação entre 
os princípios gerais de projetos de algoritmos e da instanciação desses 
princípios para resolver problemas computacionais concretos. Não existe 
uma técnica universal capaz de resolver todos os problemas computacionais 
que podem ser encontrados. No entanto, existem vários paradigmas gerais 
de projeto que podem ser de grande ajuda na resolução de problemas 
presentes nos mais diversos domínios de aplicação. Um desses paradigmas 
é o dos algoritmos gulosos.
De acordo com Kleinberg e Tardos (2006), é difícil, ou mesmo impossível, 
definir precisamente o significado de algoritmo guloso. Ainda segundo os 
autores, um algoritmo é dito guloso se constrói uma solução em poucos 
passos e toma uma decisão “míope” a cada etapa a fim de otimizar algum 
critério. Em outras palavras, um algoritmo guloso faz uma escolha localmente 
ideal na esperança de que essa escolha venha a conduzi-lo a uma solução 
globalmente ideal. Muitas vezes é possível projetar vários algoritmos gu-
losos diferentes para um mesmo problema, cada qual otimizando, em uma 
vizinhança restrita e de forma incremental, alguma medida diferente em 
direção a uma solução. Portanto, o ponto central de um algoritmo guloso é 
que, em cada etapa ou iteração, a decisão por ele tomada deve apresentar 
as seguintes características:
 � ser viável — a decisão precisa satisfazer as restrições do problema;
 � ser localmente ótima — a decisão tem que ser a melhor escolha local 
dentre todas as escolhas viáveis e disponíveis em cada passo;
 � ser irrevogável — uma vez tomada a decisão, ela não pode ser alterada 
nos passos subsequentes do algoritmo.
Existem problemas para os quais uma sequência de escolhas lo-
calmente ideais produz uma solução ideal para cada instância do 
problema em questão. No entanto, existem outros para os quais essa realidade 
não se mostra verdadeira; para tais problemas, um algoritmo guloso ainda 
pode ser valioso se estamos interessados em uma solução aproximada ou se 
podemos ficar satisfeitos com ela.
Cientistas da computação consideram o desenvolvimento de estratégias 
gulosas como uma técnica geral de projeto de algoritmos, apesar de ser 
Algoritmos gulosos2
aplicável apenas a problemas de otimização. Via de regra, algoritmos gulosos 
são intuitivamente atraentes e simples. Dado um problema de otimização, 
geralmente é fácil descobrir como proceder de uma maneira gulosa, possi-
velmente depois de considerar algumas pequenas instâncias do problema. 
O que é geralmente mais difícil é provar, quando possível, que um algoritmo 
guloso produz uma solução ótima. Uma das maneiras comuns de demonstrar 
essa correção é por indução matemática: mostramos que uma solução par-
cialmente construída obtida pelo algoritmo guloso em cada iteração pode 
ser estendida para uma solução ótima para o problema geral. Uma segunda 
maneira é mostrar que, em cada etapa, o algoritmo se sai pelo menos tão bem 
quanto qualquer outro algoritmo se sairia no avanço em direção à solução 
do problema (LEVITIN, 2012).
De maneira geral, o projeto de um algoritmo guloso pode ser guiado por 
três passos principais:
 � resolver dois casos especiais do problema geral;
 � identificar as possíveis estratégias gulosas para o problema geral a 
partir das soluções dos casos particulares;
 � restringir as abordagens levantadas a uma estratégia específica e 
provar que essa estratégia resolve o problema geral.
É importante observar que as estratégias gulosas diferem da técnica de 
programação dinâmica. Essa técnica é usada para resolver problemas cujas 
soluções satisfazem relações de recorrência com a sobreposição de subpro-
blemas. Na programação dinâmica, cada um dos subproblemas menores é 
resolvido apenas uma vez, e os resultados são registrados numa tabela, em 
vez de se resolver subproblemas de maneira repetida. A tabela é então usada 
para se obter uma solução para o problema original.
A programação dinâmica é uma técnica de projeto de algoritmo 
inventada na década de 1950 por um proeminente matemático 
norte-americano chamado Richard Bellman. Foi originalmente pensada como 
um método geral para otimizar processos de decisão em vários estágios. Assim, 
a palavra "programação" no nome dessa técnica significa “planejamento”, e 
não se refere à programação de computadores. Depois de provar seu valor 
como uma importante ferramenta da matemática aplicada, a programação 
dinâmica acabou sendo considerada um princípio geral de projeto de algoritmos 
(LEVITIN, 2012).
Algoritmos gulosos 3
Em geral, a programação dinâmica é aplicada a problemas de otimização. 
Esses problemas podem ter muitas soluções possíveis. Cada solução tem um 
valor, e o objetivo é encontrar uma solução com o valor ideal (mínimo ou má-
ximo) ou, como é mais comumente conhecida, solução ótima. Ao desenvolver 
um algoritmo de programação dinâmica, uma sequência de quatro passos 
devem ser seguidos (CORMEN et al., 2009):
 � caracterizar a estrutura de uma solução ótima;
 � definir recursivamente o valor de uma solução ótima;
 � calcular o valor de uma solução ótima, geralmente por meio de uma 
abordagem de baixo para cima (bottom-up);
 � construir uma solução ótima a partir das informações computadas.
Grafos e algoritmos gulosos
Os grafos representam uma das estruturas de dados mais versáteis e úteis 
existentes e possuem várias aplicações envolvendo a representação de 
relacionamentos entre um conjunto de objetos. Cabe recordar que um grafo 
é representado por um par G = (V, A), onde V denota o conjunto de vértices e 
A denota o conjunto de arestas. Dependendo se G é direcionado ou não, as 
arestas podem ou não ser ordenadas em A. Um típico problema modelado 
com o uso de grafos é conhecido como o problema da coloração de vértices 
(arestas), ou simplesmente coloração de grafos.
Em poucas palavras, o problema pode ser descrito da seguinte forma: dado 
um grafo G = (V, A), é preciso colorir os vértices de V usando o menor número 
de cores tais que i e j tenham cores distintas para todo (i, j) ∈ V. A coloração 
de vértices surge em muitas aplicações de agendamento e de agrupamento 
ou clusterização. A alocação de registros na otimização realizada por um com-
pilador é uma aplicação canônica de coloração. Nesse caso, cada variável de 
um determinado fragmento de programa tem um intervalo de tempo durante 
o qual seu valor deve ser mantido intacto, em particularapós ser inicializado e 
antes de seu uso final. Quaisquer duas variáveis cujos tempos de vida se cruzem 
não podem ser colocadas em um mesmo registro. Nesse cenário, a modelagem 
envolve a construção de um grafo em que cada vértice corresponde a uma vari-
ável, e o grafo deve ter uma aresta entre quaisquer dois vértices cujos tempos 
de vida se sobrepõem. Considerando que nenhuma das variáveis atribuídas à 
mesma cor conflitem, todas elas podem ser atribuídas a um mesmo registro 
(SKIENKA, 2008). A Figura 1 apresenta um exemplo do problema. Nesse caso, 
para um grafo de seis vértices é possível apresentar três soluções distintas. 
Algoritmos gulosos4
Figura 1. Soluções possíveis para o problema da coloração de um grafo de seis vértices.
Fonte: Adaptada de Techie Delight (2021).
Infelizmente, não existe um algoritmo eficiente disponível para o problema 
de coloração de um grafo com um número mínimo de cores, já que o problema 
foi provado NP-completo (HOLYER, 1981). No entanto, existem algoritmos 
aproximados para resolver o problema. 
Assim, vejamos o pseudocódigo de um algoritmo guloso apresentado 
para atribuição de cores. Observe que o algoritmo não garante o uso de uma 
quantidade mínima de cores, mas garante um limite superior para o número 
de cores. Esse algoritmo básico jamais usa mais do que d + 1 cores, onde d é 
o grau máximo de um vértice no grafo fornecido. Outra observação relevante 
é que o conjunto de cores fornecidas deve ser avaliado a cada iteração do 
laço, isso porque todas as cores já usadas precisam ser testadas quanto 
ao seu uso na adjacência do vértice corrente antes que uma nova cor seja 
empregada. Em relação ao desempenho do algoritmo, em seu pior caso ele 
apresenta complexidade da ordem de O(|V|2 + |A|).
Algoritmo guloso para coloração de grafos:
 � entrada: um grafo G = (V, A) e um conjunto D = { d1, …, dk} de k cores;
 � saída: grafo G com os vértices coloridos;
1. colora o primeiro vértice de V com a primeira cor d1 ∈ D;
2. para os restantes |V| – 1 vértices faça;
3. colora o vértice corrente com a primeira cor de D ainda não usada em 
nenhum vértice adjacente;
4. retornar G.
Algoritmos gulosos 5
A Figura 2 descreve o funcionamento do algoritmo. Inicialmente, o primeiro 
vértice é colorido com uma cor (passo 2, Figura 2a). Em cada um dos próximos 
passos (Figuras 2b e 2c), uma nova cor é utilizada, já que o reaproveitamento 
de uma cor implicaria em que dois vértices adjacentes fossem coloridos com 
um mesma cor. Nos dois últimos passos, (Figuras 2d e 2e), a primeira cor pôde 
ser reutilizada, já que o seu emprego não viola a restrição do problema. 
Logo, um conjunto de três cores foi suficiente para colorir o grafo de cinco 
vértices original. 
Figura 2. Passo a passo da coloração de cada vértice por um algoritmo guloso.
Fonte: Sharma (2021, documento on-line).
Outro problema tradicionalmente modelado com grafos e encontrado em 
diversos cenários é conhecido como o problema da cobertura de vértices, ou 
problema da cobertura mínima. Dado um grafo G = (V, A), o problema envolve 
encontrar uma resposta para a seguinte questão: qual o menor conjunto 
S ⊂ V tal que cada aresta (x, y) ∈ A contenha pelo menos um vértice de S? 
Algoritmos gulosos6
O problema da cobertura de vértices é, na verdade, um caso especial de um 
problema mais geral conhecido como cobertura de conjunto. Esse problema 
toma como entrada um par Σ = (X, S), chamado de conjunto sistema, onde 
X = { x1, …, xm } é um conjunto finito de objetos, chamado de universo, e 
S = { s1, …, sn }é uma coleção arbitrária de subconjuntos de X, tais que cada 
elemento de X pertence a pelo menos um conjunto de S.
Um conjunto C de vértices de um grafo não dirigido cobre uma aresta 
(v, w) do grafo se v pertence a C ou w pertence a C (ou ambos). Logo, 
uma cobertura por vértices de um grafo é “[...] um conjunto de vértices que 
cobre todas as arestas. Em outras palavras, uma cobertura é um conjunto de 
vértices que contém pelo menos uma das pontas de cada aresta” (FEOLILOFF, 
2020, documento on-line). 
Nesse cenário, a questão fundamental envolvendo a cobertura de con-
juntos é determinar o menor número de conjuntos necessário para cobrir 
o conjunto universo inteiro. Uma cobertura S é definida como uma subco-
leção de conjuntos cuja união cobre X. Na Figura 3a, os elementos de X são 
representados por pontos pretos, e os conjuntos s1, …, s6 são indicados por 
retângulos. Neste caso, existe uma cobertura de tamanho três, consistindo em 
s3, s4 e s5, como pode ser visto na Figura 3b. Cabe ressaltar que os conjuntos 
dessa cobertura não se sobrepõem, o que é às vezes chamado de cobertura 
exata. Em geral, os conjuntos cobertura podem se sobrepor (MOUNT, 2017).
Figura 3. Exemplo do problema da cobertura de conjuntos.
Fonte: Mount (2017, documento on-line).
Algoritmos gulosos 7
Para transformar a cobertura de vértices em um problema de cobertura de 
conjunto, basta considerar o conjunto universo X como o conjunto de arestas 
de um grafo G e definir si como o conjunto de arestas incidentes a um vértice 
i. Um conjunto de vértices define uma cobertura de vértices no grafo G se 
os subconjuntos correspondentes definirem uma cobertura definida neste 
caso particular. No entanto, uma vez que cada aresta pode estar em apenas 
dois subconjuntos diferentes, as instâncias de cobertura de vértice são mais 
simples do que a cobertura de conjunto geral. O problema da cobertura de 
vértices é relativamente mais leve computacionalmente dentre os problemas 
NP-completos — Feige (1998) indica a NP completude do problema — e pode 
ser resolvido de forma mais eficaz que o problema da cobertura de conjunto 
geral (SKIENKA, 2008).
Um algoritmo guloso para o problema da cobertura de vértices é apresen-
tado a seguir. Ele é baseado na remoção das arestas incidente aos vértices da 
aresta selecionada a cada iteração, e tem complexidade da ordem de O(|V| + 
|A|). A Figura 4 apresenta um exemplo de execução do algoritmo. 
Figura 4. Exemplo do problema da cobertura de vértices.
Fonte: Geeks for Geeks (2020, documento on-line).
A aresta inicial é assumida como sendo a (b, c) e os vértices que a compõe 
são incluídos no conjunto cobertura C. Na primeira iteração, todas as demais 
arestas que incidem sobre um dos vértices dessa aresta são removidas; logo, 
deixam o conjunto A’ as arestas (a, b), (b, d), (c, e) e (c, f). As arestas removidas 
estão representadas por linhas tracejadas na Figura 4b. Finalmente, apenas 
uma aresta resta no conjunto A’ — a aresta (d, e), e ela é então adicionada ao 
conjunto cobertura, como mostrado na Figura 4c. Portanto, a menor cobertura 
obtida é composta pelos vértices { b, c, d } ou pelos vértices { b, c, e }.
Algoritmos gulosos8
Algoritmo guloso para cobertura de vértices de grafos:
 � entrada: um grafo G = (V, A);
 � saída: um conjunto C correspondente à cobertura dos vértices de G;
1. C ← ∅;
2. A’ ← A;
3. enquanto A’ ≠ ∅ vértices faça;
4. tome uma aresta (u, v) arbitrária de A’;
5. C = C ∪ { u, v };
6. remova de A’ todas as arestas incidentes a u ou a v;
7. retornar C.
Algoritmos gulosos em problemas 
de otimização
De acordo com Cormen (2013), a melhor maneira de entender a ideia por trás 
do projeto de algoritmos gulosos é pela análise de exemplos que implementam 
estratégias gulosas. Seguindo essa abordagem, um tradicional problema 
explorado nesse contexto é aquele conhecido como escalonamento de inter-
valos, ou escalonamento de recurso (ROUGHGARDEN, 2019). Consideremos um 
conjunto de pedidos { 1, 2 ... n }, onde a enésima solicitação corresponde a um 
intervalo de tempo começando em s(i) e terminando em f(i). Um subconjunto 
de solicitações é dito compatível se não houver qualquer sobreposição no 
tempo. O objetivo é aceitar o maior subconjunto compatível possível. Con-
juntos compatíveis de tamanho máximo são chamados de conjuntos ótimos.
A ideia básica de um algoritmo guloso para o problema de escalonamento 
de intervalos é usar uma regra simples para selecionaruma primeira solici-
tação i1. Uma vez que a solicitação i1 é aceita, todas as demais solicitações 
que não são compatíveis com ela são rejeitadas. Em seguida, a próxima 
solicitação i2 para ser aceita e, novamente, rejeitamos todas as solicitações 
que não são compatíveis com i2 selecionada. O processo continua até que 
acabem todos pedidos. O desafio em projetar um bom algoritmo guloso é 
decidir qual regra simples usar para a seleção — e há muitas regras naturais 
para esse problema que não geram boas soluções.
Para exemplificar o desafio de se definir uma boa regra de escolha de 
pedidos, é possível considerar três estratégias distintas. A regra mais óbvia 
pode ser sempre selecionar o pedido disponível que começa primeiro — ou 
seja, aquele com tempo de início mínimo s(i), o que, por sua vez, faz com que o 
Algoritmos gulosos 9
recurso comece a ser usado o mais rápido possível. Esse método, porém, não 
produz uma solução ótima. Se o primeiro pedido for de um intervalo muito 
longo, então, ao aceitar o pedido, muitos pedidos de intervalos de tempo 
mais curtos serão rejeitados. Uma vez que o objetivo é atender o máximo de 
solicitações possível, a solução encontrada será inferior à solução ideal. Em 
uma hipótese bem desfavorável — por exemplo, quando o tempo de término 
f(i) é o máximo entre todas as solicitações — a solicitação aceita mantém o 
recurso ocupado por todo o tempo. Nesse caso, o método guloso aceitaria um 
único pedido, enquanto a solução ideal poderia aceitar muitos. Essa situação 
é ilustrada na Figura 5a.
Figura 5. Instâncias do problema de escalonamento de intervalo em que algoritmos gulosos 
não conseguem encontrar a solução ideal.
Fonte: Kleinberg e Tardos (2006, p. 117).
Outra estratégia intuitiva seria começar aceitando a solicitação que requer 
o menor intervalo de tempo — ou seja, a solicitação para a qual f(i) – s(i) é 
o menor possível. Embora essa regra seja um pouco melhor que a anterior, 
ela ainda pode produzir um escalonamento não ótimo. Na Figura 5b, por 
exemplo, a aceitação do intervalo mais curto ao meio impediria os outros 
dois, que formam uma solução ótima, de serem aceitos. Fica claro que nesse 
caso o problema é que a segunda solicitação compete com a primeira e com a 
terceira — ou seja, aceitar esse pedido acarretaria na rejeição dos outros dois.
Algoritmos gulosos10
Tomando como base a segunda estratégia descrita, um algoritmo guloso 
poderia ser criado com a seguinte abordagem de escolha de pedidos: para 
cada pedido, o número de outras solicitações que não são compatíveis seria 
contado e a solicitação que tivesse o menor número de solicitações não 
compatíveis seria aceita. Em outras palavras, o intervalo com o menor número 
de "conflitos" seria aceito. Essa escolha gulosa levaria à solução ótima no 
exemplo da Figura 5b. No entanto, para uma instância do problema como 
representado na Figura 5c, a única solução ideal possível (aceitar as quatro 
solicitações na linha superior) não seria obtida. Com essa terceira estratégia 
gulosa, a solicitação do meio na segunda linha é aceita, o que garante uma 
solução de tamanho não superior a três.
Uma regra gulosa que leva à solução ótima é baseada em uma quarta 
ideia: aceitar inicialmente o pedido que termina primeiro, ou seja, o pedido 
i para o qual f(i) é o menor possível. Essa também é uma ideia bastante 
natural: ela garante que o recurso fique disponível o mais rápido possível 
enquanto ainda atende a uma solicitação. Dessa forma, é possível maxi-
mizar o tempo restante para atender a outras solicitações. Para definir um 
algoritmo de maneira mais formal, R será usado para denotar o conjunto 
de solicitações que ainda não foram nem aceitas nem rejeitadas e A vai 
denotar o conjunto de solicitações aceitas. O pseudocódigo do algoritmo 
é apresentando a seguir. 
Algoritmo escalonamento guloso:
 � entrada: um conjunto R de todas as requisições e um conjunto A vazio;
 � saída: Conjunto A com todas as requisições aceitas;
1. enquanto R ≠ ∅ faça;
2. escolha uma requisição i ∈ R com menor tempo para finalização;
3. A ← A ∪ { i };
4. remova todas requisições de R que não sejam compatíveis com i;
5. fim enquanto;
6. retornar A.
Um exemplo de execução do algoritmo é ilustrado na Figura 6. Em cada 
etapa, o intervalo selecionado está indicado com linhas mais escuras, e os 
intervalos excluídos na etapa correspondente são indicados com linhas 
tracejadas.
Algoritmos gulosos 11
Figura 6. Exemplo de execução do algoritmo de escalonamento guloso.
Fonte: Kleinberg e Tardos (2006, p. 119).
Em termos de implementação, o algoritmo guloso apresentado pode 
ser construído de forma a funcionar com uma complexidade da ordem 
O(n log n). Primeiramente, é preciso ordenar as n solicitações de acordo 
com o tempo para finalização e rotulá-las nessa ordem, ou seja, assumir 
que f(i) < f(j) quando i < j. Essa ordenação leva um tempo O(n log n) quando 
algoritmos como Quick Sort (melhor caso) ou Merge Sort são empregados. 
Um tempo O(n) adicional será necessário para a construção de um vetor 
S[ 1 ... n ] com a propriedade de que S[i] contém o valor s(i). Feito isso, as 
requisições devem ser selecionadas processando os intervalos em ordem 
crescente de f(i). O primeiro intervalo sempre deve ser selecionado. Então, 
deve-se iterar através dos intervalos em ordem até atingir o primeiro in-
tervalo j para o qual s(j) ≥ f(1) — este corresponderá ao próximo intervalo 
a ser selecionado. De forma mais geral, se o intervalo mais recente que for 
selecionado terminar no tempo f, é preciso continuar iterando pelos intervalos 
subsequentes até que o primeiro j para o qual s(j) ≥ f seja alcançado. Dessa 
forma, o algoritmo guloso recém analisado pode ser implementado gastando 
um tempo constante por intervalo, fazendo com que esta parte do algoritmo 
demande um tempo O(n).
Algoritmos gulosos12
Neste capítulo, foi possível caracterizar uma classe de algoritmos larga-
mente utilizada tanto no meio científico quanto no profissional — os algorit-
mos gulosos. Eles apresentam uma estrutura geral sucinta, o que possibilita 
a avaliação de várias estratégias de decisão local para identificar a que 
melhor se adequa ao cenário em que o algoritmo está sendo empregado. No 
contexto da teoria dos grafos, alguns problemas foram modelados com essas 
estruturas e algoritmos gulosos foram utilizados para exemplificar o passo a 
passo na busca por soluções ótimas. A aplicabilidade desses algoritmos foi 
adicionalmente explorada sob a perspectiva de problemas de otimização. Em 
particular, o problema do escalonamento de intervalos foi detalhado. Diferen-
tes abordagens gulosas foram avaliadas para o problema, dando suporte à 
identificação de uma estratégia capaz de encontrar soluções ótimas para ele.
Referências
CORMEN, T. et al. Introduction to algorithms. 3. ed. London: MIT Press, 2009.
CORMEN, T. H. Algorithms unlocked. Cambridge: MIT Press, 2013.
FEIGE, U. A threshold of ln n for approximation set cover. Journal of the Association for 
Computing Machinery, v. 45, n. 4, 1998.
FEOLILOFF, P. Cobertura por vértices. [S. l.: s. n.], 2020. Disponível em: https://www.
ime.usp.br/~pf/analise_de_algoritmos/aulas/v-cover.html. Acesso em: 6 mar. 2021.
GEEKS FOR GEEKS. Vertex cover problem: set 1 (introduction and approximate algorithm). 
[S. l.: s. n.], 2020. Disponível em: https://www.geeksforgeeks.org/vertex-cover-problem-
-set-1-introduction-approximate-algorithm-2/. Acesso em: 6 mar. 2021.
HOLYER, I. The NP-completeness of edge-coloring. Society for Industrial and Applied 
Mathematics, v. 10, n. 4, p. 718–720, 1981.
KLEINBERG, J.; TARDOS, E. Algorithm design. Boston: Pearson Education, 2006.
LEVITIN, A. Introduction to the design and analysis of algorithms. 3. ed. New Jersey: 
Addison-Wesley, 2012.
MOUNT, D. Greedy approximation: set cover. [S. l.: s. n.], 2017. Disponível em: https://
www.cs.umd.edu/class/fall2017/cmsc451-0101/Lects/lect09-set-cover.pdf. Acesso 
em: 6 mar. 2021.
ROUGHGARDEN, T. Algorithms illuminated:part 3: greedy algorithms and dynamic 
programming. New York: Soundlikeyourself, 2019.
SHARMA, P. Graph coloring greedy algorithm [O(V^2 + E) time complexity]. [S. l.: s. n.], 
2021. Disponível em https://iq.opengenus.org/graph-colouring-greedy-algorithm/. 
Acesso em: 6 mar. 2021.
SKIENKA, S. The algorithm design manual. 2. ed. New York: Springer, 2008.
TECHIE DELIGHT. Graph coloring problem. [S. l.: s. n., 2021?]. Disponível em: https://www.
techiedelight.com/greedy-coloring-graph/. Acesso em: 6 mar. 2021.
Algoritmos gulosos 13
Leituras recomendadas
DASGUPTA, S.; PAPADIMITRIOU, C.; VAZIRANI, U. Algorithms. New York: Mc Graw Hill, 2008.
SEDGEWICK, R.; WAYNE, K. Algorithms. 4. ed. Boston: Pearson Education, 2011.
Os links para sites da web fornecidos neste capítulo foram todos 
testados, e seu funcionamento foi comprovado no momento da 
publicação do material. No entanto, a rede é extremamente dinâmica; suas 
páginas estão constantemente mudando de local e conteúdo. Assim, os editores 
declaram não ter qualquer responsabilidade sobre qualidade, precisão ou 
integralidade das informações referidas em tais links.
Algoritmos gulosos14