Ricerca backtracking
La ricerca con backtracking è una tipologia di ricerca in profondità che consente una minore complessità spaziale, ossia una minore quantità di memoria fisica per funzionare. In una ricerca in profondità normale l'algoritmo deve mantenere in memoria tutti i percorsi e le diramazioni di un ramo dal nodo di origine ai nodi figli. Ad esempio un albero di ricerca con 3 generazioni di nodi (d=3) e cinque ramificazioni massime per nodo (b=5) necessita di uno spazio in memoria pari a 15 ( b x d ). Nella ricerca in profondità tradizionale l'algoritmo carica in memoria tutte le sotto-ramificazioni prima di analizzare ogni singolo cammino del ramo.
Nella ricerca con backtracking, invece, l'algoritmo si limita ad espandere soltanto un percorso alla volta, all'interno dello stesso ramo, senza aprire anche tutti gli altri nodi successori, e a registrare in una variabile l'informazione sul nodo successore da analizzare in seguito. In questo modo la ricerca con backtracking necessita di una quantità di memoria pari al numero delle generazioni del ramo (d=3) e dell'informazione aggiuntiva necessaria per conoscere la successiva ramificazione da analizzare (nodo successore). In altri termini, l'algoritmo di ricerca con backtracking torna sui suoi passi ( backtracking = tornare indietro ) liberando la memoria utilizzata ogni volta che termina di analizzare un ramo prima di passare al successivo.
Facciamo un esempio pratico di ricerca con backtracking. Al primo ciclo di esecuzione l'algoritmo con backtracking espande il ramo fino al nodo 3 e registra il nodo successore 4 in una variabile di comodo. Procede poi con l'analizzare il cammino dal nodo 1 al nodo 3. Al termine del ciclo di elaborazione del ramo 1-2-3, legge il ramo successore (4) dalla variabile di comodo, libera la memoria utilizzata per registrare la ramificazione 1-2-3 e la riutilizza per registrare la nuova ramificazione 1-2-4 ancora da analizzare. E così via fino all'ultimo ramo in profondità del nodo di origine. In conclusione, grazie alla tecnica della memoria temporanea l'algoritmo di ricerca con backtracking necessita di una memoria di O(d), ben inferiore alla quantità di memoria O(bd) di un algoritmo in profondità tradizionale, riducendo notevolmente la complessità spaziale dell'algoritmo di ricerca.
