Algoritmi di backtracking sono come strategie di risoluzione dei problemi che aiutano a esplorare diverse opzioni per trovare la soluzione migliore. Funzionano provando percorsi diversi e se uno non funziona, tornano sui propri passi e ne provano un altro finché non trovano quello giusto. È come risolvere un puzzle provando pezzi diversi finché non si incastrano perfettamente.

Fare marcia indietro

Tabella dei contenuti

• Cos'è l'algoritmo di backtracking?
• Come funziona un algoritmo di backtracking?
• Esempio di algoritmo di backtracking
• Quando utilizzare un algoritmo di backtracking?
• Applicazioni dell'algoritmo di backtracking
• Nozioni di base sull'algoritmo di backtracking
• Problemi standard sull'algoritmo di backtracking
• Problemi facili sull'algoritmo di backtracking
• Problemi medi sull'algoritmo di backtracking
• Problemi difficili sull'algoritmo di backtracking

Cos'è l'algoritmo di backtracking?

Fare marcia indietro è una tecnica algoritmica di risoluzione dei problemi che prevede la ricerca di una soluzione in modo incrementale provando diverse opzioni E annullare loro se portano a a senza uscita .

Viene comunemente utilizzato in situazioni in cui è necessario esplorare molteplici possibilità per risolvere un problema, come cercare un percorso in un labirinto o risolvere enigmi come Sudoku . Quando viene raggiunto un vicolo cieco, l’algoritmo torna al punto decisionale precedente ed esplora un percorso diverso finché non viene trovata una soluzione o tutte le possibilità sono state esaurite.

Come funziona un algoritmo di backtracking?

UN algoritmo di backtracking funziona esplorando ricorsivamente tutte le possibili soluzioni a un problema. Inizia scegliendo una soluzione iniziale, quindi esplora tutte le possibili estensioni di quella soluzione. Se un'estensione porta a una soluzione, l'algoritmo restituisce quella soluzione. Se un'estensione non porta ad una soluzione, l'algoritmo torna alla soluzione precedente e tenta un'estensione diversa.

Quello che segue è uno schema generale di come funziona un algoritmo di backtracking:

1. Scegli una soluzione iniziale.
2. Esplora tutte le possibili estensioni della soluzione attuale.
3. Se un'estensione porta a una soluzione, restituisci quella soluzione.
4. Se un'estensione non porta a una soluzione, tornare alla soluzione precedente e provare un'estensione diversa.
5. Ripetere i passaggi 2-4 finché non sono state esplorate tutte le possibili soluzioni.

Esempio di algoritmo di backtracking

Esempio: Trovare il percorso più breve attraverso un labirinto

Ingresso: Un labirinto rappresentato come una matrice 2D, dove 0 rappresenta uno spazio aperto e 1 rappresenta un muro.

Algoritmo:

1. Inizia dal punto di partenza.
2. Per ciascuna delle quattro direzioni possibili (su, giù, sinistra, destra), prova a muoverti in quella direzione.
3. Se il movimento in quella direzione porta al punto finale, ritorna sul percorso intrapreso.
4. Se il movimento in quella direzione non porta al punto finale, torna alla posizione precedente e prova una direzione diversa.
5. Ripeti i passaggi 2-4 finché non viene raggiunto il punto finale o finché non vengono esplorati tutti i percorsi possibili.

Quando utilizzare un algoritmo di backtracking?

Gli algoritmi di backtracking sono utilizzati al meglio per risolvere problemi che hanno le seguenti caratteristiche:

• Esistono molteplici soluzioni possibili al problema.
• Il problema può essere suddiviso in sottoproblemi più piccoli.
• I sottoproblemi possono essere risolti indipendentemente.

Applicazioni dell'algoritmo di backtracking

Gli algoritmi di backtracking vengono utilizzati in un'ampia varietà di applicazioni, tra cui:

• Risolvere enigmi (ad es. Sudoku, cruciverba)
• Trovare il percorso più breve attraverso un labirinto
• Problemi di pianificazione
• Problemi di allocazione delle risorse
• Problemi di ottimizzazione della rete

Nozioni di base sull'algoritmo di backtracking:

• Differenza tra la tecnica Backtracking e Branch-N-Bound
• Qual è la differenza tra Backtracking e Ricorsione?

Problemi standard sull'algoritmo di backtracking:

• Il problema del tour del Cavaliere
• Ratto in un labirinto
• N problema della regina | Indietro-3
• Problema della somma dei sottoinsiemi
• m Problema di colorazione
• Ciclo hamiltoniano
• Sudoku | Indietro-7
• Puzzle magnetico
• Rimuovi le parentesi non valide
• Un approccio backtracking per generare codici Gray a n bit
• Scrivi un programma per stampare tutte le permutazioni di una determinata stringa

Problemi facili sull'algoritmo di backtracking:

• Tornare indietro per trovare tutti i sottoinsiemi
• Controlla se una determinata stringa è una stringa di somma
• Conta tutti i percorsi possibili tra due vertici
• Trova tutti i sottoinsiemi distinti di un dato insieme
• Trova se esiste un percorso di lunghezza superiore a k da una sorgente
• Stampa tutti i percorsi da una determinata origine a una destinazione
• Stampa tutte le possibili stringhe che possono essere create inserendo spazi

Problemi medi sull'algoritmo di backtracking:

• Tiro alla fune
• Problema delle 8 regine
• Somma combinatoria
• Algoritmo di Warnsdorff per il problema del tour di Knight
• Trova i percorsi dalla cella d'angolo alla cella centrale nel labirinto
• Trova il numero massimo possibile eseguendo al massimo K scambi
• Ratto in un labirinto con più passaggi o salti consentiti
• N Regina nello spazio O(n).

Problemi difficili sull'algoritmo di backtracking:

• Insieme di potere in ordine lessicografico
• Problema di interruzione di parole utilizzando il Backtracking
• Partizione di un insieme in K sottoinsiemi di uguale somma
• Percorso più lungo possibile in una matrice con ostacoli
• Trova il percorso sicuro più breve in un percorso con mine antiuomo
• Stampa tutte le partizioni palindromiche di una stringa
• Stampa di tutte le soluzioni in N-Queen Problem
• Stampa tutte le sottosequenze comuni più lunghe in ordine lessicografico

Link veloci :

• Impara la struttura dei dati e gli algoritmi | Tutorial DSA
• Le 20 migliori domande per l'intervista sull'algoritmo di backtracking
• “Video” sul Backtracking