Introducción al algoritmo de fuerza bruta
"Los datos son el nuevo petróleo", este es el nuevo mantra que rige la economía mundial. Estamos viviendo en el mundo digital y cada negocio gira en torno a los datos que se traducen en ganancias y ayudan a las industrias a mantenerse por delante de su competencia. Con la rápida digitalización, un aumento exponencial en el modelo de negocio basado en aplicaciones, los ciberdelitos son una amenaza constante. Una de esas actividades comunes que realizan los piratas informáticos es la fuerza bruta.
Brute Force es un enfoque de prueba y error en el que los atacantes usan programas para probar varias combinaciones para entrar en cualquier sitio web o sistema. Utilizan software automatizado para generar repetitivamente las combinaciones de identificación de usuario y contraseñas hasta que finalmente genere la combinación correcta.
Búsqueda de fuerza bruta
La búsqueda de fuerza bruta es el algoritmo de búsqueda más común, ya que no requiere ningún conocimiento de dominio, todo lo que se requiere es una descripción de estado, operadores legales, el estado inicial y la descripción de un estado objetivo. No mejora el rendimiento y depende completamente de la potencia informática para probar posibles combinaciones.
El algoritmo de fuerza bruta busca todas las posiciones en el texto entre 0 y nm, ya sea que la aparición del patrón comience allí o no. Después de cada intento, desplaza el patrón a la derecha exactamente 1 posición. La complejidad temporal de este algoritmo es O (m * n). así que si estamos buscando n caracteres en una cadena de m caracteres, se necesitarán n * m intentos.
Veamos un ejemplo clásico de un vendedor ambulante para comprender el algoritmo de una manera fácil.
Supongamos que un vendedor necesita viajar 10 ciudades diferentes en un país y quiere determinar las rutas más cortas posibles de todas las combinaciones posibles. Aquí el algoritmo de fuerza bruta simplemente calcula la distancia entre todas las ciudades y selecciona la más corta.
Otro ejemplo es intentar romper la contraseña de 5 dígitos, luego la fuerza bruta puede demorar hasta 10 5 intentos de descifrar el código.
Tipo de fuerza bruta
En la técnica de clasificación de fuerza bruta, la lista de datos se escanea varias veces para encontrar el elemento más pequeño de la lista. Después de cada iteración sobre la lista, reemplaza el elemento más pequeño en la parte superior de la pila e inicia la siguiente iteración a partir de los segundos datos más pequeños de la lista.
La declaración anterior se puede escribir en pseudocódigo de la siguiente manera.
Aquí el problema es de tamaño 'n' y la operación básica es 'si' prueba dónde se comparan los elementos de datos en cada iteración. No habrá diferencia entre el peor y el mejor caso, ya que el no de intercambio siempre es n-1.
Cadena de fuerza bruta
Si todos los caracteres en el patrón son únicos, entonces la coincidencia de cadenas de fuerza bruta se puede aplicar con la complejidad de Big O (n). donde n es la longitud de la cadena. La coincidencia de cadenas de fuerza bruta compara el patrón con la subcadena de un texto carácter por carácter hasta que obtiene un carácter no coincidente. Tan pronto como se encuentra una falta de coincidencia, el carácter restante de la subcadena se descarta y el algoritmo se mueve a la siguiente subcadena.
Los siguientes pseudocódigos explican la lógica de coincidencia de cadenas. Aquí el algoritmo está intentando buscar un patrón de P (0 … m-1) en el texto T (0 … .n-1).
aquí el peor de los casos sería cuando no se realiza un cambio a otra subcadena hasta la comparación de M Th .
Par más cercano
Planteamiento del problema: Para encontrar los dos puntos más cercanos en un conjunto de n puntos en el plano cartesiano bidimensional. Hay un número n de escenarios donde surge este problema. Un ejemplo de la vida real sería en un sistema de control de tráfico aéreo en el que debe monitorear los aviones que vuelan cerca uno del otro y debe encontrar la distancia mínima más segura que estos aviones deben mantener.
Fuente: Wikipedia
El algoritmo de fuerza bruta calcula la distancia entre cada conjunto distinto de puntos y devuelve los índices del punto para el que la distancia es la más pequeña.
La fuerza bruta resuelve este problema con la complejidad temporal de (O (n2)) donde n es el número de puntos.
Debajo del pseudocódigo se utiliza el algoritmo de fuerza bruta para encontrar el punto más cercano.
Casco convexo
Declaración del problema : un casco convexo es el polígono más pequeño que contiene todos los puntos. El casco convexo de un conjunto s del punto es el polígono convexo más pequeño que contiene s.
El casco convexo para este conjunto de puntos es el polígono convexo con vértices en P1, P5, P6, P7, P3
Un segmento de línea P1 y Pn de un conjunto de n puntos es parte del casco convexo si y solo si todos los demás puntos del conjunto se encuentran dentro del límite del polígono formado por el segmento de línea.
Vamos a relacionarlo con la banda de goma,
El punto (x1, y1), (x2, y2) hace que la línea ax + by = c
Cuando a = y2-y1, b = x2-x1 yc = x1 * y2 - x2 * y1 y divide el plano por ax + by-c 0
Entonces necesitamos verificar ax + by-c para los otros puntos.
La fuerza bruta resuelve este problema con la complejidad temporal de O (n 3 )
Búsqueda exhaustiva
Para problemas discretos en los que no se conoce una solución eficiente, se hace necesario probar todas y cada una de las soluciones posibles de manera secuencial.
La búsqueda exhaustiva es una actividad para encontrar todas las posibles soluciones a un problema de manera sistemática.
Intentemos resolver el problema del vendedor ambulante (TSP) utilizando el algoritmo de búsqueda exhaustiva Brute.
Declaración del problema: Hay n ciudades que el vendedor necesita viajar, quiere encontrar la ruta más corta que cubra todas las ciudades.
Estamos considerando Hamilton Circuit para resolver este problema. Si existe un circuito, cualquier punto puede comenzar vértices y terminar vértices. Una vez que se seleccionan los vértices iniciales, solo necesitamos el orden para los vértices restantes, es decir, n-1
¡Entonces habría (n-1)! Las posibles combinaciones y el costo total para calcular la ruta serían O (n). así, la complejidad del tiempo total sería O (n!).
Conclusión
Ahora que hemos llegado al final de este tutorial, espero que tengan una idea justa de lo que es Brute Force. También hemos visto varios algoritmos de fuerza bruta que puede aplicar en su aplicación.
Artículos recomendados
Esta ha sido una guía para el algoritmo de fuerza bruta. Aquí discutimos los conceptos básicos del algoritmo de fuerza bruta. También puede consultar nuestros otros artículos sugeridos para obtener más información:
- ¿Qué es un algoritmo?
- Preguntas de entrevista de algoritmo
- Introducción al algoritmo
- Algoritmo en Programación