Backtracking

Il backtracking è una tecnica di programmazione algoritmica che si basa su:

• costruire una sequqnza aggiungendo un elemento alla volta
• controllare che l’elemento può essere aggiunto (e quindi che la sequenza sia valida)
  • se si raggiunge la soluzione l’algoritmo termina
  • se no, si cambia input
    • se ancora non si raggiunge la soluzione dopo averle provate tutte: fallimento

Backtracking si basa sul bruteforcing: provarle tutte.

Famiglie

Le famiglie del bruteforce:

• enumerazione
  • trovare TUTTE le soluzioni possibili
  • esempio: elencare tutte le permutazioni di un insieme
  • soluzione: algoritmi di enumerazione
• ricerca
  • trovare UNA soluzione ammissibile in uno spazio delle soluzioni molto grande
  • esempio: trovare una sequenza di mosse per il gioco del 15 / sudoku
  • soluzione: algoritmi di enumerazione, fermandosi alla prima soluzione trovata
• conteggio
  • contare il numero di modi in cui é possibile esprimere un valore n come somma di k primi
  • soluzione: enumerare tutte le soluzioni possibilie contarle
• ottimizzazione
  • trovare una delle soluzioni ammissibili migliori rispetto a un certo criterio di valutazione

Il backtracking è la filosofia della vita: prova a fare qualcosa, se non va bene lascia stare e prova qualcos’altro.

Steps

Let’s look at the steps involved in the backtracking algorithm.

1. If the current state is the answer/ result, return SUCCESS.
2. ELSE
3. If the current state is the endpoint/ invalid, return FAILED.
4. ELSE IF, the current state is not the endpoint/ invalid, repeat the above steps for the next input.

The backtracking algorithm involves recursion and recursive calls at its core. Let’s look at how the recursive call is made.

1. Do something – This action can be something like adding a value to a list or adding a character to a string.
2. Make a recursive call – This recursive call will usually be for the next set of inputs that should be considered for processing.
3. Undo what was done in Step 1 – This will undo the additions done in step 1. And it can be something like removing the last element from the list or removing the last character from the string.

The last step of undoing step 1 is very important in the backtracking algorithm. In the above example, have a look at figure 2. We add 1 in the first step & 2 in the second step. Then, we see that this violates our condition of not having 1 & 2 adjacent to each other. Here, we backtrack and undo what we did earlier by removing 2 and then we add 3 in its place and move forward from there.