Complexidade de Problemas

Prévia do material em texto

Ariel Da Silva Dias
COMPLEXIDADE DE 
PROBLEMAS
Sumário
INTRODUÇÃO ������������������������������������������������� 3
CLASSES DE PROBLEMAS: P E NP ���������������� 8
Algoritmos NP ��������������������������������������������������������������������� 11
Algoritmos NP-Completos ������������������������������������������������� 13
Algoritmos NP-Hard ������������������������������������������������������������ 14
Podemos dizer que P = NP? ����������������������������������������������� 15
FORÇA BRUTA E HEURÍSTICAS �������������������17
Algoritmos de força bruta �������������������������������������������������� 17
Pesquisa heurística ������������������������������������������������������������ 25
Diferença entre Força Bruta e Pesquisa heurística ���������� 29
PROBLEMA DO CAIXEIRO VIAJANTE ��������� 32
CONSIDERAÇÕES FINAIS ����������������������������36
REFERÊNCIAS BIBLIOGRÁFICAS & 
CONSULTADAS ��������������������������������������������38
2
INTRODUÇÃO
A maioria dos algoritmos transforma objetos de 
entrada em objetos de saída� O tempo de execução 
de um algoritmo ou método de estrutura de dados 
geralmente cresce com o tamanho da entrada, 
embora também possa variar para diferentes en-
tradas do mesmo tamanho� Além disso, o tempo 
de execução é afetado por muitos fatores, como o 
ambiente de hardware e o ambiente de software�
Apesar das possíveis variações decorrentes de 
diferentes fatores ambientais, os estudos apre-
sentados aqui se concentram na relação entre o 
tempo de execução de um algoritmo e o tamanho 
de sua entrada� Deste modo, em cada análise, tere-
mos o tempo de execução de um algoritmo como 
uma função , em que n é o tamanho da entrada, 
o que pode ser representado em uma expressão 
polinomial�
Revendo então as principais funções da análise 
de um algoritmo, temos:
 y Função constante f(n)=C: Para qualquer ar-
gumento n, a função constante atribui o valor C� 
Não importa qual seja o tamanho da entrada n, f(n) 
sempre será igual ao valor constante C� A função 
constante mais fundamental é f(n) = 1 , o que 
caracteriza o número de etapas necessárias para 
3
realizar uma operação básica em um computador, 
como adicionar dois números, atribuir um valor a 
alguma variável ou comparar dois números� Deste 
modo, um algoritmo constante não depende do 
tamanho da entrada�
 y Função logarítmica f(n)=log n: trata-se de um 
dos aspectos interessantes e surpreendentes da 
análise de estruturas de dados e algoritmos� A 
forma geral de uma função logarítmica é , para 
alguma constante , onde b é a base do logaritmo� 
A aproximação de base dois surge na análise de 
algoritmos, uma vez que uma operação comum 
em muitos algoritmos é dividir repetidamente uma 
entrada pela metade� Normalmente deixamos de 
lado a escrita do valor da base quando ela é 2, e 
apresentamos apenas log n� A função logarítmica 
fica um pouco mais lenta à medida que n cresce. 
Sempre que n dobra, o tempo de execução aumenta 
em uma constante� O exemplo mais conhecido é 
o algoritmo de busca binária�
 y Função linear f(n)=n: função simples, mas 
importante� Dado um valor de entrada n, a função 
linear f atribui o próprio valor n� Essa função surge 
em uma análise de algoritmo sempre que fazemos 
uma única operação básica para cada um dos n 
elementos� Por exemplo, comparar um número x 
com cada elemento de uma matriz de tamanho n 
exigirá n comparações� A função linear também 
representa o melhor tempo de execução que es-
4
peramos alcançar para qualquer algoritmo que 
processe uma coleção de n entradas�
 y Função N-Log-N f(n)=n log n : essa função 
cresce um pouco mais rápido que a função linear 
e muito mais devagar que a função quadrática� 
Se pudermos melhorar o tempo de execução da 
resolução de algum problema de quadrático para 
N-Log-N, teremos um algoritmo que roda muito mais 
rápido em geral� Isso se transforma em um grande 
problema, pois sempre que n dobra, o tempo de 
execução mais que dobra�
 y Função quadrática f(n)=n²: essa função apa-
rece muito na análise de algoritmos, pois existem 
muitos algoritmos que possuem loops aninhados, 
onde o loop interno realiza um número linear de 
operações e o loop externo é realizado um número 
linear de vezes� Nesses casos, o algoritmo executa 
n * n = n² operações�
 y Função exponencial f(n)=bn: nessa função, b 
é uma constante positiva, chamada de base e o 
argumento n é o expoente� Na análise do algoritmo, 
a base mais comum para a função exponencial é b 
= 2� Por exemplo, se tivermos um loop que começa 
executando uma operação e depois dobra o número 
de operações executadas a cada iteração, então 
o número de operações executadas na enésima 
iteração é 2n� O algoritmo exponencial geralmente 
não é apropriado para uso prático, um exemplo 
são as Torres de Hanói�
5
Em um cenário ideal, gostaríamos que as opera-
ções da estrutura de dados fossem executadas 
em tempos proporcionais à função constante ou 
logarítmica e gostaríamos que nossos algoritmos 
fossem executados em tempo linear ou n-log-n� Al-
goritmos com tempos de execução quadráticos ou 
cúbicos são menos práticos, mas algoritmos com 
tempos de execução exponenciais são inviáveis para 
todas as entradas, exceto as de menor tamanho�
Observe que esse conjunto de algoritmos que 
verificamos até agora podem ser resolvidos em 
tempo polinomial, por esse motivo, são chamados 
de algoritmos polinomiais� Por outro lado, existem 
alguns algoritmos que não podem ser resolvidos ou 
não podem ser verificados em tempo polinomial.
Diz-se que um algoritmo é solucionável em tempo 
polinomial se o número de passos necessários 
para completar o algoritmo para uma dada entra-
da for O(nk) para algum inteiro não negativo k, em 
que n é a complexidade da entrada� Diz-se que 
algoritmos de tempo polinomial são «rápidos»� 
As operações matemáticas mais conhecidas, 
como adição, subtração, multiplicação e divisão, 
bem como calcular raízes quadradas, potências 
e logaritmos, podem ser executadas em tempo 
polinomial� O cálculo dos dígitos das constantes 
matemáticas mais interessantes, incluindo o pi (π) 
pode ser feito em tempo polinomial�
6
Neste e-book, estudaremos as diversas classes 
de problemas em análise de algoritmos, conside-
rando os algoritmos que podem ser solucionados 
em tempo polinomial e aqueles que não podem� 
Também conhecerá dois tipos de algoritmos que 
são muito utilizados em diferentes áreas, mas 
principalmente em inteligência artificial: força bruta 
e busca heurística�
7
CLASSES DE PROBLEMAS: 
P E NP
Considere, por exemplo, que você tenha uma lista 
não ordenada de números e queira escrever um al-
goritmo para encontrar o maior� O algoritmo, então, 
tem que olhar para todos os números da lista: não 
há como contornar isso� Mas se ele simplesmente 
mantiver um registro do maior número visto até 
agora, ele terá que olhar para cada entrada apenas 
uma vez�
O tempo de execução do algoritmo é, portanto, 
diretamente proporcional ao número de elementos 
que ele está manipulando, ou seja, o tempo será 
n� É claro que a maioria dos algoritmos é mais 
complicada e, portanto, menos eficiente do que 
aquela para encontrar o maior número em uma 
lista; mas muitos algoritmos comuns têm tempos 
de execução proporcionais a n2, ou n vezes o loga-
ritmo de n, ou similares�
Uma expressão matemática que envolve n’s e n²s 
e n’s elevados a outras potências é chamado de 
polinômio, ou seja, P é o conjunto de problemas 
cujos tempos de solução são proporcionais aos 
polinômios envolvendo n’s� Todas as principais 
funções de P foram mencionadas na introdução 
deste e-book�
8
Desse modo, um algoritmo cujo tempo de execução 
é proporcional a é mais lento do que um algorit-
mo cujo tempo de execução é proporcional a n� 
Mas tais diferenças se tornam insignificantes em 
comparação a outra distinção, entre expressões 
polinomiais e expressões em que um número é 
elevado à enésima potência, como, digamos, 2n�
Enquanto, por exemplo, um algoritmo cujo tempo 
de execução é proporcional a nleva um segundo 
para realizar uma computação envolvendo 100 
elementos, um algoritmo cujo tempo de execução 
é proporcional a n3 pode levar quase três horas� Já 
um algoritmo cujo tempo de execução é propor-
cional a 2n leva 300 quintilhões de anos – e essa 
discrepância fica muito, muito pior quanto mais 
o N cresce�
Considere, por exemplo, os problemas da vida real 
(do dia a dia). Embora possamos usar uma ampla 
variedade de termos para classificar os problemas, 
na maioria dos casos usamos uma escala Fácil a 
Difícil�
Na ciência da computação teórica, a classificação 
e a complexidade das definições de problemas 
comuns têm dois conjuntos principais: P, que é o 
tempo polinomial que foi apresentado, e NP, que 
é o tempo polinomial não determinístico� Existem 
também conjuntos NP-Difícil e NP-Completo, que 
9
usamos para expressar problemas mais sofisti-
cados. No caso de classificação de fácil a difícil, 
podemos rotulá-los como fácil (P), médio (NP), 
difícil (NP-Completo) e, finalmente, mais difícil 
(NP-Hard). O relacionamento deles é apresentado 
na figura 1.
Figura 1: relacionamento P, NP, NP-Completo e NP-Hard
NP - Hard
NP - Completo
NP
P
Mais difícil
Difícil
Médio
Fácil
Fonte: elaborado pelo autor�
No diagrama da figura 1, assumimos que P e NP 
são o mesmo conjunto, ou, em outras palavras, 
assumimos que P é diferente de NP ou P≠NP� Essa 
é uma afirmação aparentemente verdadeira, mas 
ainda não comprovada� Outro aspecto interessante 
deste diagrama é que existe alguma sobreposição 
entre NP e NP-Difícil� Chamamos NP-Completo 
quando o problema pertence a ambos os conjuntos�
10
Logo, após mapear P, NP, NP-Completo e NP-Difícil 
para “fácil”, “médio”, “difícil” e “muito difícil”, uma 
pergunta pode ser colocada: como é possível 
colocar um determinado algoritmo em cada uma 
destas categorias? Para isso, serão apresentadas 
a seguir algumas formalidades�
ALGORITMOS NP
NP (que significa tempo polinomial não determinís-
tico) é o conjunto de problemas cujas soluções 
podem ser verificadas em tempo polinomial, mas 
não podem ser resolvidos em tempo polinomial� 
Mas, até onde qualquer um pode verificar, muitos 
desses problemas levam um tempo exponencial 
para serem resolvidos� 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�
Espera-se que esses algoritmos tenham uma 
complexidade exponencial, que definiremos como: 
𝑇𝑇 𝑛𝑛 = 𝑂𝑂(𝐶𝐶1	𝑥𝑥	𝑘𝑘𝐶𝐶2𝑥𝑥𝑛𝑛) ,
em que C1 > 0, C2 > 0 e k > 0 e , sendo que C1, C2 
e k são constantes e n é o tamanho da entrada� 
T(n) é uma função do tempo exponencial quando 
pelo menos C1=1 e C2=1� Como resultado, obtemos 
11
O(kn)� Por exemplo, observaremos complexidades 
como O(nn), O(2n), O(20.0000001xn) neste conjunto de 
problemas�
Formalmente, é possível afirmar que esses pro-
blemas NP devem ser problemas de decisão – ter 
uma resposta sim ou não – embora observe que, 
na prática, todos os problemas de função podem 
ser transformados em problemas de decisão� Essa 
distinção nos ajuda a definir o que queremos dizer 
com verificado.
Para falar com precisão, então, um algoritmo é NP 
se não pode ser resolvido em tempo polinomial e 
o conjunto de soluções para qualquer problema de 
decisão pode ser verificado em tempo polinomial 
por uma “Máquina de Turing Determinística”�
Um dos exemplos mais comuns e eficazes é o 
Sudoku� Dada uma grade de Sudoku não resol-
vida (9 x 9, por exemplo), um algoritmo levaria 
um bom tempo para resolvê-lo� No entanto, se a 
grade 9 x 9 aumentar para uma grade de 100 x 
100 ou 10�000 x 10�000, o tempo que levaria para 
resolvê-la aumentaria exponencialmente porque o 
problema em si se torna significativamente mais 
difícil� No entanto, dada uma grade de Sudoku 
resolvida (de 9 x 9), é bastante simples verificar 
se a solução específica está realmente correta, 
mesmo que o tamanho seja dimensionado para 
12
10�000 x 10�000� Seria mais lento, mas o tempo 
para verificar uma solução aumenta a uma taxa 
mais lenta (polinomialmente).
ALGORITMOS NP-COMPLETOS
O próximo conjunto é muito semelhante ao ante-
rior� Dando uma olhada no diagrama, todos eles 
pertencem a NP, mas estão entre os mais difíceis 
do conjunto� O que os torna diferentes de outros 
problemas NP é uma distinção útil chamada com-
pletude� Para qualquer problema NP-Completo, 
existe um algoritmo de tempo polinomial que pode 
transformar o problema em qualquer outro proble-
ma NP-completo� Esse requisito de transformação 
também é chamado de redução�
Formalmente, podemos dizer que se trata de um 
conjunto de problemas a cada um dos quais qual-
quer outro problema NP pode ser reduzido em 
tempo polinomial e cuja solução ainda pode ser 
verificada em tempo polinomial. Isso significa que 
qualquer problema NP pode ser transformado em 
um problema NP-Completo�
Informalmente, eles são os “mais difíceis” dos 
problemas NP� Assim, se qualquer problema NP-
-Completo pode ser resolvido em tempo polinomial, 
então se todo problema NP-Completo pode ser 
resolvido em tempo polinomial, todo problema em 
NP também pode ser resolvido em tempo polinomial 
13
(ou seja, P = NP). O exemplo mais famoso seria o 
problema dos Caixeiros Viajantes�
ALGORITMOS NP-HARD
O último conjunto de problemas contém os pro-
blemas mais difíceis e complexos da ciência da 
computação� Eles não são apenas difíceis de 
resolver, mas também difíceis de verificar� Entre 
os problemas mais difíceis da ciência da compu-
tação estão:
 y Agrupamento K-means: trata-se de um termo 
genérico para uma classe de algoritmos não su-
pervisionados para descobrir grupos de coisas, 
pessoas ou ideias que estão intimamente relacio-
nadas entre si;
 y Problema do Caixeiro Viajante: este é o problema 
de otimização da ciência da computação mais 
conhecido no mundo moderno� Em outras pala-
vras, trata-se de um problema de encontrar a rota 
ótima entre os nós no grafo� A distância total de 
viagem pode ser um dos critérios de otimização� 
Mais adiante foi reservado um tópico para falarmos 
um pouco mais sobre este algoritmo que tem sido 
empregado não somente na computação, mas em 
diversas áreas como controle de rota de entregas 
e rota de automóveis�
Esses algoritmos têm uma propriedade semelhante 
aos de NP-Completo pois todos eles podem ser 
14
reduzidos a qualquer problema em NP� Por causa 
disso, eles estão NP-Hard e são pelo menos tão 
difíceis quanto qualquer outro problema no NP� 
Um problema pode estar tanto em NP quanto em 
NP-Hard, que é outro aspecto de ser NP-Completo�
Essa característica levou a um debate sobre se o 
algoritmo do Caixeiro Viajante é ou não NP-Comple-
to� Como os problemas NP e NP-Completo podem 
ser verificados em tempo polinomial, provar que 
um algoritmo não pode ser verificado em tempo 
polinomial também é suficiente para colocar o 
algoritmo em NP-Hard�
PODEMOS DIZER QUE P = NP?
Uma questão que chama a atenção de muitos 
cientistas da computação é se todos os algoritmos 
NP pertencem ou não a P� Trata-se de um problema 
interessante porque significaria, por exemplo, que 
qualquer problema NP-Completo pode ser resolvido 
em tempo polinomial� Por causa desse problema, 
temos um dos Problemas do Prêmio do Milênio 
para o qual há um prêmio de US$ 1�000�000�
Desse modo, torna-se possível afirmar que P! = NP, 
no entanto, P = NP ainda pode ser possível� Se fosse 
assim, além de problemas NP-Completos serem 
resolvidos em tempo polinomial, certos algoritmos 
NP-Difícil também simplificariam drasticamente. 
Por exemplo, se o verificador deles for NP ou NP-
15
-Completo, segue-se que eles também devem ser 
solucionáveis em tempo polinomial, movendo-os 
também para P = NP = NP - Completo�
Agora que os conceitos foram todos definidos, 
uma pergunta mais importante a ser feita é: “Por 
que tudo isso importa?”� Ter uma solução paraesse problema pode ter consequências profundas 
não apenas no meio acadêmico, mas também em 
situações práticas� Isso inclui:
 y Criptografia: das muitas senhas que mantemos, 
seja do e-mail, do celular ou aquelas que usamos 
no caixa eletrônico, contamos com esses códigos 
para governar nossas vidas cotidianas porque são 
fáceis de verificar, mas difíceis de decifrar;
 y Roteamento de veículos: O transporte e o mo-
vimento da logística seriam otimizados em todo o 
mundo, impactando muitos setores, desde o trans-
porte até o comércio eletrônico e a manufatura;
 y Dobramento de proteínas: Compreender ou 
prever como uma determinada sequência de amino-
ácidos (uma proteína) se dobrará para formar sua 
forma 3D ajudará em muitas áreas, como design 
de medicamentos e talvez até curar câncer�
Observe então que ocorreria uma mudança radical 
na ciência da computação e até mesmo nos cená-
rios do mundo real� Se encontrarmos um algoritmo 
de tempo polinomial, esses algoritmos descritos 
(e outros) se tornam vulneráveis a ataques.
16
FORÇA BRUTA E 
HEURÍSTICAS
A inteligência artificial (IA) é um dos setores em 
maior expansão nos últimos anos, com diversos 
tipos de aplicações, que abrange desde a montagem 
de automóveis em uma linha de fábrica, passando 
pelo reconhecimento biométrico, até chegar em 
descoberta de doenças e suas curas na saúde� 
Trata-se então do estudo da construção de objetos 
que agem objetivamente�
Essas Ias, para realizarem suas ações e alcança-
rem seus objetivos, executam tipos específicos 
de algoritmos� Dois desses algoritmos são força 
bruta e busca heurística�
ALGORITMOS DE FORÇA BRUTA
O algoritmo de força bruta também é conhecido 
como busca cega ou busca uniforme� A força bruta 
pode localizar um estado não objetivo a partir de 
um estado objetivo, além disso, ela normalmente 
não tem controle sobre a busca escolhida� A busca 
cega ou força bruta é uma das principais estratégias 
de busca quando não se tem um caminho direto 
para a busca�
O algoritmo de força bruta é usado quando não 
há outro algoritmo disponível para acelerar o pro-
17
cesso e é preciso verificar cada solução possível 
para poder resolvê-lo� Por exemplo, vamos pegar 
um cenário em que você precisa pesquisar no di-
cionário o significado da palavra “psicossomático” 
usando o algoritmo de força bruta� Você precisa 
percorrer cada palavra para chegar à sua palavra-
-alvo� Considerando um dicionário com n palavras, 
a complexidade de tempo seria igual a O(n), uma 
vez que leva n passos – sendo também o número 
de palavras do dicionário�
Você pode usar o método de busca binária para 
chegar ao seu objetivo rapidamente, ou seja, dividir 
o dicionário em duas listas iguais e obter o ponto 
médio� Se a palavra vier antes do ponto médio, 
você pegará a primeira parte e descartará a outra 
metade� Isso se repetirá até que você descubra 
sua palavra� Nesse caso, a complexidade será O 
(log (n))�
Você pode usar essas técnicas para acelerar o 
desempenho, mas se você tiver um dicionário de 
entrada não ordenado e precisar percorrer cada 
palavra para descobrir sua palavra-alvo, não terá 
o mesmo resultado�
Você pode melhorar os algoritmos de força bruta 
reduzindo os critérios de pesquisa, pois são direta-
mente proporcionais à entrada fornecida. Também 
pode ser melhorado usando diferentes abordagens 
18
heurísticas para cada problema, o que resulta na 
solução ótima de um problema� O algoritmo de 
força bruta baseia-se na abordagem de tentativa 
e erro, que é uma metodologia fundamental na 
resolução de problemas� Nessa metodologia, o 
programa continua fazendo tentativas até obter 
sucesso no problema�
Por exemplo, você tem o desafio de encontrar 
todos os inteiros entre 1 e 100�000�000 que são 
divisíveis por 332� Se você adotar uma abordagem 
simples, o algoritmo de força bruta geraria todos os 
inteiros que estão no intervalo� Você pode reduzir 
os critérios de pesquisa e torná-los mais eficientes 
começando com 332 e somando (adicionando) 
repetidamente o mesmo número até que o número 
exceda o limite determinado� Assim, você pode 
salvar os possíveis ensaios realizando análises 
em alguns casos�
Existem vários tipos de algoritmos de força bru-
ta, dentre eles a busca em largura e a busca em 
profundidade�
Busca em largura e busca em 
profundidade
Problemas de busca são aqueles em que nossa 
tarefa é encontrar o caminho ótimo entre um nó 
inicial e um nó objetivo em um grafo� Existem 
diversas variações para problemas de busca: o 
19
grafo pode ser direcionado ou não direcionado, 
ponderado ou não ponderado, e pode haver mais 
de um nó objetivo�
A busca em largura realiza a busca pela formação 
dos níveis de uma árvore� Ele liga vários tópicos 
visitados, obtendo o objetivo mais superficial do 
usuário que está mais próximo da raiz�
A busca em profundidade: vagueia consecutiva-
mente ao longo do caminho enquanto desce na 
árvore até surgir uma solução para o problema ou 
até chegar em um caminho sem saída, momento o 
qual ele volta atrás em seu caminho e cava outros 
caminhos�
Ambos os algoritmos pesquisam sobrepondo uma 
árvore ao grafo, que chamamos de árvore de busca� 
Busca em profundidade e busca em largura definem 
sua raiz para o nó inicial e aumentam adicionando 
os sucessores das folhas atuais da árvore�
Dessa forma, essas técnicas cobrem todo o grafo 
até encontrarem o nó objetivo ou esgotarem o grafo� 
O que eles diferem é a ordem em que visitam os 
nós, ou seja, adiciona-os à árvore de busca.
A busca em profundidade, por exemplo, em cada 
etapa adiciona à árvore um filho do nó incluído 
mais recentemente com pelo menos um filho não 
incluído� Portanto, adiciona o nó inicial, depois 
20
seu filho, depois seu neto e assim por diante. Por 
esse motivo, essa técnica aumenta ao máximo 
a profundidade da árvore de pesquisa em cada 
etapa, ou seja, se não houver mais filhos de um 
nó para adicionar, ele retrocede para o pai do nó� 
A figura 2 ilustra o caminho feito pela busca em 
profundidade em uma árvore�
Figura 2: árvore de busca em profundidade
1
52
3 4 6 8 9
7
Fonte: Elaborado pelo autor�
Observe que o número 1 representa o primeiro 
nó visitado pelo algoritmo de busca, o número 2 
representa o segundo nó representado pelo algo-
ritmo de busca e assim por diante�
De outra maneira, a busca em largura percorre a 
árvore camada por camada� Primeiro adiciona todos 
os filhos do nó inicial, completando assim o nível 
1. Em seguida, adiciona todos os filhos de todas 
as folhas do primeiro nível um por um� Depois, ele 
21
adiciona todos os filhos dos netos do nó inicial e 
assim por diante�
Portanto, se o fator de ramificação for constante 
em todos os níveis, essa técnica tornará a árvore 
mais ampla a cada etapa� Para fazer isso, a busca 
em largura adiciona à árvore um filho do nó adicio-
nado menos recentemente que possui pelo menos 
um filho não incluído. A figura 3 ilustra o caminho 
feito pela busca em largura em uma árvore�
Figura 3: árvore de busca em largura
1
2
5 6
3
7
4
8 9
Fonte: Elaborado pelo autor�
Ao comparar o caminho percorrido pela figura 2 
e pela figura 3, é possível destacar as principais 
características para cada algoritmo�
Na árvore de busca em largura, todos os números 
de inclusão no nível i são menores do que os nú-
meros no nível i + 1� Esse não é o caso busca em 
profundidade que, se o nó i tiver um número de 
22
inclusão menor que o i + 1, todos os descenden-
tes de i + 1 terão números menores que i e seus 
descendentes�
Assim, a busca em largura aumenta a árvore nível 
por nível, enquanto a busca em profundidade au-
menta subárvore por subárvore�
No pior cenário, a busca em profundidade cria 
uma árvore de pesquisa cuja profundidade é m, 
portanto, sua complexidade de tempo é , em que 
b é o número de nós na árvore e m a profundidade�
Como o BFS (Breadth-First Search – Busca em 
largura) é ótimo, seu resultado de pior caso é 
encontrar o nó objetivo após adicionar b1 nós no 
nível 1, b2 no nível 2 e assimpor diante até o nível 
d, em que adiciona bd nós� No total, a árvore de pior 
caso da busca em largura contém 1 + b1 + b2 + … + 
bd nós, o que significa que o tempo para crescer é 
da ordem de O(bd)�
Onde aplicar a força bruta?
A força bruta pode ser aplicada a uma ampla varie-
dade de problemas, desde problemas de tentativa 
e erro, pesquisa a um número, realização de algum 
tipo de classificação nas listas não classificadas de 
entrada, procura de números inteiros entre alguns 
intervalos em qualquer condição, até descobrir o 
maior número em um intervalo, dentre outras opções 
23
possíveis� Trata-se de uma técnica extremamente 
útil na resolução de problemas de pequeno porte�
Destaca-se também a popularidade dos algoritmos 
de força bruta entre os invasores para roubar in-
formações confidenciais. Quando um invasor usa 
um conjunto de possíveis candidatos para atacar 
algumas informações direcionadas ou dados va-
zados, esse fenômeno é chamado de ataque de 
força bruta� O atacante continua as tentativas até 
que haja algum sucesso� Se o tamanho da entra-
da for maior, mais tempo levará, mas há uma boa 
probabilidade de atingir a meta�
O ataque mais comum é roubar as informações de 
senha dos usuários� No ataque de dicionário, um 
invasor usa um dicionário de senhas que contém 
bilhões de palavras que podem ser usadas como 
senha por usuários normais, a partir disso, o pro-
cesso de ataque executa uma a uma as senhas 
de um dicionário para autenticar as credenciais 
dos usuários e se o usuário definir uma senha 
que esteja neste dicionário, há um risco alto do 
atacante ter sucesso em sua ação�
Na técnica de ordenação de força bruta, a lista 
de dados é verificada várias vezes para localizar 
o menor elemento na lista� Após cada iteração 
sobre a lista, ele substitui o menor elemento no 
24
topo da pilha e inicia a próxima iteração a partir 
do segundo menor dado da lista�
Neste exemplo de ordenação, o problema é de ta-
manho ‘n’, e a operação básica é o teste ‘if’, cujos 
itens de dados estão sendo comparados em cada 
iteração� Não haverá diferença entre o pior e o 
melhor caso, pois o número de troca é sempre n-1�
A principal desvantagem do método de força bruta 
é que, para muitos problemas do mundo real, o 
número de candidatos naturais é proibitivamente 
grande� Por exemplo, se procurarmos os divisores 
de um número como descrito acima, o número de 
candidatos testados será o número n dado�
PESQUISA HEURÍSTICA
Uma heurística no sentido mais comum é um mé-
todo que envolve a adaptação da abordagem de 
um problema com base em soluções anteriores 
para problemas semelhantes� Essas abordagens 
visam ser fáceis e rapidamente aplicáveis a uma 
série de problemas, de modo a encontrar soluções 
aproximadas rapidamente sem usar o tempo e 
os recursos para desenvolver e executar uma 
abordagem precisa� O princípio de uma heurística 
pode ser aplicado a vários problemas em matemá-
tica, ciências e otimização, aplicando heurística 
computacionalmente�
25
A pesquisa heurística também é conhecida como 
pesquisa informada e é orientada a objetivos� O 
objetivo principal da busca heurística é ser rápido 
e fácil, abrangendo uma variedade de problemas, 
pois encontra uma resposta aproximada sem exigir 
ou gastar muito tempo e recursos�
A busca heurística pode não fornecer sempre a 
solução mais precisa ou melhor, mas encontra 
uma solução adequada em um período racional de 
tempo, sendo um método de busca muito útil para 
resolver problemas difíceis� Portanto, é o melhor 
caminho para problemas que levam um tempo 
infinito para serem resolvidos.
A procura de espaços de solução tem sido fun-
damental para o desenvolvimento da inteligência 
artificial para a resolução de problemas. Desde 
então, o uso de algoritmos de busca heurística 
se expandiu consideravelmente para incluir uma 
variedade de aplicações, como planejamento de 
rotas, biologia computacional e robótica�
Existem vários tipos diferentes de algoritmos de 
busca heurística que podem ser utilizados depen-
dendo da tarefa, a saber:
 y Hill Climbing: algoritmo aplicado em IA cujo 
objetivo é o de encontrar a melhor solução dispo-
nível, continuando a gerar soluções até encontrar 
o estado requisitado� A cada passo do processo, 
26
o algoritmo irá gerar soluções (nós) e comparar 
o nó com o objetivo� Se for o estado de meta es-
perado, ele conclui o processo� Se não for, ele irá 
gerar novos nós e repetir até que o estado objetivo 
seja encontrado ou até atingir o máximo local, 
ou o estado em que todas as outras opções são 
piores que o atual� As estratégias do Hill Climbing 
são frequentemente utilizadas para otimizações 
matemáticas, como no problema do caixeiro 
viajante, que tenta encontrar as rotas mais curtas 
possíveis entre as paradas de vendas�
 y Simulated Annealing: trata-se de um algoritmo 
iterativo com uma solução inicial e um problema 
de otimização� O Simulated Annealing usa funções 
heurísticas para comparar os estados vizinhos dos 
dados e decidir entre permanecer no mesmo estado 
ou mudar para um novo� O algoritmo se moverá 
para estados mais próximos da solução ótima até 
atingir um estado que tenha sido observado como 
bom o suficiente para a aplicação ou até que seu 
tempo de execução seja atingido�
 y A*: É um algoritmo de busca que é usado para 
encontrar o caminho mais curto entre um ponto 
inicial e um ponto final. Trata-se de um algoritmo 
útil que é frequentemente usado para percorrer 
um mapa para encontrar o caminho mais curto a 
ser seguido� A* foi inicialmente projetado como 
um problema de travessia de grafos, para ajudar 
27
a construir um robô que possa encontrar seu pró-
prio curso� 
O algoritmo A* ainda continua sendo um algorit-
mo amplamente popular para travessia de grafos 
pois procura por caminhos mais curtos primeiro, 
tornando-o um algoritmo ideal e completo� Outro 
aspecto que torna o A* tão poderoso é o uso de 
grafos ponderados em sua implementação, e isso 
quer dizer que ele usa números para representar o 
custo de tomar cada caminho ou curso de ação, ou 
seja, que os algoritmos podem seguir o caminho 
com o menor custo e encontrar a melhor rota em 
termos de distância e tempo�
Um algoritmo heurístico sacrifica a otimização – 
precisão e exatidão – por velocidade para resolver 
problemas com mais rapidez e eficiência.
Todos os grafos possuem diferentes nós ou pon-
tos que o algoritmo deve tomar para chegar ao 
nó final. Todos os caminhos entre esses nós têm 
um valor numérico, que é considerado como o 
peso do caminho� O total de todos os caminhos 
transversais lhe dá o custo dessa rota�
Inicialmente, o algoritmo calcula o custo para todos 
os nós vizinhos imediatos (n) e escolhe aquele de 
menor custo, e esse processo se repete até que 
nenhum novo nó possa ser escolhido e todos os 
28
caminhos tenham sido percorridos� Então, você 
deve considerar o melhor caminho entre eles� 
DIFERENÇA ENTRE FORÇA BRUTA 
E PESQUISA HEURÍSTICA
A principal diferença entre Força Bruta e Busca 
Heurística é que a força bruta é uma forma de 
busca desinformada, ou seja, pesquisa sem as 
informações adequadas, além de não ter conhe-
cimento sobre o problema�
A busca desinformada (ou Pesquisa Cega), como 
o nome sugere, está pesquisando sem “informa-
ções” sobre o nó objetivo� Por exemplo, em busca 
em largura os nós no mesmo nível são percorri-
dos primeiro e então ele se move para o próximo 
nível e não para até encontrar o nó com valores 
que estava procurando, logo, não há necessidade 
de informações para selecionar os nós a serem 
percorridos� Você também pode pensar em uma 
estratégia de pesquisa desinformada como uma 
estratégia de pesquisa de força bruta�
Por outro lado, a busca heurística é uma busca in-
formada, em outras palavras, pesquisa com dados 
e informações adequados para obter resultados 
possíveis, isso quer dizer que gera um caminho em 
torno da solução e, uma vez que é principalmente 
orientada a objetivos, não leva muito tempo para 
29
executar tarefas– ao contrário da força bruta, que 
é relativamente demorada�
A busca Informada está pesquisando com “in-
formações” sobre o nó objetivo� Por exemplo, 
no algoritmo de busca A*, primeiro, coletamos 
informações sobre o nó objetivo, como sua locali-
zação na forma de coordenadas cartesianas e, em 
seguida, escrevemos uma função que pode guiar 
nossa travessia do nó, por exemplo, encontrando 
sua distância euclidiana� Essa função é chamada 
de função heurística� 
A função heurística guiará nossa travessia de nós 
informando a distância que resta de cada nó até o 
nó objetivo� Você também pode pensar na Estraté-
gia de Pesquisa Informada como uma Estratégia 
de Pesquisa Guiada�
As estratégias de pesquisa informada e desin-
formada são o coração e a alma da Inteligência 
Artificial. Na vida real, as buscas informadas e 
desinformadas podem ter essa aparência: a busca 
desinformada ocorre quando você está olhando 
de um site para outro ou folheando os livros da 
revista sem realmente precisar encontrar a infor-
mação, enquanto a busca informada é de natureza 
oposta, por exemplo, você está no trabalho ou está 
estudando alguma coisa e chega um termo que 
você não entende naquele momento, então você 
30
não navegará na internet por alguma informação 
aleatória, mas especificamente para encontrar o 
termo específico.
Resumidamente, a força bruta é considerada 
uma forma cega de busca, pois não inclui técnica 
heurística e, por definição, trata-se de uma técnica 
geralmente muito ineficiente. A pesquisa heurística 
por sua vez é baseada em problemas, logo, está 
técnica geralmente encontra uma solução aproxi-
mada para um problema�
31
PROBLEMA DO CAIXEIRO 
VIAJANTE
O Problema do Caixeiro Viajante é o desafio de 
encontrar a rota mais curta e mais eficiente para 
uma pessoa tomar, dada uma lista de destinos 
específicos. Trata-se de um problema algorítmico 
bem conhecido nas áreas de ciência da computa-
ção e pesquisa operacional�
Obviamente, há muitas rotas diferentes para esco-
lher, mas encontrar a melhor – aquela que exigirá a 
menor distância ou custo – é o que matemáticos 
e cientistas da computação passaram décadas 
tentando resolver�
O problema do caixeiro viajante atraiu tanta aten-
ção porque é muito fácil de descrever, mas muito 
difícil de resolver, o que faz com que o problema 
do caixeiro viajante pertença à classe de proble-
mas de otimização combinatória NP-completos� 
Isso significa que o problema do caixeiro viajante 
é classificado como NP-difícil porque não possui 
solução “rápida” e a complexidade de calcular a 
melhor rota aumentará quando você adicionar 
mais destinos ao problema�
O problema pode ser resolvido analisando cada 
rota de ida e volta para determinar a mais curta� 
No entanto, à medida que o número de destinos 
32
aumenta, o número correspondente de viagens de 
ida e volta supera as capacidades até mesmo dos 
computadores mais rápidos� Com 10 destinos, pode 
haver mais de 300�000 permutações e combinações 
de ida e volta� Com 15 destinos, o número de rotas 
possíveis pode ultrapassar 87 bilhões�
Dentre as soluções mais populares, destacam-se:
 y Abordagem força bruta: que calcula e com-
para todas as permutações possíveis de rotas ou 
caminhos para determinar a solução única mais 
curta� Para resolver o PCV (Problema do Caixeiro 
Viajante) usando a abordagem força bruta, você 
deve calcular o número total de rotas e, em seguida, 
desenhar e listar todas as rotas possíveis� Calcule 
a distância de cada rota e, em seguida, escolha a 
mais curta – esta é a solução ideal;
 y Método Branch and Bound: esse método 
divide um problema a ser resolvido em vários 
subproblemas� É um sistema para resolver uma 
série de subproblemas, cada um dos quais pode 
ter várias soluções possíveis e a solução selecio-
nada para um problema pode afetar as possíveis 
soluções de subproblemas subsequentes� Para 
resolver o problema do caixeiro viajante usando 
o método Branch and Bound, você deve escolher 
um nó inicial e, em seguida, definir o limite para um 
valor muito grande (digamos, infinito). Selecione o 
arco mais barato entre o nó não visitado e o atual 
33
e, em seguida, adicione à distância atual. Repita 
o processo enquanto a distância atual for menor 
que o limite� Se a distância atual for menor que o 
limite, você terminou� Agora você pode somar a 
distância para que o limite seja igual à distância 
atual� Repita esse processo até que todos os arcos 
tenham sido cobertos�
 y Método do vizinho mais próximo: essa é talvez 
a heurística do problema do caixeiro viajante mais 
simples� A chave para esse método é sempre visi-
tar o destino mais próximo e depois voltar para a 
primeira cidade quando todas as outras cidades 
forem visitadas� Para resolver o problema dessa 
maneira, escolha uma cidade aleatória e então 
procure a cidade não visitada mais próxima e vá 
até lá� Depois de visitar todas as cidades, você 
deve retornar à primeira cidade.
 y Inserção mais distante: ao contrário das outras 
inserções, a Inserção Mais Distante começa com 
uma cidade e a conecta com a cidade mais distan-
te dela� Em seguida, ele encontra repetidamente 
a cidade que ainda não está no passeio que está 
mais distante de qualquer cidade no passeio e a 
coloca entre as duas cidades que fariam com que 
o passeio resultante fosse o mais curto possível�
 y Algoritmo Christofides: o Algoritmo de Chris-
tofides é uma heurística com garantia de aproxi-
mação de � Na pior das hipóteses, o passeio não 
é maior que da duração do passeio ideal� Devido 
34
à sua velocidade e garantia de aproximação de , o 
Algoritmo Christofides é frequentemente usado para 
construir um limite superior, como um tour inicial 
que será otimizado usando heurísticas de melhoria 
de tour, ou como um limite superior para ajudar 
a limitar o espaço de busca para ramificações e 
técnicas de corte utilizadas na busca da rota ideal�
Apesar da complexidade de resolver o Problema 
do Caixeiro Viajante, ele ainda encontra aplicações 
em diversas áreas. Por exemplo, soluções eficien-
tes encontradas por meio desse problema estão 
sendo usadas em rotas de entregas de mercadoria 
de um centro de transporte, como um depósito ou 
armazém, até a escolha de entrega do cliente final.
35
CONSIDERAÇÕES FINAIS
Nesse e-book você pôde compreender a teoria 
da complexidade, que realiza a classificação de 
problemas com base em quão difíceis eles são 
de resolver�
Você pôde compreender também que um proble-
ma é atribuído à classe P (tempo polinomial) se 
o número de etapas necessárias para resolvê-lo 
for limitado por alguma potência do tamanho do 
problema�
Por outro lado, um problema é atribuído à classe 
NP (tempo polinomial não determinístico) se ele 
permitir uma solução não determinística e o nú-
mero de etapas para verificar a solução é limitado 
por alguma potência do tamanho do problema� A 
classe de problemas P é um subconjunto da classe 
de problemas NP, mas também existem problemas 
que não são NP�
Durante a leitura, você observou que se uma solução 
é conhecida para um problema NP, ela pode ser 
reduzida a uma única verificação em tempo polino-
mial e que um problema é NP-completo se for NP 
e um algoritmo, para resolvê-lo, pode ser traduzido 
em um para resolver qualquer outro problema NP� 
Como exemplos de problemas NP-completos ve-
rificamos o problema do caixeiro viajante.
36
Além disso, pôde compreender que um problema 
é dito NP-hard se um algoritmo, para resolvê-lo, 
pode ser traduzido de maneira que consiga resolver 
qualquer outro problema NP� Observe então que é 
muito mais fácil mostrar que um problema é NP do 
que mostrar que é NP-hard� Um problema que é NP 
e NP-hard é chamado de problema NP-completo�
Você também conheceu duas técnicas de de-
senvolvimento de algoritmos, a heurística (busca 
informada) e a força bruta (busca não informada), 
também conhecida como busca cega ou busca 
uniforme, que é um procedimento mais demorado, 
entretanto, cabe ressaltar que a estratégia de busca 
informadaé mais eficiente do que a estratégia de 
busca não informada quando temos informações 
sobre o nó objetivo, caso essa informação não 
esteja presente, a estratégia de busca não infor-
mada deve ser aplicada�
37
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]�
	Introdução
	Classes de Problemas: P e NP
	Algoritmos NP
	Algoritmos NP-Completos
	Algoritmos NP-Hard
	Podemos dizer que P = NP?
	Força bruta e heurísticas
	Algoritmos de força bruta
	Pesquisa heurística
	Diferença entre Força Bruta e Pesquisa heurística
	Problema do caixeiro viajante
	Considerações finais
	Referências Bibliográficas & Consultadas