|
|
La tecnica di “Backtrack” è una tecnica utilizata per la progettazione di algoritmi che si basa sul concetto di costruzione ed eventuale distruzione di parte della soluzione ovvero “prova a fare qualcosa, se non funziona disfala e prova a farne un’ altra”. Un algoritmo può essere classificato di backtrack quando in esso sono previsti sia strumenti per la costruzione della soluzione che per distruzione di parte di essa. Gli algoritmi di visita di un albero, previsita, postvisita ed invisita sono esempi di algoritmi di backtrack nei quali l’elaborazione su un nodo può dipendere dal risultato della visita dei suoi sottoalberi. Anche DFS su grafi è un esempio di backtrack. Nel seguito vedremo l’applicazione della tecnica di backtrack alla soluzione del problema di String Matching. Data una sequenza T di n caratteri, detta testo, il problema dello String Matching consiste nel trovare almeno una occorrenza di una sequenza P di m caratteri, detta pattern, dentro T. Chiaramente deve valere che m < n. Per esempio, dato un certo pattern P di m=8 elementi e una certa sequenza T con n=23 elementi, come indicati di seguito, è facile vedere che c’è un’ occorrenza del pattern P a partire dalla posizione k=14 del testo T.
Lo stesso problema può essere formulato diversamente. Per risolvere il problema si deve cercare se esiste un indice k con 1 <= k <= n - m + 1, (infatti se fosse k=23-8+1=16 ci starebbe ancora un pattern di lunghezza n=8) tale che il j-esimo carattere di P sia uguale al (k+j-1)-esimo carattere di T con j = 1,…,m. Un primo algoritmo intuitivo, che chiameremo ricerca bruta, è quello che cerca di riconoscere il pattern partendo dalla prima posizione e scandendo le successive m posizioni. Si confronta quindi il primo carattere di P con il primo di T, il secondo di P col secondo di T e cosi via. Se il pattern non è interamente riconosciuto, si ripete il procedimento a partire però dalla seconda posizione di T, confrontando sta volta il primo carattere di P col secondo di T ecc…Se anche stavolta il pattern non è riconosciuto si prova a partire dalla terza posizione di T, poi dalla quarta e cosi via. Per esempio supponendo di essere a settimo tentativo, ci ritroveremmo in una situazione di questo tipo:
essendo che il quarto elemento di P è diverso dal decimo elemento di T (ovvero il quarto a partire dalla posizione 7) allora si passera a confrontare P con T a partire dall’ ottavo elemento k=8 e cosi via…. Realizzando le stringhe P e T con due vettori di caratteri, si può realizzare la funzione in linguaggio C, che realizza questo algoritmo.
Vengono utilizzato tre indici: k per avanzare nel testo, j per scandire P, e i per scandire T. La complessità nel caso pessimo di questo algoritmo si ha quando k assume n – m + 1 valori. Quindi per ogni valore di k, i e j ne assumono al più m. L’ algoritmo avrà quindi complessità O(n m). Questo tipo di backtrack non è il più furbo. Esiste un modo più furbo che ci permette di progettare un’ algoritmo di complessità O(n +m), l’ algoritmo di Knuth Morris Pratt.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.