Análise de Algoritmos

Prévia do material em texto

Ariel Da Silva Dias
PROJETO E ANÁLISE DE 
ALGORITMOS
Sumário
INTRODUÇÃO ������������������������������������������������� 3
ALGORITMOS GULOSOS �������������������������������� 4
Problema do agrupamento de alunos ��������������������������������� 8
ALGORITMO DA MOCHILA ��������������������������11
ALGORITMOS DE PROGRAMAÇÃO 
DINÂMICA ����������������������������������������������������15
Recursão e programação dinâmica ����������������������������������� 17
Programação dinâmica e série de Fibonacci �������������������� 17
ALGORITMOS DE DIVISÃO E CONQUISTA ��� 20
Torre de Hanoi ��������������������������������������������������������������������� 22
Divisão e conquista e programação dinâmica ������������������ 24
BACKTRACKING ������������������������������������������26
Exemplo de uso do backtracking ��������������������������������������� 27
Problema das n-rainhas ������������������������������������������������������ 29
Encontrar caminhos Hamiltonianos em um grafo ������������ 32
CONSIDERAÇÕES FINAIS ����������������������������33
REFERÊNCIAS BIBLIOGRÁFICAS & 
CONSULTADAS ��������������������������������������������35
2
INTRODUÇÃO
Em um projeto de algoritmo não existe uma “bala 
de prata” que seja a cura para todos os problemas 
de computação� Diferentes problemas requerem 
o uso de diferentes tipos de técnicas� Um bom 
programador usa todas essas técnicas com base 
no tipo de problema� Algumas técnicas comumen-
te usadas são a divisão e conquista, algoritmos 
gulosos (que curiosamente não são algoritmos, 
mas sim uma técnica), programação dinâmica e 
backtracking�
Neste e-book, estudaremos as diferentes técnicas 
de implementação de algoritmos, citando exem-
plos com práticas que podem ser reproduzidas em 
diferentes linguagens de programação�
Todas essas técnicas possuem um objetivo: en-
contrar uma solução ótima para um dado problema 
computacional� Você vai perceber, por exemplo, que 
qualquer técnica de desenvolvimento é capaz de 
resolver um problema, entretanto, surgem outros 
problemas: o tempo de execução e a quantidade 
de memória utilizada� Desse modo, essas técnicas 
que serão apresentadas a seguir tem o objetivo de 
melhorar a execução e diminuir a complexidade�
3
ALGORITMOS GULOSOS
O algoritmo guloso ou ganancioso é uma estraté-
gia de solução de problemas que toma decisões 
localmente ótimas em cada estágio na esperança 
de alcançar uma solução globalmente ótima� Esse 
algoritmo simples e intuitivo pode ser aplicado 
para resolver qualquer problema de otimização 
que exija o resultado ótimo máximo ou mínimo, 
além disso, a melhor coisa sobre esse algoritmo 
é que é fácil de entender e implementar�
A complexidade do tempo de execução associada 
a uma solução gananciosa é bastante razoável� 
No entanto, você pode implementar uma solução 
gananciosa somente se a declaração do problema 
seguir duas propriedades mencionadas a seguir:
 y Propriedade da escolha gananciosa: escolher 
a melhor opção em cada fase pode levar a uma 
solução ótima global (geral)�
 y Subestrutura ótima: se uma solução ótima 
para o problema completo contém as soluções 
ótimas para os subproblemas, o problema tem 
uma subestrutura ótima�
Seguindo as etapas que serão apresentadas, você 
será capaz de formular uma solução gananciosa 
para a declaração de problemas:
4
 y Etapa 1: em um determinado problema, encontre 
a melhor subestrutura ou subproblema�
 y Etapa 2: determine o que a solução incluirá 
(por exemplo, maior soma, caminho mais curto)�
 y Etapa 3: crie um processo iterativo para analisar 
todos os subproblemas e criar uma solução ideal�
Como exemplo, vamos considerar um caso bem 
próximo de nossa realidade e que pode ser explicado 
no formato de um algoritmo (não necessariamente 
com programação)�
Declaração do problema: Seu carro pode percorrer 
uma quantidade x de quilômetros com o tanque 
cheio e você tem que chegar a B vindo de A� Você 
tem que chegar ao seu destino com um número 
mínimo de reabastecimentos�
Existem três opções:
 y reabastecer no posto de gasolina mais próximo;
 y reabasteça no posto de gasolina mais distante 
possível;
 y viajar até que não haja combustível�
A segunda opção parece a melhor, em vez de arris-
car encontrar um posto de combustível no ponto 
em que nosso combustível acabará�
Vamos olhar para o algoritmo, começamos nossa 
jornada e viajamos para o posto de combustível 
mais distante que podemos chegar� A partir daí, 
5
repetimos o processo escolhendo a segunda opção 
novamente e chegamos ao posto de combustível 
mais distante possível e assim faremos até che-
garmos ao nosso destino�
Observe então o nosso algoritmo:
 y Primeiro fazemos uma escolha gananciosa 
(para chegar ao posto de gasolina mais distante 
possível);
 y Dessa forma, reduzimos nosso problema em 
subproblemas (dividindo nossa jornada em vários 
postos de gasolina);
 y Em seguida, iteramos sobre o subproblema 
(alcançar o posto de gasolina mais distante pos-
sível) no tempo determinado�
Um possível código é apresentado na tabela 1 a 
seguir�
Tabela 1: código do exemplo de abastecimento�
1 class combustivel{
2
3 val maximaDistanciaCarroPodePercorrer: Int = 400
4 val matrizParadasCombustivel: Array = ar-
rayOf(100, 350, 400, 600, 700, 800, 900, 1200)
5 val numeroParadas = matrizParadasCombustivel.
size
6 var numeroAbastecimentos = 0
7 var posicaoParada = 0
8
9 fun encontrarMinAbast(): Int {
6
10
11 while (destinoNaoEncontrado()) {
12 val ultimaParadaAbastecimento = 
posicaoParada
13
14 while (destinoNaoEncontrado() and isNextSto-
pReachable()) {
15 posicaoParada += 1
16 }
17
18 if (posicaoParada == 
ultimaParadaAbastecimento)
19 return -1 
20
21 if (destinoNaoEncontrado()) {
22 numeroAbastecimentos++
23 }
24 }
25
26 return numeroAbastecimentos
27 }
28
29 private fun isNextStopReachable(): Boolean {
30 return ((matrizParadasCombustivel[posicaoParada 
+ 1] - matrizParadasCombustivel[posicaoParada])enquadram nesse 
intervalo� Agrupe-os�
 y Em seguida, passe para o próximo número a 
partir do último número agrupado O(n)�
 y Repita o processo�
9
Portanto, semelhante ao problema anterior do 
combustível, encontramos uma abordagem O(n) 
se as idades forem dadas de maneira ordenada, 
caso contrário, se você incluir a classificação dos 
números, é um O(nLogn) – o que ainda é um enor-
me melhoria comparando a O(2n), e isso faz uma 
enorme diferença� Talvez o problema de tempo 
exponencial mais famoso em NP, por exemplo, seja 
encontrar fatores primos de um grande número� 
Verificar uma solução requer apenas multiplicação, 
mas resolver o problema parece exigir sistemati-
camente experimentar muitos candidatos�
10
ALGORITMO DA MOCHILA
Esse é um dos problemas clássicos da computação: 
imagine que você tem que planejar uma longa via-
gem e tem uma mochila para caber os vários itens 
que precisa carregar, por exemplo, uma seleção 
de frutas que vai lhe nutrir durante toda a viagem�
Como você tem uma capacidade limitada nesta 
mochila, decidiu levar diferentes quantidades de 
diferentes frutas, mas o objetivo final é maximizar 
a “ingestão de calorias” que você obtém de sua 
mochila cheia�
Esse, novamente, é um problema de maximização 
em que estamos tentando descobrir a combinação 
de itens alimentares que nos dão o máximo valor 
deles�
Vamos supor que Q signifique os pesos, enquanto 
V corresponde ao valor do alimento, em termos 
de ingestão de calorias� Repetimos os seguintes 
passos até que nossa mochila esteja cheia:
 y Podemos descobrir a fruta mais valiosa divi-
dindo os pesos por valores, ou seja, peso/valores�
 y Encha a mochila com esse produto mais valioso 
(chamaremos de PMV)�
 y Podemos encher parcialmente ou completa-
mente esse produto na mochila� Se conseguirmos 
preencher completamente e ainda houver espaço 
11
para outros itens, descubra o próximo melhor PMV 
e repita essas etapas�
O problema da mochila modela uma situação 
análoga ao enchimento de uma mochila, que não 
pode mais suportar um certo peso, com todo ou 
parte de um determinado conjunto de objetos 
tendo cada elemento um peso e um valor� Os itens 
colocados na mochila devem maximizar o valor 
total, sem ultrapassar o peso máximo�
Na teoria encontramos uma solução que funciona 
e tem um processo repetitivo de quebrar problemas 
em menores e, portanto, temos um algoritmo guloso�
A ideia é adicionar os objetos mais eficazes como 
prioridade, até que a bolsa fique saturada, observe 
o pseudocódigo a seguir:
Tabela 2: código algoritmo guloso
1 mochila(n,v,w,W)
2 for j=0 to j=W
3 t[0, j]=0 
4 for i=1 to n
5 for j=0 to W
6 if w[i]>j 
7 t[i, j]=t[i - 1, j]
8 else 
9 t[i, j] = max(t[i - 1, j], t[i - 1, j - w[i]]+v[i])
Fonte: elaborado pelo autor�
12
No algoritmo da tabela 2, a função mochila recebe 
quatro parâmetros:
 y n  número de itens;
 y v[i]  valor do i-ésimo item;
 y w[i]  peso do i-ésimo item;
 y W  capacidade máxima da mochila.
Portanto, precisamos escolher os itens cujo peso 
total não ultrapasse o limite de peso e seu valor 
total seja o mais alto possível� Por exemplo, su-
ponha os seguintes itens com seus pesos e seus 
respectivos valores:
 y Item 1  R$ 1,00 e pesa 1kg
 y Item 2  R$ 8,00 e pesa 3kg
 y Item 3  R$ 18,00 e pesa 5kg
 y Item 4  R$ 22,00 e pesa 6kg
 y Item 5  R$ 28,00 e pesa 7kg
Queremos colocar esses itens em uma mochila, 
no entanto a mochila suporta, no máximo, 11kg� 
Deste modo, a melhor solução para o exemplo 
acima é escolher o item de 5kg e o item de 6kg, 
que dá um valor máximo de R$ 40,00 dentro do 
limite de peso�
A complexidade desse algoritmo, conforme des-
crito, é O(n²), pois haverá um loop while e um loop 
for� Entretanto, se ordenarmos os itens em ordem 
decrescente de relação Valor/Peso, podemos sim-
13
plesmente escolher os itens em ordem decrescente 
até que a mochila esteja cheia, o que, portanto, 
torna nossa solução O(N log N)�
Embora declarado e resolvido de maneira simples, 
o problema da mochila pode ser mapeado dire-
tamente e usado como protótipo para inúmeros 
problemas práticos� As aplicações diretas incluem:
 y uma empresa de transporte tentando embalar 
o maior volume de pacotes em um avião de trans-
porte sem quebrar a capacidade de peso;
 y o desejo de uma equipe esportiva profissio-
nal de construir uma equipe que atenda a várias 
projeções estatísticas sem quebrar o teto salarial�
Além do algoritmo guloso, também podemos utili-
zar a programação dinâmica e recursividade para 
resolver o problema da mochila�
14
ALGORITMOS DE 
PROGRAMAÇÃO 
DINÂMICA
A programação dinâmica é uma excelente abordagem 
que pode ser aplicada a uma classe de problemas 
para obter uma solução eficiente e ótima.
Em outras palavras, o conceito por trás da pro-
gramação dinâmica é quebrar os problemas em 
subproblemas e salvar o resultado para o futuro, 
para que não tenhamos que calcular o mesmo 
problema novamente� A otimização adicional de 
subproblemas que otimiza a solução geral é co-
nhecida como propriedade de subestrutura ótima�
Duas maneiras pelas quais a programação dinâ-
mica pode ser aplicada:
 y Top-Down: Nesse método, o problema é 
decomposto e se o problema já estiver resolvido, 
o valor salvo é retornado, caso contrário, o valor 
da função é memorizado, ou seja, será calculado 
pela primeira vez; para todas as outras vezes, o 
valor armazenado será chamado de volta. A me-
morização é uma ótima maneira para programas 
computacionalmente caros. 
 y Bottom-Up: Essa é uma maneira eficaz de evitar 
a recursão, diminuindo a complexidade de tempo 
que a recursão acumula (ou seja, custo de memória 
15
devido ao recálculo dos mesmos valores)� Aqui, as 
soluções para pequenos problemas são calculadas, 
o que cria a solução para o problema geral�
Deste modo, a programação dinâmica pode ser 
aplicada se você notar que o problema pode ser 
dividido em subproblemas e estes podem ser 
divididos em muitos outros menores, sendo que 
alguns deles se sobrepõem (ou seja, requer o 
cálculo de valores previamente calculados)� O 
objetivo principal é otimizar o código reduzindo a 
repetição de valores armazenando os resultados 
dos subproblemas�
A programação dinâmica é uma estratégia para 
linearizar problemas de programação exponen-
cialmente difíceis, ou seja, a ideia é armazenar 
os resultados dos subproblemas para que não 
tenhamos que recalculá-los posteriormente�
Também podemos resolver o problema da mochila 
com programação dinâmica� Para usar a progra-
mação dinâmica, primeiro criamos uma tabela 
bidimensional com dimensões de 0 a n e 0 a W� 
Em seguida, usamos uma abordagem Bottom-Up 
para calcular a solução ótima� Nessa solução, 
temos um loop aninhado sobre o item número 
n e o limite de peso W� Portanto, seu tempo de 
execução é O(nW)�
16
RECURSÃO E PROGRAMAÇÃO 
DINÂMICA
A recursão é uma maneira de encontrar a solução 
expressando o valor de uma função em termos de 
outros valores dessa função direta ou indiretamente 
– tal função é chamada de função recursiva, logo, 
segue uma abordagem de cima para baixo�
A programação dinâmica nada mais é do que 
recursão com memorização, ou seja, calcular e 
armazenar valores que podem ser acessados 
posteriormente para resolver subproblemas que 
ocorrem novamente, tornando seu código mais 
rápido e reduzindo a complexidade do tempo (os 
ciclos computacionais da CPU são reduzidos)�
Aqui, a ideia básica é economizar tempo pelo uso 
eficiente do espaço, pois a recursão leva tempo, mas 
não espaço, enquanto a programação dinâmica usa 
espaço para armazenar soluções para subproble-
mas para referência futura, economizando tempo�
PROGRAMAÇÃO DINÂMICA E 
SÉRIE DE FIBONACCI
A série de Fibonacci é uma sequência de números 
de tal forma que cada número é a soma dos dois 
anteriores, começando em 0 e 1, definida pela 
fórmula:
F(n)=F(n-1)+F(n-2)
17
Podemos utilizar um método recursivo para calcular 
o Fibonacci,observe na tabela 3 a seguir�
Tabela 3: código Fibonacci recursivo
1 Def ibonacci_recursivo(n):
2 if nlinear e 
merge sort
Exemplo: multiplicação de 
matrizes
Fonte: elaborado pelo autor�
Observe pela tabela 6 que ambos os algoritmos 
possuem suas propriedades bem definidas, ou seja, 
podemos resolver problemas distintos, porém não 
se limitando a eles�
25
BACKTRACKING
Backtracking é um algoritmo geral para resolver 
alguns problemas computacionais, mais nota-
velmente problemas de satisfação de restrições, 
que constrói adicionalmente candidatos para as 
soluções e abandona os retrocessos de um can-
didato assim que determina que ele não pode ser 
concluído para uma solução razoável� O algoritmo 
de backtracking é usado em várias aplicações, 
incluindo o problema das N-rainhas, o problema 
do passeio do cavaleiro, problemas de resolução 
de labirintos e a busca por todos os caminhos de 
Hamilton em um grafo�
Trata-se de uma técnica algorítmica cujo objetivo 
é usar força bruta para encontrar todas as solu-
ções para um problema, o que implica compilar 
gradualmente um conjunto de todas as soluções 
possíveis� Como um problema terá restrições, as 
soluções que não as atenderem serão removidas�
Ele encontra uma solução construindo-a passo a 
passo, aumentando os níveis ao longo do tempo 
através de chamadas recursivas� Uma árvore de 
busca conhecida como árvore de espaço de estados 
é usada para encontrar essas soluções, em que 
cada ramo em uma árvore de espaço de estados 
representa uma variável e cada nível representa 
uma solução�
26
Um algoritmo de backtracking usa o método de 
busca em profundidade, isso quer dizer que quan-
do o algoritmo começa a explorar as soluções, a 
função abundante é aplicada para que o algoritmo 
possa determinar se a solução proposta satisfaz 
as restrições� Se isso acontecer, ele continuará pro-
curando, caso contrário, a ramificação é removida 
e o algoritmo retorna ao nível anterior�
EXEMPLO DE USO DO 
BACKTRACKING
Estamos pegando um exemplo muito simples aqui 
para explicar a teoria por trás de um processo de 
backtracking� Queremos dispor três letras a, b, c 
de tal forma que c não possa ficar ao lado de a.
De acordo com o backtracking, primeiro, cons-
truiremos uma árvore de espaço de estados e 
encontraremos todas as soluções possíveis, em 
seguida, as verificaremos com a restrição fornecida 
e manteremos apenas as soluções que satisfaçam 
a restrição dada�
27
Figura 2: árvore de espaço de estados
a
b
b
c b c a b a
c a c
c
a b
Fonte: elaborado pelo autor.
As possíveis soluções dos problemas seriam: 
(a,b,c), (a,c,b), (b,a,c), (c,b,a)�
No entanto, as soluções válidas para esse problema 
seriam aquelas que satisfizessem a restrição, ou 
seja, se mantêm apenas (a,b,c) e (c,b,a) no conjunto 
final de soluções.
O algoritmo de backtracking é aplicado a alguns 
tipos específicos de problemas. Por exemplo, po-
demos usá-lo para encontrar uma solução viável 
para um problema de decisão, além disso, ele se 
mostra muito eficaz para problemas de otimização.
Em qualquer algoritmo de backtracking, o algoritmo 
busca um caminho para uma solução viável que 
inclua alguns pontos de verificação intermediários. 
Se os checkpoints não levarem a uma solução vi-
28
ável, o problema pode retornar aos checkpoints e 
seguir outro caminho para encontrar uma solução�
Para alguns casos, um algoritmo de backtracking 
é usado para o problema de enumeração a fim de 
encontrar o conjunto de todas as soluções viáveis 
para o problema�
PROBLEMA DAS N-RAINHAS
Um exemplo clássico de backtracking é o problema 
das n-rainhas, proposto pela primeira vez pelo entu-
siasta de xadrez alemão Max Bezzel em 1848� Dado 
um tabuleiro de xadrez de tamanho n, o problema 
é colocar n-rainhas no tabuleiro n vezes, de modo 
que não haja duas rainhas atacando uma à outra�
Para esse problema, precisamos encontrar todos 
os arranjos das posições n das rainhas no tabuleiro, 
mas há uma restrição: nenhuma rainha deve ser 
capaz de atacar outra rainha� O código em Python 
a seguir mostra um exemplo prático�
Tabela 7: código problema n-rainhas
1 N = 5 #dimensao do tabuleiro
2 linha = [False] * N
3 diagAsc = [False] * (2 * N - 1)
4 diagDesc = [False] * (2 * N - 1)
5 numSol = 0
6 solucao = [0] * N
7
29
8 def rainha(col):
9 if colexplorar todas as soluções existentes�
34
Referências Bibliográficas 
& Consultadas
BORIN, V. P. Estrutura de dados. Curitiba: 
Contentus, 2020. [Biblioteca Virtual].
CAMPOS FILHO, F. F. Algoritmos numéricos: 
uma abordagem moderna de cálculo numérico. 
3. ed. Rio de Janeiro: LTC, 2018. [Minha 
Biblioteca].
CORMEN, T. H. Desmistificando algoritmos. 
1. ed. Rio de Janeiro: LTC, 2014. [Minha 
Biblioteca].
DROZDEK, A. Estrutura de dados e 
algoritmos em C++. 4. ed. Cengage Learning, 
2017. [Minha Biblioteca].
GOLDBARG, M. C.; GOLDBARG, E. G., LUNA, 
H. P. L. Otimização combinatória e meta-
heurísticas: Algoritmos e Aplicações. 1. ed. 
Rio de Janeiro: GEN / Elsevier, 2016. [Minha 
Biblioteca].
PINTO, R. A.; PRESTES, L. P.; SERPA, M. S.; 
COUTO, J. M. C.; BIANCO, C. M.; NUNES, P. 
C. M. Estrutura de dados. Porto Alegre: Sagah, 
2019. [Minha Biblioteca].
TOSCANI, L. V., VELOSO, P. A. S. 
Complexidade de algoritmos. 3. ed. Porto 
Alegre: Bookman, 2012. [Minha Biblioteca].
WAZLAWICK, R. S. Introdução a algoritmos 
e programação com Python: uma abordagem 
dirigida por testes; 1. ed. Rio de Janeiro: 
Elsevier, 2017. [Minha Biblioteca].
	_GoBack
	Introdução
	Algoritmos gulosos
	Problema do agrupamento de alunos
	Algoritmo da mochila
	Algoritmos de programação dinâmica
	Recursão e programação dinâmica
	Programação dinâmica e série de Fibonacci
	Algoritmos de divisão e conquista
	Torre de Hanoi
	Divisão e conquista e programação dinâmica
	Backtracking
	Exemplo de uso do backtracking
	Problema das n-rainhas
	Encontrar caminhos Hamiltonianos em um grafo
	Considerações finais
	Referências Bibliográficas & Consultadas