Sommario:
Definizione - Cosa significa Backtracking?
Il backtracking è un algoritmo per acquisire alcune o tutte le soluzioni a determinati problemi computazionali, in particolare per problemi di soddisfazione dei vincoli. L'algoritmo può essere utilizzato solo per problemi che possono accettare il concetto di "soluzione candidata parziale" e consente un test rapido per vedere se la soluzione candidata può essere una soluzione completa. Il backtracking è considerato una tecnica importante per risolvere i problemi e i puzzle di soddisfazione dei vincoli. È anche considerata un'ottima tecnica per l'analisi e costituisce anche la base di molti linguaggi di programmazione logica.
Techopedia spiega Backtracking
Il backtracking aiuta a risolvere un problema generale trovando una soluzione al primo sotto-problema e quindi tentando ricorsivamente di risolvere altri sotto-problemi in base alla soluzione del primo problema. Se il problema corrente non può essere risolto, il passaggio viene retrocesso e la successiva possibile soluzione viene applicata ai passaggi precedenti, quindi procede ulteriormente. In effetti, una delle cose chiave nel backtracking è la ricorsione. È anche considerato un metodo di ricerca esaustiva che utilizza divide e conquistare. Un algoritmo di backtracking termina quando non ci sono più soluzioni al primo sotto-problema.
Il backtracking è un algoritmo che può aiutare a realizzare l'implementazione del non determinismo. Richiede una ricerca approfondita di un determinato spazio di emissione. È usato principalmente in linguaggi di programmazione logica come Prolog. Ovunque sia possibile applicare il backtracking, è più veloce della tecnica della forza bruta, poiché elimina un gran numero di candidati con un singolo test.
