Bactracking
Algoritmi e Strutture Dati
Capitolo 16 - Backtrack
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
© Alberto Montresor
1
Introduzione
Classi di problemi (decisionali, di ricerca, di ottimizzazione)
✦
Definizioni basate sul concetto di soluzione ammissibile: una soluzione che
soddisfa un certo insiemi di criteri
✦
Problemi “tipici”
✦
Contare le soluzioni ammissibili
✦
Costruire almeno una o tutte le soluzioni ammissibili
✦
Trovare le soluzioni ammissibili “più grandi”, “più piccole” o
in generale “ottimali”
✦
Esempio:
✦
Elencare tutti i sottoinsiemi di k elementi di un insieme S
✦
© Alberto Montresor
2
Problemi: commenti
Enumerazione
✦
Elencare algoritmicamente tutte le possibili soluzioni ammissibili
(spazio di ricerca)
✦
Costruire almeno una soluzione
✦
Si utilizza l'algoritmo per elencare tutte le soluzioni, fermandosi alla prima
✦
Contare le soluzioni
✦
In molti casi, è possibile contare in modo analitico
✦
Esempio: |S| = n, # sottoinsiemi di k elementi:
✦
In altri casi, si costruiscono le soluzioni e si contano
✦
© Alberto Montresor
3
Problemi: commenti


Trovare le soluzioni ottimali

Si costruiscono tutte le soluzioni e si valuta una funzione di costo

Si possono utilizzare altre tecniche:

Programmazione dinamica, greedy

Tecniche risolutive per problemi intrattabili
Esempi:

Circuito hamiltoniano (commesso viaggiatore)
© Alberto Montresor
4
Costruire tutte le soluzioni
Per costruire tutte le possibili soluzioni, si utilizza un approccio “brute-force”: si
esamina interamente lo spazio delle possibili soluzioni
✦
A volte è l'unica strada possibile
✦
La potenza dei computer moderni rende “affrontabili” problemi
di discrete dimensioni
✦
10!
✦
= 3.63 · 106
220 = 1.05 · 106
✦
permutazione di 10 elementi
sottoinsieme di 20 elementi
Inoltre, a volte non è necessario analizzare l'intero spazio delle soluzioni
✦
© Alberto Montresor
5
Backtracking
Filosofia:
✦
“Prova a fare qualcosa, e se non va bene, disfalo e prova qualcos'altro”
✦
Come funziona?
✦
Un metodo sistematico per iterare su tutte le possibili istanze di uno spazio di
ricerca
✦
E' una tecnica algoritmica che, come altre, deve essere personalizzata per ogni
applicazione individuale
✦
© Alberto Montresor
6
Backtracking
Organizzazione generale
✦
Una soluzione viene rappresentata come un vettore S[1..n]
✦
Il contenuto degli elementi S[i] è preso da un insieme di scelte C
dipendente dal problema
✦
Esempi:
✦
C insieme generico, possibili soluzioni permutazioni di C
✦
C insieme generico, possibili soluzioni sottoinsiemi di C
✦
C mosse di gioco, possibili soluzioni sequenze di mosse
✦
C archi di un grafo, possibili soluzioni percorsi sul grafo
✦
© Alberto Montresor
7
Backtracking
Come procedere: ad ogni passo, partiamo da una soluzione parziale S[1..k]
✦
Se S[1..k] è una soluzione ammissibile, la “processiamo” in qualche modo e
abbiamo finito
✦
Altrimenti:
✦
Se è possibile, estendiamo S[1..k] con una delle possibili scelte in una
soluzione S[1..k+1], e valutiamo la nuova soluzione ricorsivamente
✦
Altrimenti, “cancelliamo” (ritornando indietro nella ricorsione) l'elemento
S[k] (backtrack) e ripartiamo dalla soluzione S[1..k-1]
✦
Si può fare backtrack su più passi di ricorsione
✦
© Alberto Montresor
8
Backtracking
Spazio di ricerca ≡ albero di decisione
✦
Soluzioni ≡ foglie in un albero di decisione
✦
Soluzioni parziali ≡ nodi interni dell'albero di decisione
✦
Radice ≡ soluzione parziale vuota
✦
© Alberto Montresor
9
Backtracking
Lo spazio di ricerca può essere ridotto:
✦
“Rami” dell'albero che sicuramente non portano a soluzioni ammissibili possono
essere “potati” (pruned)
✦
La valutazione viene fatta nelle soluzioni parziali radici del sottoalbero
da potare
✦
© Alberto Montresor
10
Backtracking
Due possibili approcci:
✦
Ricorsivo:
✦
lavora tramite una visita in profondità nell'albero delle scelte, basata su un
approccio ricorsivo
✦
Iterativo: utilizza un approccio greedy, eventualmente tornando
sui propri passi
✦
Esempio: Inviluppo convesso
✦
Esempio: String matching
✦
© Alberto Montresor
11
Algoritmo generico


Ritorna true per bloccare
l'esecuzione, ad esempio
dopo la prima soluzione
Ritorna false per
le soluzioni parziali



© Alberto Montresor
C insieme di possibili
candidati per estendere
la soluzione
S: vettore contenente la
soluzione parziale S[1..i]
...: informazioni addizionali
12
Esempio 1
Problema
✦
Elencare tutti i sottoinsiemi di un insieme S
✦
Problemi
✦
Quali sono le scelte possibili?
✦
© Alberto Montresor
13
Esempio 1: commenti

Commenti



Non c'è pruning. Tutto lo spazio possibile viene esplorato.
Ma questo avviene per definizione
In che ordine vengono stampati gli insiemi?
E' possibile pensare ad una soluzione iterativa, ad-hoc?
(non-backtracking)
© Alberto Montresor
14
Esempio 1: versione iterativa
© Alberto Montresor
15
Esempio 2
Problema
✦
Elencare tutti i sottoinsiemi di dimensione k di un insieme S
✦
Versione iterativa
✦
Qual è il costo?
✦
Soluzione basata su backtracking
✦
Possiamo potare?
✦
© Alberto Montresor
16
Esempio 2: 1° tentativo
Qual è il problema?
© Alberto Montresor
17
Esempio 2: 2° tentativo
Qual è il problema?
© Alberto Montresor
18
Esempio 2: Tentativo corretto
© Alberto Montresor
19
Esempio 2: vantaggi
© Alberto Montresor
20
Esempio 2: sommario
Cosa abbiamo imparato?
✦
“Specializzando” l'algoritmo generico, possiamo ottenere una versione più
efficiente
✦
Versione efficiente per
✦
valori di k “piccoli” (vicini a 1)
✦
valori di k “grandi” (vicini a n)
✦
Miglioramento solo parziale verso n/2
✦
E' difficile ottenere la stessa efficienza con un algoritmo iterativo
✦
© Alberto Montresor
21
Esempio 3

Problema


Stampa di tutte le permutazioni di un insieme A
Rispetto al problema precedente:

L'insieme dei candidati dipende dalla soluzione parziale corrente
© Alberto Montresor
22
n Regine
Problema: posizionare n regine in una scacchiera n·n, in modo tale che nessuna
regina ne “minacci” un'altra.
✦
Commenti storici:
✦
Il problema classico, con n=8, è stato studiato, fra gli altri,
anche da Gauss
✦
Metodo
✦
Partiamo dall'approccio più stupido,
e mano a mano raffiniamo la soluzione.
✦
© Alberto Montresor
23
n Regine
Idea: ci sono n2 caselle dove piazzare una regina
✦
Algoritmo:
✦
S[1..n2] array binario
✦
controllo soluzione
✦
choices(S, n, i)
✦
S[i] = true ⇒ “regina in S[i]”
se i = n2
ritorna { true, false} se regina in
S[i] non minaccia le
regine in
S[1..i-1], { false }
altrimenti
# soluzioni per n=8
✦
264 ~ 1.84 · 1019
Commenti:
✦
Forse abbiamo un problema di rappresentazione?
✦
Matrice binaria molto sparsa
✦
© Alberto Montresor
24
n Regine
Idea: Dobbiamo piazzare n regine, ci sono n2 caselle
✦
Algoritmo
✦
S[1..n] coordinate in 1..n2
S[i] coordinata della regina i
controllo soluzione
se i = n
✦
✦
choices(S, n, i)
✦
# soluzioni per n=8
✦
ritorna posizioni legali
(n2)n = 648 = 248 ~ 2.81 · 1014
Commenti
✦
C'è un miglioramento, ma lo spazio è ancora grande...
✦
Problema: una soluzione “1-7-....” come si distingue da “7-1-....” ?
✦
© Alberto Montresor
25
n regine
Idea: la regina i non può stare in una casella “precedente” alla regina i-1
(S[i-1] < S[i])
✦
Algoritmo
✦
S[1..n] coordinate in 1..n2
S[i] coordinata della regina i
controllo soluzione
se i = n
✦
✦
choices(S, n, i)
✦
# soluzioni per n=8
✦
ritorna posizioni legali, S[i-1] < S[i]
(n2)n / n! = 648 / 40320 ~ 6.98 · 109
Commenti:
✦
Ottimo, abbiamo ridotto molto, ma si può ancora fare qualcosa
✦
© Alberto Montresor
26
n regine
Idea: ogni riga della scacchiera deve contenere esattamente una regina. Infatti non
ne può contenere 2 o più, e se ne contenesse 0 un'altra riga dovrebbe contenerne 2
✦
Algoritmo
✦
S[1..n] valori in 1..n
S[i] colonna della regina i
✦
controllo soluzione
✦
choices(S, n, i)
✦
# soluzioni per n=8
✦
se i = n
ritorna le colonne “legali”
nn = 88 ~ 1.67 · 107
Commenti
✦
Quasi alla fine
✦
© Alberto Montresor
27
n regine
Idea: anche ogni colonna deve contenere esattamente una regina;
i numeri 1..n devono apparire in S[1..n] come permutazione
✦
Algoritmo
✦
Modifichiamo l'algoritmo delle permutazioni per verificare anche le diagonali
✦
# soluzioni per n=8
✦
n! = 40320 ~ 4.03 · 104
# soluzioni effettivamente visitate: 15720
✦
QuickTime™ and a
GIF decompressor
are needed to see this picture.
© Alberto Montresor
28
n regine
Non è la soluzione migliore per ottenere una soluzione
✦
Minimum-conflicts heuristic
✦
Si muove il pezzo con il più grande numero di conflitti nella casella delle stessa
colonna con il numero minimo di conflitti
✦
Per n=106, circa 50 passi in media
✦
Assume che la soluzione iniziale sia “ragionevolmente buona”.
✦
Ogni regina viene messa nella colonna che ha il numero minimo di conflitti
con le regine già sulla scacchiera
✦
Al contrario, se tutte le regine sono sulla stessa riga, ci vogliono almeno n-1
spostamenti
✦
Questo algoritmo non garantisce che la terminazione sia sempre corretta
✦
© Alberto Montresor
29
Giro di cavallo
Problema:
✦
Si consideri ancora una scacchiera n·n; lo scopo è trovare un “giro di cavallo”,
ovvero un percorso di mosse valide del cavallo in modo che ogni casella venga
visitata al più una volta
✦
Soluzione:
✦
Tramite backtrack
✦
© Alberto Montresor
30
Giro di cavallo
Soluzione
✦
Matrice n∙n contenente le cui celle contengono
✦
0
se la cella non è mai stata visitata
i
se la cella è stata visitata al passo i
✦
✦
# soluzioni: 64! ~ 1089
✦
Ma: ad ogni passo ho al massimo 8 caselle possibili, quindi ne visito al più
864 ~1057
✦
In realtà, grazie al pruning ne visito molto meno
✦
© Alberto Montresor
31
Giro di cavallo
© Alberto Montresor
32
Sudoku
“Suuji wa dokushin ni kagiru”
✦
© Alberto Montresor
33
Sudoku
© Alberto Montresor
34
Sudoku
© Alberto Montresor
35
Generazione labirinti


Problemi

Come generare un labirinto in una scacchiera n·n?

Come uscire da un labirinto?
Esempio:
© Alberto Montresor
36
Un ultimo puzzle
Problema
✦
Si consideri ancora una scacchiera n·n, con n=2k
✦
Qualsiasi scacchiera di questo tipo con una cella rimossa può essere ricoperta da
triomini a forma di L
✦
Trovare un algoritmo che trovi una possibile
ricopertura della scacchiera
✦
© Alberto Montresor
37
Inviluppo convesso
Definizione
✦
Un poligono nel piano bidimensionale è convesso se ogni segmento di retta che
congiunge due punti del poligono sta interamente nel poligono stesso, incluso il
bordo.
✦
Inviluppo convesso (Convex hull)
✦
Dati n punti p1, . . . , pn nel piano, con n ≥ 3, trovare il più piccolo poligono
convesso che li contiene tutti
✦
© Alberto Montresor
38
Inviluppo convesso
Un algoritmo banale ma inefficiente
✦
Un poligono può essere rappresentato per mezzo dei suoi spigoli
✦
Si consideri la retta che passa per una coppia di punti i,j, che divide il piano in due
semipiani chiusi
✦
Se tutti i rimanenti n-2 punti stanno dalla stessa parte, allora lo spigolo Sij fa parte
dell’inviluppo convesso
✦
© Alberto Montresor
39
Inviluppo convesso
© Alberto Montresor
40
Algoritmo di Graham
Algoritmo di Graham (1972)
✦
Il punto con ordinata minima fa parte dell’inviluppo convesso
✦
Si ordinano i punti in base all’angolo formato dalla retta passante per il punto con
ordinata minima e la retta orizzontale
✦
© Alberto Montresor
41
© Alberto Montresor
42
Algoritmo di Graham
© Alberto Montresor
43
Algoritmo di Graham
© Alberto Montresor
44
Algoritmo di Graham
Complessità
✦
O(n log n), perchè dominato dalla fase di ordinamento degli angoli
✦
© Alberto Montresor
45