Introduzione all'algoritmo della forza bruta
"I dati sono il nuovo petrolio", questo è il nuovo mantra che governa l'economia globale. Viviamo nel mondo digitale e ogni azienda ruota attorno ai dati che si traducono in profitti e aiutano le industrie a stare al passo con la concorrenza. Con la rapida digitalizzazione, un aumento esponenziale del modello di business basato su app, i crimini informatici rappresentano una minaccia costante. Una di queste attività comuni che gli hacker svolgono è la forza bruta.
Brute Force è un approccio di prova ed errore in cui gli aggressori utilizzano programmi per provare varie combinazioni per entrare in qualsiasi sito Web o sistema. Usano software automatizzato per generare ripetutamente le combinazioni ID utente e password fino a quando non genera la combinazione giusta.
Ricerca della forza bruta
La ricerca della forza bruta è l'algoritmo di ricerca più comune in quanto non richiede alcuna conoscenza del dominio, tutto ciò che serve è una descrizione dello stato, operatori legali, lo stato iniziale e la descrizione di uno stato obiettivo. Non migliora le prestazioni e si affida completamente alla potenza di calcolo per provare possibili combinazioni.
L'algoritmo della forza bruta cerca tutte le posizioni nel testo tra 0 e nm, indipendentemente dal fatto che il verificarsi del modello abbia inizio lì o meno. Dopo ogni tentativo, sposta il motivo a destra esattamente di 1 posizione. La complessità temporale di questo algoritmo è O (m * n). quindi se stiamo cercando n caratteri in una stringa di m caratteri, ci vorranno n * m tentativi.
Vediamo un classico esempio di venditore ambulante per capire l'algoritmo in modo semplice.
Supponiamo che un venditore debba viaggiare in 10 diverse città in un paese e che voglia determinare i percorsi più brevi possibili tra tutte le combinazioni possibili. Qui l'algoritmo della forza bruta calcola semplicemente la distanza tra tutte le città e seleziona la più breve.
Un altro esempio è tentare di violare la password di 5 cifre, quindi la forza bruta può richiedere fino a 10 5 tentativi di decifrare il codice.
Brute Force Sort
Nella tecnica di ordinamento della forza bruta, l'elenco dei dati viene scansionato più volte per trovare l'elemento più piccolo nell'elenco. Dopo ogni iterazione sull'elenco, sostituisce l'elemento più piccolo nella parte superiore dello stack e avvia l'iterazione successiva dai secondi dati più piccoli nell'elenco.
L'istruzione sopra può essere scritta in pseudo-codice come segue.
Qui il problema è di dimensione 'n' e l'operazione di base è il test 'if' in cui gli elementi di dati vengono confrontati in ogni iterazione. Non ci sarà alcuna differenza tra il caso peggiore e il migliore poiché il no di swap è sempre n-1.
Brute Force Matching String
Se tutti i caratteri nel motivo sono unici, è possibile applicare la corrispondenza della stringa della forza bruta con la complessità di Big O (n). dove n è la lunghezza della stringa. Forza bruta La corrispondenza delle stringhe confronta il modello con la sottostringa di un carattere di testo per carattere fino a quando non ottiene un carattere non corrispondente. Non appena viene rilevata una mancata corrispondenza, il carattere rimanente della sottostringa viene eliminato e l'algoritmo passa alla sottostringa successiva.
Gli pseudo codici seguenti spiegano la logica di corrispondenza della stringa. Qui l'algoritmo sta cercando di cercare un modello di P (0… m-1) nel testo T (0… .n-1).
qui il caso peggiore sarebbe quando non si passa a un'altra sottostringa fino al confronto M Th .
Coppia più vicina
Dichiarazione del problema: per scoprire i due punti più vicini in una serie di n punti nel piano cartesiano bidimensionale. Esiste un numero n di scenari in cui si presenta questo problema. Un esempio di vita reale potrebbe essere rappresentato da un sistema di controllo del traffico aereo in cui è necessario monitorare gli aerei che volano l'uno vicino all'altro e si deve scoprire la distanza minima più sicura che questi aerei dovrebbero mantenere.
Fonte: Wikipedia
L'algoritmo della forza bruta calcola la distanza tra ogni set distinto di punti e restituisce gli indici del punto per cui la distanza è la più piccola.
La forza bruta risolve questo problema con la complessità temporale di (O (n2)) dove n è il numero di punti.
Sotto lo pseudo-codice utilizza l'algoritmo della forza bruta per trovare il punto più vicino.
Scafo convesso
Dichiarazione del problema : uno scafo convesso è il poligono più piccolo che contiene tutti i punti. Lo scafo convesso di una serie s del punto è il poligono convesso più piccolo contenente s.
Lo scafo convesso per questa serie di punti è il poligono convesso con vertici in P1, P5, P6, P7, P3
Un segmento di linea P1 e Pn di un insieme di n punti è una parte dello scafo convesso se e solo se tutti gli altri punti dell'insieme si trovano all'interno del confine poligonale formato dal segmento di linea.
Mettiamolo in relazione con l'elastico,
Il punto (x1, y1), (x2, y2) rende l'asse della linea + di = c
Quando a = y2-y1, b = x2-x1 e c = x1 * y2 - x2 * y1 e divide il piano per ax + by-c 0
Quindi dobbiamo controllare ax + by-c per gli altri punti.
La forza bruta risolve questo problema con la complessità temporale di O (n 3 )
Ricerca esaustiva
Per problemi discreti in cui non esiste una soluzione efficiente nota, diventa una necessità testare ogni possibile soluzione in modo sequenziale.
La ricerca esaustiva è un'attività per scoprire tutte le possibili soluzioni a un problema in modo sistematico.
Proviamo a risolvere il Problema del commesso viaggiatore (TSP) usando l'algoritmo di ricerca esauriente Brute.
Dichiarazione del problema: ci sono n città in cui il venditore deve viaggiare, vuole scoprire il percorso più breve che copre tutte le città.
Stiamo prendendo in considerazione Hamilton Circuit per risolvere questo problema. Se esiste un circuito, qualsiasi punto può iniziare vertici e terminare vertici. Una volta selezionati i vertici di partenza, abbiamo solo bisogno dell'ordine dei vertici rimanenti, ovvero n-1
Quindi ci sarebbe (n-1)! Le possibili combinazioni e il costo totale per il calcolo del percorso sarebbero O (n). quindi la complessità temporale totale sarebbe O (n!).
Conclusione
Ora che abbiamo raggiunto la fine di questo tutorial, spero che voi ragazzi abbiate una buona idea di cosa sia Brute Force. Abbiamo anche visto i vari algoritmi di forza bruta che puoi applicare nella tua applicazione.
Articoli consigliati
Questa è stata una guida per l'algoritmo della forza bruta. Qui abbiamo discusso i concetti di base dell'algoritmo della forza bruta. Puoi anche consultare i nostri altri articoli suggeriti per saperne di più -
- Che cos'è un algoritmo?
- Algorithm Interview Questions
- Introduzione all'algoritmo
- Algoritmo in programmazione