PROJETO E ANÁLISE DE

ALGORITMOS
Ariel Da Silva Dias
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<Int> = 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]) <
maximaDistanciaCarroPodePercorrer)
31 }
32
33 private fun destinoNaoEncontrado() = posicaoParada
<= numeroParadas
34

7
35 }

Fonte: elaborado pelo autor.

Observe na tabela 1 as linhas 11 e 14. Note que

temos dois loops aninhados, logo a complexidade
é O(n2). Entretanto, acaba por se tornar O(n) porque
não estamos iterando e computando sobre todos
os subarrays repetidamente.

À medida que iteramos sobre o array no loop aninhado,

uma vez que o interrompemos, continuamos o
loop externo a partir daí, portanto, ambos os loops
juntos cobrem todo o array linearmente em uma
única iteração, portanto, O(n).

PROBLEMA DO AGRUPAMENTO DE
ALUNOS
Declaração do problema: Você tem um grande
salão cheio de crianças de várias idades e vários
professores dispostos a lecionarem para diferen-
tes turmas.
y Você deve agrupar essas crianças/alunos em
um grupo em que a diferença de idade entre dois
alunos quaisquer seja de no máximo 1.
y Você também tem um número limitado de
professores e, portanto, deve estar formando o
número mínimo de grupos possível.

8
y Você, então, atribuirá um professor a um grupo
para ensinar.

Rapidamente podemos propor uma solução sim-

ples de se imaginar:
y Você cria um grupo de todas as combinações
possíveis de alunos.
y Itera sobre cada grupo e verifica se a diferença
entre a idade máxima e mínima é 1, caso contrário,
descartamos esse grupo.
y Essa abordagem levará 2n operações e, portanto,
nosso algoritmo é muito lento O(2n).

Porém, como percebemos, podemos dividir o pro-

blema em problemas menores com a abordagem
gananciosa. Vamos analisar uma possível solução
neste novo algoritmo:
y Ordene as idades do menor para o maior na
matriz O(nLogn).
y Itere sobre a matriz e, para cada elemento,
adicione a ela para construir seu intervalo.
y Em seguida, itere os próximos elementos e
verifique quais números se 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 n <= 1:
3 return n
4 else:
5 return(fibonacci_recursivo(n-1) +
fibonacci_recursivo(n-2))

Fonte: elaborado pelo autor.

Observe que no código da tabela 3, o programa

chamará a si mesmo, repetidas vezes, para calcu-
lar outros valores. O cálculo da complexidade de
tempo da abordagem baseada em recursão é O(2N).

Vamos ilustrar as instruções executadas quando

deseja-se, por exemplo, calcular ou seja, o quarto
elemento da sequência de Fibonacci:
F(4) = F(3) + F(2) = ((F(2) + F(1)) + F(2) = ((F(1) +
F(0)) + F(1)) ) + (F(1) + F(0))
Observe que, por esse método, valores como F(2)
são calculados duas vezes e as chamadas para F(1)
e F(0) são feitas várias vezes. Imagine o número
de repetições se você tiver que calcular F(100),
levaria um tempo imenso! Por isso, é um método
inviável para sequências muito grandes.

18
Agora observe o código da tabela 4, no qual não
se usa recursão. Aqui, foi criada uma lista vazia
de comprimento (n+1) e definimos o caso base
de F(0) e F(1) nas posições de índice 0 e 1. Essa
lista é criada para armazenar os valores calculados
correspondentes usando um loop for para valores
de índice 2 até n.

Tabela 4: código Fibonacci programação dinâmica

1 def fib(n):
2 if n<=1:
3 return n
4 lista_ = [0]*(n+1)
5 lista_[0] = 0
6 lista_[1] = 1
7 for i in range(2, n+1):
8 lista_[i] = lista_[i-1] + lista[i-2]
9 return lista_[n]

Fonte: elaborado pelo autor.

Diferentemente do método recursivo, a complexi-

dade de tempo desse código é linear e leva muito
menos tempo para calcular a solução, pois o loop
é executado de 2 a n, ou seja, é executado em O
(n). Portanto, essa abordagem é a maneira mais
eficiente de escrever um programa.

19
ALGORITMOS DE DIVISÃO
E CONQUISTA
Muitos algoritmos úteis são recursivos em estrutura,
ou seja, para resolver um determinado problema,
eles chamam a si mesmos recursivamente uma ou
mais vezes para lidar com subproblemas intima-
mente relacionados. Esses algoritmos geralmente
seguem um algoritmo de divisão e conquista. O
algoritmo de divisão e conquista envolve três eta-
pas em cada nível de recursão:
y Dividir: trata-se do primeiro passo da estratégia
de dividir e conquistar. Como sugerido pelo nome,
nesta etapa dividimos o problema em subproble-
mas menores até que o problema seja pequeno
o suficiente para ser resolvido. Nessa etapa, os
subproblemas tornam-se menores, mas ainda
representam parte do problema real, e, nesse
momento, usamos a recursão para implementar
o algoritmo de divisão e conquista. Um algoritmo
recursivo chama a si mesmo com valores de entra-
da menores ou mais simples – chamamos isso de
caso recursivo –, assim, quando implementamos a
etapa de divisão, determinamos o caso recursivo
que dividirá o problema em subproblemas menores.
y Conquistar: A seguir temos o passo “conquistar”,
em que resolvemos diretamente os subproblemas.
Até agora, já dividimos a entrada nas menores

20
partes possíveis e agora vamos resolvê-las reali-
zando operações básicas. Implementamos a etapa
de conquista com recursão especificando o caso
base recursivo. Uma vez que os subproblemas se
tornam pequenos o suficiente para que não seja
mais recursiva, dizemos que a recursão finalizou
e que chegamos ao caso base. Quando chegamos
ao caso base, resolvemos o subproblema.
y Combine: Por fim, chegamos ao último passo
da estratégia de dividir e conquistar – combinar.
Nessa etapa, combinamos a solução dos subpro-
blemas para resolver todo o problema e a saída
retornada da resolução do caso base será a en-
trada de subproblemas maiores. Então, depois de
chegarmos ao caso base, começaremos a resolver
subproblemas maiores com a entrada retornada
de subproblemas menores. A partir disso, mescla-
mos a saída da etapa de conquista para resolver
subproblemas maiores. Vamos propagar de baixo
para cima até resolvermos todo o problema original.

A complexidade de tempo para o algoritmo de

divisão e conquista é calculada usando o teorema
mestre:
T(n) = aT(n / b) + f(n)
Em que n é o tamanho da entrada, a é o número de
subproblemas na recursão e n/b é o tamanho de
cada subproblema em que todos os subproblemas
são assumidos como tendo o mesmo tamanho.

21
Podemos dizer que f(n) é o trabalho realizado fora
da chamada recursiva.

A abordagem de dividir e conquistar é amplamente

usada para resolver muitas declarações de proble-
mas como merge sort, quick sort, encontrar o par
de pontos mais próximo, entre outros. A seguir é
apresentado um problema clássico da computação
e o qual todo programador deve aprender.

TORRE DE HANOI
Figura 1: Torre de Hanoi com três peças.

A B C

Fonte: elaborado pelo autor.

Observe a figura 1. A partir disso, imagine que

você recebe N blocos em ordem decrescente de
tamanho na Torre A e deseja mover todos esses
blocos para a Torre C com a ajuda da Torre B.
Lembre-se de que você pode mover apenas um
bloco de cada vez e bloco nunca pode estar em
cima de um bloco menor.

22
Suponha que peguemos alguns blocos, N = 3, o
processo de mover os blocos da Torre A para a
Torre C seria o seguinte:
y Primeiro, mova o menor bloco para a Torre C.
Esta etapa mostra a divisão do problema dividindo
o número de blocos de N = 3 a N = 2. Portanto, agora
podemos assumir que nosso subproblema está
movendo dois blocos da Torre A para a Torre C;
y Em seguida, mova o bloco do meio para a Torre
B. Semelhante ao passo anterior, dividimos ainda
mais o subproblema de N = 2 para N = 1 no ponto
de origem;
y Nessa etapa, começamos a resolver os subpro-
blemas substituindo o menor bloco pelo bloco do
meio na Torre B;
y Em seguida, mova o bloco maior para a Torre
C da Torre A e mova o bloco menor para esvaziar
a Torre A da Torre B;
y Por fim, combinamos a solução e obtemos o
resultado final movendo o bloco do meio sobre o
bloco maior da Torre B para a Torre C e movendo
o bloco menor da Torre A para a Torre C.

O código da tabela 5 apresenta um exemplo em

Python.

Tabela 5: código Torre de Hanoi

1 def torreHannoi (N, origem, destino, auxiliar):
2 if N == 1 :

23
3 print(“Mova o disco 1 da origem”,origem,”ao
destino”,destino)
4 Return
5 torreHannoi(N-1, origem, aux, destino)
6 print(“Mova o disco”,N,”da origem”,origem,”para o
destino”,destino)
7 torreHannoi(N-1, aux, destino, origem)
8
9 N=3
10 torreHannoi(N,’A’,’B’,’C’)

Fonte: elaborado pelo autor.

Observe no código da tabela 5 que temos a de-

claração da função na linha 1 e, internamente,
nas linhas 5 e 7 – chamadas recursivas para essa
função. Na linha 2 temos a condição de parada
da recursividade, que é quando tiver apenas um
bloco. Observe que a variável N declarada na linha
10 é o número de blocos e os valores A, B e C são
as três hastes.

DIVISÃO E CONQUISTA E
PROGRAMAÇÃO DINÂMICA
O algoritmo de divisão e conquista tem muitos be-
nefícios que o tornam um algoritmo de resolução
de problemas muito útil, afinal, ajuda a resolver
problemas difíceis em 3 etapas simples usando o
algoritmo top-down recursivamente.

24
Por sua vez, a programação dinâmica trata-se
de uma técnica algorítmica que está intimamente
relacionada à abordagem de dividir e conquistar,
no entanto, enquanto a abordagem de dividir e
conquistar é essencialmente recursiva e, por-
tanto, apenas de cima para baixo (top-down), a
programação dinâmica funciona de baixo para
cima (bottom-up).

A tabela 6 a seguir possui um comparativo entre

os algoritmos de divisão e conquista e a progra-
mação dinâmica.

Tabela 6: comparativo entre divisão e conquista e progra-

mação dinâmica
Divisão e conquista Programação dinâmica
Inclui três passos Inclui quatro passos
Essencialmente recursivo Não é recursivo
Ele funciona recursivamente Os subproblemas são interde-
em subproblemas e, portanto, pendentes por natureza
consome mais tempo
Exemplo: pesquisa linear e Exemplo: multiplicação de
merge sort 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 c
b

b c a c a b

c b c a b a

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 col < N:
10 for lin in range(N):
11 if linha[lin] or diagAsc[lin+col] or
diagDesc[lin-col+N-1]:
12 Continue
13 solucao[col] = lin
14 linha[lin] = diagAsc[lin+col] = diagDesc[lin-
-col+N-1] = True
15 rainha(col+1)
16 linha[lin] = diagAsc[lin+col] = diagDesc[lin-
-col+N-1] = False
17 else:
18 print solução
19 global numSol
20 numSol = numSol + 1
21
22 rainha(0)
23 print “Num.Solucoes= “, numSol

Fonte: elaborado pelo autor.

No código apresentado na tabela 7, começamos

declarando o valor de N, ou seja, da dimensão do
tabuleiro. Em seguida, utilizamos uma estrutura
de repetição em uma função para posicionar as
rainhas de acordo com as limitações propostas
no problema.

Se tomarmos 5 por 5 como exemplo de um tabulei-

ro de xadrez, a resolução do problema resulta em
10 soluções, o que nos leva a usar o algoritmo de

30
backtracking para recuperar todas essas soluções
conforme ilustra a figura 3.

Figura 3: iterações do problema das n-rainhas

x x x x
x x x x
x x x x
x x x x
x x x x

x x x x
x x x x
x x x x
x x x x
x x x x

x x
x x
x x
x x
x x

Fonte: elaborado pelo autor.

A figura 3 representa as 10 iterações geradas du-

rante a execução do código, em que o tabuleiro
tem a dimensão 5 por 5 e a letra X representa uma
rainha. Para esse problema as soluções encontra-
das são válidas, mas ainda assim, um algoritmo
de retrocesso para o problema das n-rainhas apre-
senta uma complexidade de tempo igual a O(2n) ,
considerando aqui um valor de n muito grande (e
não apenas 5, como foi colocado no código).

31
ENCONTRAR CAMINHOS
HAMILTONIANOS EM UM GRAFO
Um caminho hamiltoniano é um caminho de grafo
que conecta dois vértices do grafo que visitam cada
vértice exatamente uma vez. Se existir um cami-
nho hamiltoniano com extremidades adjacentes,
o ciclo do grafo resultante é um ciclo hamiltoniano
ou somente hamiltoniano.

Um caminho hamiltoniano pode existir tanto em

um grafo direcionado quanto em um grafo não
direcionado. Neste escopo, caminho é uma sequên-
cia de arestas e vértices em que todos os vértices
são distintos, além disso, a sequência de arestas
em um caminho pode ser finita ou infinita. Desse
modo, se um caminho cobre todos os vértices de
um determinado grafo sem repetir nenhum vértice,
então trata-se de um caminho hamiltoniano.

32
CONSIDERAÇÕES FINAIS
Nesse e-book você pôde compreender que existem
técnicas específicas para resolver os problemas
computacionais. Nós iniciamos o seu estudo co-
nhecendo os algoritmos gulosos, que são aqueles
que escolhem a melhor solução local e se movem
em direção ao objetivo final, esperando que essa
estratégia se aproxime da solução ótima global.

Em seguida você estudou sobre a programação

dinâmica, que é uma técnica em programação de
computadores que ajuda a resolver eficientemente
uma classe de problemas que possuem subproblemas
sobrepostos. Isso quer dizer que se algum proble-
ma puder ser dividido em subproblemas, que por
sua vez são divididos em subproblemas menores,
e há sobreposição entre esses subproblemas, as
soluções deles poderão ser salvas para referência
futura.

Outra técnica que foi apresentada é a divisão e

conquista, que, para resolver um determinado
problema, tem como intuito chamar uma ou mais
funções, que chamam a si mesmas recursivamente
uma ou mais vezes, para lidar com subproblemas
intimamente relacionados.

Por fim você compreendeu o que é o backtracking

e como ocorre a implementação de algoritmos

33
nessa técnica. Trata-se de uma técnica que con-
tinua sendo vital para resolver vários tipos de
problemas, mesmo que a complexidade de tempo
desse algoritmo possa ser alta, pois pode precisar
explorar 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].