backtracking
In informatica e in ricerca operativa, metodo di ricerca esaustiva delle soluzioni di un problema di natura combinatoria. Consiste nel partire da soluzioni parziali che si estendono o si restringono, ritornando sui propri passi, in base all’esito, positivo o negativo, del confronto tra la soluzione parziale e i vincoli posti dal problema alla natura delle soluzioni.
Un esempio di b. può essere fornito dall’attraversamento di un labirinto (fig. A): partendo da 1, una persona che voglia trovare tutte le uscite con una ricerca sistematica, si troverà in 2 di fronte a una scelta; supponendo che adotti la regola di scegliere a ogni incrocio la prima diramazione possibile a cominciare da destra in verso antiorario, senza mai percorrere nello stesso verso una diramazione già percorsa, allora, arrivata in 2, si muoverà verso 3 e di lì in 4, da dove tornerà sui suoi passi fino a 3, per passare quindi a 5; il resto del percorso si ricava procedendo secondo la stessa regola; dall’esempio si può osservare come, quando si è trovata una soluzione totale, o quando si arriva a una soluzione parziale non estendibile (vicolo cieco), si torna sui propri passi fino alla prima soluzione parziale che non era stata rigettata e che può essere estesa fino a una soluzione totale. Nella fig. B è riportato, in forma più astratta ma ancora abbastanza intuitiva, l’albero di ricerca delle soluzioni del problema del labirinto: l’albero rappresenta i punti di entrata, i punti di uscita e i punti di decisione relativi al labirinto proposto e tutte le loro connessioni dirette; la ricerca degli attraversamenti del labirinto con il metodo del b. equivale a una visita in profondità dell’albero (linea tratteggiata).