Introdução ao algoritmo de força bruta
"Os dados são o novo petróleo", este é o novo mantra que está governando a economia global. Vivemos no mundo digital e toda empresa gira em torno de dados que se traduzem em lucros e ajudam as indústrias a permanecerem à frente da concorrência. Com a digitalização rápida, um aumento exponencial no modelo de negócios baseado em aplicativos, os crimes cibernéticos são uma ameaça constante. Uma dessas atividades comuns que os hackers realizam é a força bruta.
O Brute Force é uma abordagem de tentativa e erro em que os atacantes usam programas para experimentar várias combinações para invadir qualquer site ou sistema. Eles usam software automatizado para gerar repetidamente as combinações de identificação de usuário e senhas até que, eventualmente, gere a combinação certa.
Pesquisa de força bruta
A pesquisa de força bruta é o algoritmo de pesquisa mais comum, pois não requer nenhum conhecimento de domínio; tudo o que é necessário é uma descrição do estado, operadores legais, o estado inicial e a descrição de um estado de objetivo. Não melhora o desempenho e depende totalmente do poder da computação para experimentar possíveis combinações.
O algoritmo de força bruta pesquisa todas as posições no texto entre 0 e nm, independentemente de a ocorrência do padrão começar lá ou não. Após cada tentativa, ele muda o padrão para a direita exatamente em 1 posição. A complexidade do tempo desse algoritmo é O (m * n). portanto, se estivermos procurando n caracteres em uma sequência de m caracteres, serão necessárias n * m tentativas.
Vamos ver um exemplo clássico de um vendedor ambulante para entender o algoritmo de uma maneira fácil.
Suponha que um vendedor precise viajar 10 cidades diferentes em um país e ele queira determinar as rotas mais curtas possíveis dentre todas as combinações possíveis. Aqui, o algoritmo de força bruta simplesmente calcula a distância entre todas as cidades e seleciona a menor.
Outro exemplo é tentar quebrar a senha de 5 dígitos e a força bruta pode levar até 10 5 tentativas de decifrar o código.
Classificação da força bruta
Na técnica de classificação de força bruta, a lista de dados é varrida várias vezes para encontrar o menor elemento da lista. Após cada iteração na lista, ele substitui o menor elemento no topo da pilha e inicia a próxima iteração a partir dos segundos menores dados da lista.
A declaração acima pode ser escrita em pseudo-código da seguinte maneira.
Aqui, o problema é do tamanho 'n' e a operação básica é 'if', teste onde os itens de dados estão sendo comparados em cada iteração. Não haverá diferença entre o pior e o melhor caso, já que o número de swap é sempre n-1.
Correspondência de cordas de força bruta
Se todos os caracteres no padrão forem exclusivos, a correspondência de sequência de força bruta poderá ser aplicada com a complexidade de Big O (n). onde n é o comprimento da string. Força bruta A correspondência de seqüência de caracteres compara o padrão com a substring de um caractere de texto por caractere até obter um caractere incompatível. Assim que uma incompatibilidade é encontrada, o caractere restante da substring é eliminado e o algoritmo se move para a próxima substring.
Os pseudo-códigos abaixo explicam a lógica de correspondência de cadeias. Aqui, o algoritmo está tentando procurar um padrão de P (0… m-1) no texto T (0… .n-1).
aqui o pior caso seria quando uma mudança para outra substring não for feita até a comparação M Th .
Par mais próximo
Declaração do problema: Descobrir os dois pontos mais próximos em um conjunto de n pontos no plano cartesiano bidimensional. Não há um número de cenários em que esse problema ocorre. Um exemplo da vida real seria um sistema de controle de tráfego aéreo no qual você deve monitorar os aviões que voam próximos um do outro e descobrir a distância mínima mais segura que esses aviões devem manter.
Fonte: Wikipedia
O algoritmo de força bruta calcula a distância entre cada conjunto distinto de pontos e retorna os índices do ponto para o qual a distância é menor.
A força bruta resolve esse problema com a complexidade do tempo de (O (n2)) onde n é o número de pontos.
Abaixo do pseudo-código, utiliza o algoritmo de força bruta para encontrar o ponto mais próximo.
Casco convexo
Declaração do problema : Um casco convexo é o menor polígono que contém todos os pontos. O casco convexo de um conjunto s do ponto é o menor polígono convexo que contém s.
O casco convexo para este conjunto de pontos é o polígono convexo com vértices em P1, P5, P6, P7, P3
Um segmento de linha P1 e Pn de um conjunto de n pontos faz parte do casco convexo se e somente se todos os outros pontos do conjunto estiverem dentro do limite do polígono formado pelo segmento de linha.
Vamos relacionar com o elástico,
Os pontos (x1, y1), (x2, y2) fazem a linha ax + + = c
Quando a = y2-y1, b = x2-x1 ec = x1 * y2 - x2 * y1 e divide o plano por ax + by-c 0
Portanto, precisamos verificar ax + by-c para os outros pontos.
A força bruta resolve esse problema com a complexidade temporal de O (n 3 )
Pesquisa exaustiva
Para problemas discretos nos quais não há solução eficiente conhecida, torna-se necessário testar todas as soluções possíveis de maneira seqüencial.
A pesquisa exaustiva é uma atividade para descobrir de forma sistemática todas as soluções possíveis para um problema.
Vamos tentar resolver o problema do vendedor ambulante (TSP) usando o algoritmo de pesquisa exaustiva Brute.
Declaração do problema: Não há n cidades em que o vendedor precise viajar; ele deseja descobrir o caminho mais curto que cobre todas as cidades.
Estamos considerando o circuito de Hamilton para resolver esse problema. Se existir um circuito, qualquer ponto poderá iniciar os vértices e vértices finais. Depois que os vértices iniciais são selecionados, precisamos apenas da ordem dos vértices restantes, isto é, n-1
Então haveria (n-1)! As combinações possíveis e o custo total para calcular o caminho seriam O (n). portanto, a complexidade total do tempo seria O (n!).
Conclusão
Agora que chegamos ao final deste tutorial, espero que vocês tenham uma boa idéia do que é a Força Bruta. Também vimos os vários algoritmos de força bruta que você pode aplicar em seu aplicativo.
Artigos recomendados
Este foi um guia para o algoritmo de força bruta. Aqui discutimos os conceitos básicos do algoritmo de força bruta. Você também pode consultar nossos outros artigos sugeridos para saber mais -
- O que é um algoritmo?
- Perguntas da entrevista de algoritmo
- Introdução ao algoritmo
- Algoritmo em Programação