In informatica, molti algoritmi di ricerca sono stati sviluppati da diversi sviluppatori per cercare aspetti distinti (stringhe, numeri, modelli, soluzioni).
La ricerca viene effettuata in vari modi. La ricerca della forza bruta e dell'esaurimento sono due algoritmi di ricerca di stringhe utilizzati dai programmatori. Questi metodi funzionano sul principio della ricerca di ogni soluzione fattibile.
Punti chiave
- Gli attacchi di forza bruta testano sistematicamente ogni possibile combinazione per decifrare password o crittografia.
- Algoritmi di ricerca esaustivi valutano tutte le potenziali soluzioni per trovare quella ottimale.
- Entrambi i metodi possono richiedere molte risorse ma risolvono efficacemente i problemi senza euristiche specifiche.
Forza bruta contro ricerca esaustiva
Forza bruta è una ricerca non uniforme che utilizza una prova ed errore per indovinare le informazioni di accesso, le chiavi di crittografia o trovare una pagina Web nascosta. La ricerca esaustiva è un tipo di ricerca a forza bruta utilizzata per risolvere problemi relativi a permutazione e combinazione. È una ricerca uniforme e richiede meno tempo.
L'algoritmo della forza bruta è una tecnica codificata dagli sviluppatori per recuperare le stringhe, e viene persino utilizzato per risolvere il puzzle delle otto regine (un puzzle per posizionare otto regine su una scacchiera otto per otto).
Tuttavia, è una strategia intuitiva che richiede molti confronti per risolvere il problema.
La ricerca esaustiva è un tipo di ricerca della forza brutale che viene utilizzata per risolvere problemi relativi alla permutazione e alla combinazione.
L'obiettivo principale è cercare per ogni soluzione la soluzione ottima soddisfacendo i vincoli. Possono essere risolti anche altri problemi, come i problemi del venditore ambulante e dello zaino.
Tavola di comparazione
Parametri di confronto | Ricerca della forza bruta | Ricerca esaustiva |
---|---|---|
Tipo di ricerca | Brute Force è una ricerca non uniforme. | Esauriente è una ricerca uniforme perché sappiamo in quale direzione viene eseguito il recupero. |
Ricerche | Brute Force serve per cercare lo schema delle corde. | L'algoritmo di ricerca esaustivo serve per il recupero di permutazioni, combinazioni e sottoinsiemi. |
Procedura | L'algoritmo Brute Force cerca il modello desiderato spostandosi verso destra in un dato testo. | L'algoritmo di ricerca esaustiva esamina ogni nodo fino a raggiungere il nodo finale. |
Ora | La forza bruta è un metodo che richiede tempo. | L'algoritmo di ricerca esaustiva richiede meno tempo in confronto. |
Applicazioni | L'algoritmo di ricerca Brute Force viene utilizzato per posizionare otto regine su tavole otto per otto. | L'algoritmo di ricerca esaustiva viene utilizzato per risolvere il problema del commesso viaggiatore. |
Che cos'è la ricerca a forza bruta?
L'algoritmo Brute Force è una delle tecniche di ricerca in Informatica. Poiché si tratta di un metodo intuitivo, è un approccio molto semplice per risolvere problemi basati esclusivamente su previsioni.
In questo metodo, non viene utilizzata alcuna tecnica complessa per trovare la soluzione.
Il processo consiste nel continuare a scorrere il testo per cercare la stringa. Se una stringa non corrisponde, spostati di un passaggio a destra e ripeti il processo finché non viene trovata la corrispondenza appropriata.
La procedura ora è semplice. Supponiamo di dover cercare la stringa PLANT.
Abbina l'ortografia di ogni parola nel paragrafo con la stringa PLANT. Spostati verso destra se una frase nella riga non corrisponde. Se una stringa corrisponde, la nostra ricerca ha avuto successo. Abbiamo ricevuto i risultati desiderati.
Pertanto, possiamo dire che questo è un metodo di ricerca che richiede molto tempo se la lunghezza del testo è più lunga. Il trucco per calcolare il numero di confronti è la moltiplicazione di N x M dove N è la lunghezza del testo e M è la lunghezza della stringa.
Per esempio,
Testo = 10
String= PIANTA quindi, dimensione della stringa =5
Combinazioni = NXM = 10 x 5= 50
Nella vita pratica, possiamo usare la ricerca della forza bruta. Un esempio è posizionare otto regine su scacchiere 8 × 8. La regola è di disporre le regine in modo tale che nessuna regina blocchi il percorso di un'altra.
Che cos'è la ricerca esaustiva?
La ricerca esaustiva è un sottoinsieme dell'algoritmo di ricerca Brute Force, che serve per la ricerca di combinazioni e permutazioni. Questo algoritmo si concentra sulla ricerca di ogni soluzione al problema dato soddisfacendo tutti i vincoli.
Poiché esaustivo significa faticoso, questo tipo di ricerche sono ricerche cieche, ma uniformi. La strategia mira a massimizzare o minimizzare il problema.
Molti problemi possono essere risolti utilizzando una ricerca esaustiva, come il problema del commesso viaggiatore e il problema dello zaino.
Il problema del commesso viaggiatore è che prima di tornare al luogo di partenza, il venditore deve visitare le N città (una sola volta) utilizzando il percorso più breve.
Dove N è il numero delle città, e i vincoli sotto questo problema sono:
- Seguendo il percorso più breve di città in città.
- Visita tutte le città prima di tornare.
- Visita tutte le città una sola volta.
Per esempio,
Ci sono cinque città: A, B, C, D ed E. La città di partenza viene scelta saggiamente applicando le combinazioni. Quindi, che tutti i vincoli siano soddisfatti.
Mentre scegliamo un percorso appropriato, proveremo diverse combinazioni che saranno estenuanti e dispendiose in termini di tempo. In altre parole, dobbiamo formare un movimento ciclico per raggiungere l'obiettivo.
Principali differenze tra forza bruta e ricerca esaustiva
- L'algoritmo di ricerca Brute Force è il metodo non uniforme. D'altra parte, un algoritmo di ricerca esaustivo è un metodo uniforme.
- L'algoritmo di ricerca Brute Force è un metodo per cercare la stringa nel testo. Al contrario, un algoritmo di ricerca esaustivo cerca la soluzione di permutazioni e combinazioni.
- La tecnica Brute Force funziona abbinando tutte le lettere in una stringa. Tuttavia, una ricerca esaustiva segue la procedura di esame di ogni nodo del diagramma di flusso finché i vincoli non sono soddisfatti.
- Il metodo Brute Force richiede più tempo ed è applicabile quando i dati sono brevi. D'altra parte, un algoritmo esaustivo è applicabile anche in scenari complessi.
- Poiché nella tecnica di ricerca esaustiva viene seguito il metodo Brute Force, è più popolare di una ricerca esaustiva.
- https://ieeexplore.ieee.org/abstract/document/4640789/
- https://link.springer.com/chapter/10.1007/3-540-44411-4_2
Ultimo aggiornamento: 13 luglio 2023
Sandeep Bhandari ha conseguito una laurea in ingegneria informatica presso la Thapar University (2006). Ha 20 anni di esperienza nel campo della tecnologia. Ha un vivo interesse in vari campi tecnici, inclusi i sistemi di database, le reti di computer e la programmazione. Puoi leggere di più su di lui sul suo pagina bio.