TÉCNICAS DE PROJETOS DE ALGORITMO
MÉTODO:
Força Bruta
Alunos:
Tiago Maciel
Gabryel Alves
Vinicius Mendes
Arthur Fellype
O que é força bruta e o seu objetivo?
A técnica de força bruta ou busca exaustiva consiste em tentar todas as
possibilidades para solucionar um problema, fazendo uma travessia completa ou
parcial do espaço de busca da solução.
Por exemplo, quebradores de senhas, problemas de ordenação e de busca, etc.
É uma técnica poderosa e direta para problemas complexos, porém não eficiente.
Vantagens:
Ampla aplicabilidade;
Fácil implementação;
Desvantagens:
Raramente fornece algoritmos eficientes;
Não são tão flexíveis como outros algoritmos.
Como funciona?
Primeiro passo é gerar todas as soluções possíveis para o problema.
Segundo passo é avaliar todas as soluções para o problema.
Terceiro passo é escolher a solução com o melhor custo.
No quebrador de senha, por exemplo, geramos todas as senhas possíveis dentro
dos requisitos estabelecidos e em seguida usamos aquela que é a verdadeira senha
do usuário.
Backtracking e Branch e Bound são exemplos de técnicas de força bruta e seguem
os passos acima.
Exemplo 1
Imagine que você tem um pequeno cadeado com uma combinação 4 números, cada um deles
indo de 0 a 9. Você esquece sua combinação, mas você não quer comprar outro cadeado.
Como você não consegue se lembrar de nenhum dos números, precisa usar um método de
força bruta para abrir a fechadura.
Exemplo 2
Caixeiro viajante
O TSP envolve um vendedor que precisa visitar um conjunto de cidades, passando
por cada uma delas exatamente uma vez, e retornar à cidade de origem, de forma a
minimizar a distância ou o custo total percorrido. O objetivo principal é encontrar o
caminho de menor custo que passe por todas as cidades e retorne ao ponto de
partida.
Tipo de problema: Problema de otimização (minimização de custo ou distância).
Categoria de complexidade: NP-difícil.
Caixeiro Viajante
[1, 2, 3, 4, 5, 1]
Custo: 22
2
2 4
1 3 [1, 2, 3, 5, 4, 1]
3
6 7 Custo: 15
3
3
[1, 2, 5, 3, 4, 1]
4 5 Custo: ?
3
[1, 4, 2, 3, 5, 1]
Custo: 19
Ciclo Hamiltoniano
Ciclo Hamiltoniano
É um ciclo em um grafo que visita
cada vértice exatamente uma vez,
sem se preocupar com a
minimização de distância ou
custo. A única exigência é que o
ciclo passe por todos os vértices do
grafo uma vez e retorne ao vértice
inicial. É um grafo não ponderado
(Só se preocupa com
conectividade).
Estratégias
Backtracking
É uma técnica de busca que explora de maneira ordenada e
inteligente todas as possíveis soluções de um problema. Caso uma
possível solução possa ser descartada no meio do caminho então
o algoritmo retrocede (backtrack) e tenta outra solução.
Branch and Bound
Sendo também uma técnica de busca em cima de todas as soluções
possíveis, o método de branch and bound ( B&B) utiliza de
enumeração inteligente nas possíveis soluções para examinar frações
dessas soluções ( branch ) e calcula limites (bounds) para examiná-la,
caso o limite não seja agradável à melhor solução então ela é podada
e outro ramo (branch) começa a ser analisado.
Exemplo Real
Complexidade de tempo: O(n²)
MÉTODO: Força Bruta
REFERÊNCIAS BIBLIOGRÁFICAS:
ALGORITMO BRANCH-AND-BOUND ( OU ENUMERAÇÃO IMPLÍCITA ).SÃO PAULO: USP,
2011.DISPONÍVEL EM : HTTPS://SITES.ICMC.USP.BR/MARI/SEGUNDO2011/AULA0711.PDF
CARVALHO, MARCO ANTÔNIO. BACKTRACKING. DISPONÍVEL EM :
HTTP://WWW3.DECOM.UFOP.BR/TOFFOLO/SITE_MEDIA/UPLOADS/2011- 1/BCC402/SLIDES/10._BACKTRACKING.PDF
HTTPS://WWW.FREECODECAMP.ORG/PORTUGUESE/NEWS/ALGORITMOS-DE-FORCA-BRUTA-EXPLICADOS/
HTTPS://WWW.FREECODECAMP.ORG/PORTUGUESE/NEWS/ALGORITMOS-DE-
FHTTPS://EDIRLEI.COM/AULAS/PAA_2017_1/PAA_AULA_02_FORCA_BRUTA_2017.PDFORCA-BRUTA-EXPLICADOS/
ALGORITMOS - TEORIA E PRÁTICA, THOMAS CORMEN.
