Algoritmo di backtracking

Che cos'è l'algoritmo di backtracking?

Il backtracking è un algoritmo che cerca possibili combinazioni per risolvere problemi di calcolo. Costruisce in modo incrementale i candidati e rimuove quelli che non soddisfano i vincoli dati. Questa tecnica è molto utile in situazioni in cui devi scegliere una soluzione fattibile tra più risultati possibili.

Questo algoritmo è considerato migliore e più efficiente dell'approccio Brute Force. A differenza di Bruteforce, che prova tutte le possibili soluzioni, Backtracking si concentra sulla ricerca di una sola soluzione finale in base a dati vincoli. Inoltre, fa risparmiare tempo e memoria annullando l'ultimo passaggio (backtrack) e provando un'altra opzione dopo aver raggiunto un vicolo cieco. Inoltre, si ferma non appena viene trovata una soluzione valida.

Il backtracking è una tecnica ampiamente utilizzata perché può risolvere problemi complessi senza un consumo esauriente di risorse. È particolarmente utile per problemi in cui devono essere soddisfatti numerosi vincoli, come il Sudoku, il problema della regina n e la pianificazione. Navigando in modo intelligente attraverso potenziali soluzioni, il backtracking può trovare una risposta che soddisfi tutte le condizioni. Ciò lo rende inestimabile per attività che richiedono sia precisione che efficienza.

Come funziona l'algoritmo di backtracking?

Gli algoritmi di backtracking sono una tecnica di risoluzione dei problemi che consiste nel trovare soluzioni valide passo dopo passo. Se i vincoli di un passaggio non soddisfano determinate condizioni, l'algoritmo torna al passaggio precedente.

Quindi continua con altre possibili combinazioni che soddisfano i vincoli dati. Poiché esistono numerose possibili combinazioni, seleziona una delle opzioni più soddisfacenti e risolve il problema in sequenza. Questa tecnica algoritmica è utile quando è necessario risolvere una o più possibili opzioni. Il ritiro significa annullare la scelta ogni volta che si verifica una situazione che non produce una soluzione valida.

In generale, l'algoritmo di backtracking per risolvere un problema prevede i seguenti passaggi:

Fase 1) Inizializzazione: Iniziare con una soluzione iniziale vuota/parziale.

Fase 2) Selezione: In base a criteri e vincoli specifici, seleziona un'opzione per estendere la soluzione corrente.

Fase 3) Esplorazione: Risolvere ricorsivamente prendendo in considerazione il candidato scelto e procedendo nel processo di risoluzione del problema.

Fase 4) Controllo dei vincoli: Controlla se la soluzione parziale corrente viola qualche vincolo a ogni passaggio. In caso affermativo, torna indietro al passaggio precedente e prova un candidato diverso.

Fase 5) Risoluzione:Il processo di backtracking si interrompe quando viene trovata una soluzione valida o quando tutte le combinazioni sono state esaurite.

Fase 6) Backtracking: Se l'opzione corrente non risolve il problema dato, torna allo stato precedente. Quindi considera la nuova opzione per risolvere il problema dato.

Passaggio 7) Ripeti: Continuare con questi passaggi finché il problema non sarà risolto o non saranno state esplorate tutte le opzioni.

Natura ricorsiva dell'algoritmo di backtracking

Gli algoritmi di backtracking sono di natura ricorsiva. Ciò significa che l'algoritmo richiama se stesso con parametri diversi finché non trova una soluzione o non ha testato tutte le possibilità:

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

Termini comuni relativi ai problemi di backtracking

Ecco alcuni termini di base relativi alla tecnica del Backtracking:

Vettore della soluzione: Rappresenta le soluzioni come n-tuple, come (X1, X2, …, Xn).
vincoli: Regole che limitano i valori X, impliciti ed espliciti.
Spazio di soluzione: Tutti i valori X validi che soddisfano vincoli espliciti.
Albero dello spazio di stato: Rappresenta lo spazio delle soluzioni come un albero.
Spazio statale: Descrive i percorsi in un albero dello spazio di stato.
Stato del problema: Nodi nell'albero di ricerca che rappresentano soluzioni parziali.
Stati di soluzione: Stati che formano tuple di soluzioni valide in S.
Rispondi Stati: Soddisfare i vincoli impliciti e produrre le soluzioni desiderate.
Nodo promettente: Porta alle soluzioni desiderate e rimane fattibile.
Nodo non promettente: Porta a stati irrealizzabili, non ulteriormente esplorati.
Nodo vivo: Generato con bambini inesplorati.
E-Nodo: Nodo attivo con generazione di figli in corso.
Nodo morto: Nessuna ulteriore espansione di tutti i figli generati.
Generazione di nodi Depth-First: Utilizza l'ultimo nodo attivo come prossimo E-nodo.
Funzione di delimitazione: Massimizza o minimizza B(x1, x2, …, Xa) per l'ottimizzazione.
Alberi statici: Formulazione dell'albero indipendente dall'istanza del problema.
Alberi dinamici: La formulazione dell'albero varia a seconda dell'istanza del problema.

Quando utilizzare un algoritmo di backtracking?

Possiamo scegliere la tecnica del Backtracking per risolvere un problema complesso quando:

Esistono molte scelte: Il backtracking è adatto se esistono molte opzioni a ogni passaggio del processo di risoluzione dei problemi. Queste opzioni possono riguardare la selezione di elementi e mosse.
Nessuna scelta migliore chiara: Quando non si hanno informazioni sufficienti per determinare la scelta migliore tra le opzioni disponibili, è possibile utilizzare un algoritmo di backtracking.
La decisione porta a più scelte: Puoi scegliere il tecnica di backtracking per rivedere sistematicamente le scelte.
Bisogna esplorare tutte le possibili soluzioni: Il backtracking esplora sistematicamente tutte le soluzioni prendendo una serie di decisioni basate le une sulle altre.

Tipi di problemi di backtracking

Ci sono tre tipi di problemi negli algoritmi di backtracking: problemi decisionali, problemi di ottimizzazione e problemi di enumerazione. Impariamo a conoscerli di seguito.

Problema decisionale: In questo tipo di problema, l'obiettivo è determinare se esiste una soluzione fattibile. Controlliamo le risposte "sì" e "no". Ad esempio, il problema delle n-regine. È un problema decisionale che esamina la probabilità di posizionare n regine su una scacchiera n × n senza attaccarsi a vicenda.
Problema di ottimizzazione: Nei problemi di ottimizzazione, l'obiettivo è trovare la migliore soluzione possibile tra molte opzioni. Ciò può comportare la determinazione dei valori massimo e minimo di una certa funzione o variabile. Ad esempio, considera il problema dello zaino, in cui l'obiettivo è massimizzare il valore totale degli oggetti nella borsa rispettando il suo limite di peso.
Problema di enumerazione: Il suo obiettivo è trovare tutte le possibili soluzioni a un dato problema. Elenchiamo ogni opzione valida senza alcuna omissione. Un esempio sarebbe generare tutte le possibili combinazioni di lettere da un dato set di caratteri.

Applicazioni del Backtracking ed esempi

Esistono varie applicazioni del Backtracking. Alcune di esse sono spiegate di seguito con il loro pseudo codice.

Sudoku Solver: Questo problema contiene una sottogriglia 3×3 con numeri duplicati. La tecnica di backtracking mostrerà che la soluzione restituisce false, indicando la necessità di un diverso posizionamento dei numeri.

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

Problema N-Regina:L'approccio del backtracking determina come presentare le regine su una scacchiera N × N in modo che nessuna di esse sia pericolosa per le altre.

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

Problema della somma dei sottoinsiemi: Viene utilizzato per trovare il sottoinsieme di numeri di un dato insieme che sommati danno una determinata somma target.

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

Problema del ciclo hamiltoniano: Il backtracking può essere applicato per trovare un tour chiuso in un grafico che visita ogni vertice esattamente una volta.
Problema del topo nel labirinto:La tecnica del backtracking viene utilizzata per trovare il percorso di un topo dal punto di partenza del labirinto fino all'uscita.

Vantaggi e svantaggi dell'algoritmo di backtracking

Vantaggi dell'algoritmo di backtracking

Le tecniche di backtracking vengono utilizzate per risolvere problemi complessi. Presentano molti vantaggi, come:

La tecnica del backtracking è efficiente per gestire i vincoli.
Questo metodo è utile per risolvere problemi di ottimizzazione.
La tecnica funziona per vari tipi di problemi.
Questa procedura può aiutare a esaminare tutte le possibili soluzioni.
Poiché esegue il backtracking, consente di risparmiare più memoria rispetto alla tecnica Bruteforce.

Svantaggi dell'algoritmo di backtracking

Le tecniche di backtracking hanno anche alcune limitazioni, come la complessità temporale. Questa tecnica ha i seguenti svantaggi:

Non esiste una soluzione garantita.
È più lento a causa delle numerose combinazioni.
Ha un'elevata complessità temporale a causa delle numerose possibilità.
Non è adatto alle limitazioni in tempo reale, poiché trovare la soluzione migliore potrebbe richiedere molto tempo.
L'efficienza dipende dal livello di complessità del problema.

Differenza tra backtracking e ricorsione

Ricorsione	backtracking
Si richiama fino al raggiungimento del caso base.	Utilizza la ricorsione per esaminare tutte le possibilità finché non si trova il miglior risultato fattibile.
Approccio dal basso verso l'alto.	Approccio dall'alto verso il basso.
Nessun valore viene scartato.	Le soluzioni non praticabili vengono rifiutate.

Conclusione

Il backtracking è una strategia algoritmica utile per risolvere problemi complessi esplorando sistematicamente soluzioni fattibili e tornando indietro quando necessario. Possiamo aspettarci che le tecniche di backtracking migliorino con miglioramenti nella potenza di calcolo e nell'efficienza algoritmica. Questi progressi consentiranno loro di affrontare problemi più grandi e complessi in modo efficiente.

Inoltre, i modelli di apprendimento automatico possono guidare le decisioni di backtracking sulla base di modelli appresi in precedenza.

Tutte queste innovazioni tecnologiche rivoluzioneranno gli algoritmi di backtracking, rendendoli uno strumento potente e versatile per affrontare problemi complessi in vari ambiti.