Algoritmi e Strutture Dati Capitolo 16

Bactracking
Introduzione
Algoritmi e Strutture Dati
✦
✦
Alberto Montresor
✦
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.
1
© Alberto Montresor
Problemi: commenti
✦
✦
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
✦
u
Elencare algoritmicamente tutte le possibili soluzioni ammissibili (spazio di ricerca)
Trovare le soluzioni ottimali
u
Si costruiscono tutte le soluzioni e si valuta una funzione di costo
u
Si possono utilizzare altre tecniche:
Costruire almeno una soluzione
Si utilizza l'algoritmo per elencare tutte le soluzioni, fermandosi alla prima
u
Contare le soluzioni
✦
In molti casi, è possibile contare in modo analitico
✦
✦
Esempio: |S| = n, # sottoinsiemi di k elementi:
2
© Alberto Montresor
Problemi: commenti
Enumerazione
✦
✦
Problemi “tipici”
✦
Università di Trento
✦
Definizioni basate sul concetto di soluzione ammissibile: una soluzione che
soddisfa un certo insiemi di criteri
✦
Capitolo 16 - Backtrack
✦
Classi di problemi (decisionali, di ricerca, di ottimizzazione)
Programmazione dinamica, greedy
u
Tecniche risolutive per problemi intrattabili
Esempi:
u
n!
(n k)!k!
u
Circuito hamiltoniano (commesso viaggiatore)
In altri casi, si costruiscono le soluzioni e si contano
© Alberto Montresor
3
© 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
✦
✦
✦
Backtracking
✦
A volte è l'unica strada possibile
La potenza dei computer moderni rende “affrontabili” problemi
di discrete dimensioni
✦
10! = 3.63 · 106
permutazione di 10 elementi
✦
220
sottoinsieme di 20 elementi
= 1.05 ·
106
✦
5
✦
✦
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
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
6
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:
✦
Esempi:
✦
Come funziona?
✦
Il contenuto degli elementi S[i] è preso da un insieme di scelte C dipendente dal problema
C insieme generico, possibili soluzioni permutazioni di C
“Ritenta, e sarai più fortunato”
© Alberto Montresor
✦
Una soluzione viene rappresentata come un vettore S[1..n]
✦
✦
Backtracking
Organizzazione generale
✦
“Prova a fare qualcosa, e se non va bene, disfalo e prova qualcos’altro”
✦
Backtracking
✦
✦
✦
Inoltre, a volte non è necessario analizzare l'intero spazio delle soluzioni
© Alberto Montresor
Filosofia:
✦
✦
7
© Alberto Montresor
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
8
tematici, come il Sudoku. Questo problema può essere risolto semplicemente terminando
l’enumerazione alla prima occorrenza di una soluzione.
Backtracking
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
Lo
di ricerca
essere
ridotto: si utilizza un approccio a “forza bruta”, basato
Perspazio
enumerare
tutte le può
soluzioni
ammissibili,
✦ “Rami”
su backtrack,
che
esplora loche
spazio
delle soluzioni
in modo
sistematico.
Una soluzione
viene
dell'albero
sicuramente
non portano
a soluzioni
ammissibili
possono
rappresentata
come
un
vettore
S[1
.
.
.
n].
Il
contenuto
degli
elementi
S[i]
è
preso
da
un
insieme
essere “potati” (pruned)
di scelte dipendente dal particolare problema. Ad ogni passo, si parte da una soluzione parziale
✦ La valutazione viene fatta nelle soluzioni parziali radici del sottoalbero S[1 . . . i 1]; se è possibile, si estende tale soluzione con una delle possibili scelte in una
da potare
soluzione parziale S[1 . . . i] e si valuta la nuova soluzione parziale ricorsivamente; altrimenti,
si opera un passo di backtrack (ritornando indietro nella ricorsione) e si effettua una nuova
scelta fra quelle possibili a partire da S[1 . . . i 1].
✦
La procedura enumerazione() realizza questo schema. Ad ogni chiamata della procedura,
l’insieme C delle possibili opzioni per la scelta i-esima viene calcolato a partire dalle scelte
precedenti S[1 . . . i 1]. Tutte le possibili strade vengono quindi intraprese: uno dopo l’altro,
tutti i valori di C vengono scelti e memorizzati in S[i]; se S[1, . . . , i] è una soluzione ammissibile, tale soluzione viene elaborata in qualche modo (stampata, contata, valutata in base ad
una funzione di costo, etc.) dalla procedura processSolution(). Infine, la procedura enumerazione() chiama ricorsivamente se stessa, dando per assodate le prime i scelte e spostandosi
sull’(i + 1)-esima. La ricorsione termina quando l’albero è stato visitato completamente.
9
© Alberto Montresor
Backtracking
✦
boolean enumerazione(I TEM[ ] S, integer n, integer i, . . . )
Due possibili approcci:
✦
S ET C ⇥ choices(S, n, i, . . .)
% Determina C in funzione di S[1 . . . i
foreach c ⇤ C do
S[i] ⇥ c
if S[1 . . . i] è una soluzione ammissibile then
if processSolution(S, n, i, . . .) then return true
if enumerazione(S, n, i + 1, . . .) then return true
return false
Ricorsivo:
✦
✦
Per supportare il caso in cui è sufficiente generare una e una sola soluzione ammissibile, le10
procedure enumerazione() e processSolution() restituiscono un valore booleano, vero se una
soluzione ammissibile è stata trovata, falso altrimenti.
Algoritmo generico
© Alberto Montresor
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
1]
l C insieme di possibili Ritorna true per bloccare
Applichiamo
lo
schema
precedente
all’Esempio
16.13. In questo
caso, la scelta possibile è
candidati
per estendere
l'esecuzione, ad esempio
la
soluzione
dopo laoprima
se inserire
meno soluzione
un elemento; l’insieme delle scelte è quindi dato da {true,false} e il vettore
Ritorna false
Sl costituisce
unaper
rappresentazione
booleana dell’insieme generato. L’insieme delle scelte è
le
soluzioni
parziali
l S:sono
tuttavia vuoto quando tutti gli elementi
già contenente
stati esaminati,
vettore
la ovvero quando i > n.
soluzione
parziale
S[1..i]
Dato un insieme di n elementi, l’elemento i-esimo può essere presente oppure no. In
l ...: informazioni addizionali
altre parole, l’insieme delle scelte è dato da {true,false} e il vettore S è una rappresentazione booleana dell’insieme generato. Una prima versione dell’algoritmo potrebbe essere la
l
11
© Alberto Montresor
12
S ET A
Esempio 1
✦
;
while A non forma un albero di copertura do
S ET mst-generico
(Gsicuro
RAPH G,
] w)
trova un arco
[u,integer[
v]
Problema
SElencare
ETA
A tutti
;[
A
{[u, v]} di un insieme S
i sottoinsiemi
while AAnon forma un albero di copertura do
return
Esempio 1: commenti
u
Commenti
u
✦
✦
Problemi
trova un arco sicuro [u, v]
✦
u
Quali
A sonoAle[scelte
{[u,possibili?
v]}
u
return A
subsets(integer[ ] S, integer n, integer i)
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)
S ET C
iif(i  n, {0, 1}, ;)
foreach
c 2 C ]do
subsets
(boolean[
S, integer n, integer i)
S[i]
c
S ET C
iif(i  n, {true, false}, ;)
if i = n then
foreach c 2 C do
(S, n)
S[i] processSolution
c
subsets
if
i = n (S,
thenn, i + 1)
processSolution(S, n)
© Alberto Montresor
subsets(S, n, i + 1)
13
Esempio 1: versione iterativa
© Alberto Montresor
14
Esempio 2
subsets(integer n)
for j
0 to 2n 1 do
subsets(integer n)
print ’{’
for jfor i0 to 02nto n1 do1 do
print ’{’
if (j and 2i ) 6= 0 then
for i
0 to n i 1 do
print
✦
Problema
✦
✦
Versione iterativa
✦
if (j and 2i ) 6= 0 then
print ’}’
print i
✦
Qual è il costo?
Soluzione basata su backtracking
✦
print ’}’
Elencare tutti i sottoinsiemi di dimensione k di un insieme S
Possiamo potare?
subsets(integer[ ] S, integer n, integer k, integer i)
subsets
] S,n,integer
S ET C(boolean[
iif(i 
{0, 1},n,
;)integer k, integer i)
foreach
2(iCdo
S ET C c iif
n, {true, false}, ;)
S[i] c 2 cC do
foreach
S[i]
if i = nc then
© Alberto Montresor
15
© Alberto Montresor
16
subsets(S, n, k, i + 1, count)
Esempio
2: 1° tentativo
count
count S[i])
Esempio 2:essere
2° tentativo
potrebbe
la seguente:
subsets(integer[ ] S, integer n, integer k, integer i)
subsets(integer[ ] S, integer n, integer k, integer i, integer count)
Questo algoritmo, invocato da subsets(S, n, k, 1, 0), genera tutti i sottoinsiemi di un insieS ET
C
iif(i
 n, {0,
1}, ;)
iif(i  n, {0, 1}, ;)
me di
n elementi,
e invoca
processSolution() sui soli sottoinsiemi di k elementi. A tal scopo, S ET C
foreachcount
c 2 conta
C doquanti elementi sono presenti nel sottoinsieme corrente. Il costo della foreach c 2 C do
la variabile
S[i]
c
S[i]
c
procedura
è ovviamente
O(2n ).
i = n(Albero
then delle scelte per sottoinsieme). L’enumerazione
Esempioif16.14
visualizzata
Qualpuò
è il essere
problema?
integer
count
0
come la visita in profondità di un albero di scelte, dove ad ogni nodo corrisponde una soluzione
for jno). 1Nel
to caso
n dodi subsets(), l’albero è binario e completo, con tutte le sue
(parziale oppure
count
+ S[j]
foglie al livello n.
La figuracount
Fig. 16.5
mostra l’albero con n = 4, k = 2. I sottoinsiemi con
esattamente kif =
2 nodi
evidenziati in grigio.
count
=sono
k then
(S, n) completamente l’albero. Ci sono tanti casi in cui
In realtà, nonprocessSolution
è necessario analizzare
count
count + S[i]
if i = n and count = k then
processSolution(S, n)
subsets(S, n, k, i + 1, count)
count
count S[i]
Qual è il problema?
una soluzione
parziale
potrà
subsets
(S, n, non
k, i +
1) mai generare una soluzione ammissibile: ad esempio, se
un insieme ha già k elementi, oppure se le scelte ancora da prendere non sono sufficienti a Questo algoritmo, invocato da subsets(S, n, k, 1, 0), genera tutti i sotto
ottenere un insieme di k elementi. In questo caso, si dice che l’albero di decisione viene
me di n elementi, e invoca processSolution() sui soli sottoinsiemi di k elem
“potato” (in inglese pruned): i rami che non possono generare (ulteriori) soluzioni possibili
la variabile count conta quanti elementi sono presenti nel sottoinsieme corr
9
17
18
vengono
© Alberto
Montresor ignorati.
© Alberto Montresor
n
procedura
è
ovviamente
O(2
).
Il nostro algoritmo può essere semplicemente modificato cambiando l’insieme delle scelte,
Esempio
2: Tentativo
corretto
Esempio 2: vantaggi
e modificando
la condizione
di ammissibilità, ma il tempo resta comunque O(2n ).
Esempio
16.6 (Albero delle scelte per sottoinsieme). L’enumerazione può
come la visita in profondità di un albero di scelte, dove ad ogni nodo corrisp
(parziale oppure no). Nel caso di subsets(), l’albero è binario e comple
foglie al livello n. La figura Fig. 16.5 mostra l’albero con n = 4, k = 2.
esattamente k = 2 nodi sono evidenziati in grigio.
subsets(integer[ ] S, integer n, integer k, integer i, integer count)
S ET C = iif(count < k and count + (n
foreach c 2 C do
S[i]
c
count
count + S[i]
if count = k then
processSolution(S, i)
else
subsets(S, n, k, i + 1, count)
count
count S[i]
© Alberto Montresor
i + 1)
k, {0, 1}, ;)
In realtà, non è necessario analizzare completamente l’albero. Ci son
una soluzione parziale non potrà mai generare una soluzione ammissibi
un insieme ha già k elementi, oppure se le scelte ancora da prendere non
ottenere un insieme di k elementi. In questo caso, si dice che l’albero
“potato” (in inglese pruned): i rami che non possono generare (ulteriori)
vengono ignorati.
Il nostro algoritmo può essere semplicemente modificato cambiando l’in
e modificando la condizione di ammissibilità, ma il tempo resta comunque
19
subsets(integer[ ] S, integer n, integer k, integer i, integer count)
© Alberto Montresor
20
Esempio 2: sommario
✦
Esempio 3
Cosa abbiamo imparato?
✦
u
“Specializzando” l'algoritmo generico, possiamo ottenere una versione più
efficiente
u
u
✦
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
✦
✦
foreach c ⌅ A do
S[i] ⇤ c
A.remove(c)
if A.isEmpty() then processSolution(S, n)
permutations(A, n, S, i + 1)
A.insert(c)
21
Idea: ci sono
n2 caselle16.7
dove piazzare
una ne
regina
Soluzione
Esercizio
Una regina
può minacciare un’altra se si trovano
riga, colonna o diagonale. Data una scacchiera n ⇥ n, è possibile rappresentare la
✦ Algoritmo:
vari modi,2 molti dei quali poco efficienti. Ad esempio,
✦
Il problema classico, con n=8, è stato studiato da Gauss (fra gli altri)
S[1..n ] array binario
S[i] = true ⇒ “regina in S[i]”
–✦ secontrollo
l’insieme
delle possibili scelte
soluzione
se i = èn2metto / non metto una regina in una partico
la soluzione è rappresentata da una matrice n ⇥ n di booleani e la dimensione
✦ choices(S, n, i)
{ true, false} 2
da analizzare (salvo potature) è pari a 2n ;
✦
se la nuova
minacciain
una
– sepruning
l’insieme delle possibili verifica
scelte contiene
le regina
n2 posizioni
cui una delle n
delle regine esistenti, nel qual caso restituisce { }
essere collocata, la soluzione è rappresentata da un vettore di n interi in {1, .
✦ # soluzioni per n=8
264 ~ 1.84 · (salvo
1019 potature) è pari a (n2 )n .
dimensione dello spazio da analizzare
Metodo
Partiamo dall'approccio più stupido,
e mano a mano raffiniamo la soluzione.
✦
© Alberto Montresor
22
Soluzione Esercizio 16.5 La soluzione è simile a quella vista per le permu
nl’unico
Regineaccorgimento che l’elemento c scelto nel ciclo foreach deve essere diverso
© Alberto Montresor
✦
Commenti storici:
✦
daRispetto
A l’elemento
scelto,precedente:
e lo reinseriamo al momento di fare un passo di backtrack.
al problema
iniziale
è permutations(A, n, S, 1).
u
permutations(S ET A, integer n, I TEM[ ] S, integer i)
Problema: posizionare n regine in una scacchiera n·n, in modo tale che nessuna
regina ne “minacci” un'altra.
✦
Stampa di tutte le permutazioni di un insieme A
L'insieme dei candidati dipende dalla soluzione parziale corrente
n Regine
✦
Problema 16. BACKTRACK
CAPITOLO
23
Commenti:
Queste
dimensioni sono molto grandi; ma è possibile semplificare le cose notando c
✦ Forse abbiamo un problema di rappresentazione?
deve
contenere esattamente una regina, e lo stesso vale per le colonne. Quindi,
di ✦ognuna
n molto
reginesparsa
può essere rappresentata da un numero in {1, . . . , n},
Matricedelle
binaria
delle posizioni deve essere una permutazione di tale insieme. Lo spazio da analizz
grande n!. Per completare la soluzione, lo spazio deve essere ulteriormente pot
© Alberto Montresor
24
n Regine
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)
{ 1 … n2 }
✦
pruning
ritorna il sottoinsieme di mosse legali
✦
# soluzioni per n=8
(n2)n = 648 = 248 ~ 2.81 · 1014
✦
✦
✦
C'è un miglioramento, ma lo spazio è ancora grande...
✦
Problema: una soluzione “1-7-....” come si distingue da “7-1-....” ?
✦
25
S[1..n] coordinate in 1..n2
S[i] coordinata della regina i
✦
controllo soluzione
se i = n
✦
choices(S, n, i)
{ 1 … n2 }
✦
pruning
ritorna posizioni legali, S[i-1] < S[i]
✦
# soluzioni per n=8
(n2)n / n! = 648 / 40320 ~ 6.98 · 109
✦
Algoritmo
S[1..n] valori in 1..n
S[i] colonna della regina i, dove riga = i
controllo soluzione
se i = n
✦
choices(S, n, i)
{1 … n }
✦
pruning
ritorna le colonne “legali”
✦
# soluzioni per n=8
nn = 88 ~ 1.67 · 107
✦
Ottimo, abbiamo ridotto molto, ma si può ancora fare qualcosa
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
✦
Commenti:
© Alberto Montresor
✦
✦
✦
✦
n regine
✦
Algoritmo
Commenti
© Alberto Montresor
✦
Idea: la regina i non può stare in una casella “precedente” alla regina i-1 (S[i-1] < S[i])
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
✦
# soluzioni effettivamente visitate: 15720
n! = 40320 ~ 4.03 · 104
Commenti
✦
Quasi alla fine
© Alberto Montresor
27
© Alberto Montresor
28
n regine
✦
Giro di cavallo
Non è la soluzione migliore per ottenere una soluzione
✦
Minimum-conflicts heuristic
✦
✦
✦
✦
✦
✦
Problema:
✦
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
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
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
10
29
© Alberto Montresor
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
Alg
10
10
Algoritmi e Strutture di Dati
Algoritmi e Strutture di Dati
boolean cavallo(integer[ ][ ] S, integer i, integer x, integer y)30
S ET C ⇤ mosse(S, x, y)
foreach c ⌅ C do
Giro di cavallo
cavallo(boolean[ ][ ] S, integer i, integer x, integer y)S[x, y] ⇤ i
if i = 81 then
S ET C cavallo
⇥ mosse
(S, x,][y)] S, integer i, integer x, integerprocessSolution
boolean
(integer[
y)
(S)
foreach c ⇤ C do
return
true
S ET C
mosse(S, x, y)
S[x, y] ⇥ i
if cavallo(S, i + 1, x + mx [c], y + my [c]) then
foreach c 2 C do
return true;
if
i =y]81 then
S[x,
i
processSolution(S)
return false
© Alberto Montresor
if i = 64 then
return
true (S)
processSolution
if cavallo
(S,
i + 1, x + mx [c], y + my [c]) then
return true
return true;
if cavallo(S, i + 1, x + mx [c], y + my [c]) thenmx ⇤ { 1, +1, +2, +2, +1, 1, 2, 2}
return true;
return false
my ⇤ { 2, 2, 1, +1, +2, +2, +1, 1}
S[x, y]
0
return false
# soluzioni: 64! ~ 1089
Ma: ad ogni passo ho al massimo 8 caselle possibili, quindi ne visito al più 864 ~1057
mx ⇥ { 1, +1, +2, +2, +1, 1, 2, 2}
my ⇥ { 2, 2, 1, +1, +2, +2, +1, 1}
In realtà, grazie al pruning ne visito molto meno
mx
my
{ 1, +1, +2, +2, +1, 1, 2, 2}
{ 2, 2, 1, +1, +2, +2, +1, 1}
S ET mosse(integer[ ][ ] S, integer x, integer y)
S ET C ⇤ Set()
for integer i ⇤ 1 to 8 do
nx ⇤ x + mx [i]
ny ⇤ y + my [i]
if 1 ⇥ nx ⇥ 8 and 1 ⇥ ny ⇥ 8 and S[nx , ny ] = 0 then
C.insert(i)
return C
© Alberto Montresor
31
S ET mosse(integer[ ][ ] S, integer x, integer y)
S ET C
Set()
for
integer
i
1 to 8 do
© Alberto Montresor
32
sto capitolo, vediamo un gioco matematico che può essere risolto agil5 6 sud7 3
k. Nel
Sudoku è data una tabella formata da 9 righe e29 colonne,
Sudoku
3 con 2 1
di 3 righe e 3 colonne ciascuna, dove alcune caselle sono 8riempite
9 1 e 97
e 9. ✦Si“Suuji
devonowa
riempire
le caselle
vuote con numeri compresi tra
dokushin
ni
kagiru”
Algoritmi
3 7tutti i numeri
8tra e Strutture
9 di2Dati
ga,302
ciascuna colonna e ciascuna sottotabella contenga
la tabella in ingressola soluzione è:
inizializzato a tutti zero e x, y è una posizione qualsiasi. Al termine, se la risposta è true, la
2 5
9
7 6
2 5 3 8 9 1 4 7 6
matrice A contiene il percorso del cavallo.
8 9 7 2 6 4
2
4
4 1 x, 5integer
7 y)
3
1 5(integer[3][ ] A,9 integer n, integer6 k, integer
boolean cavallo
3
9
1
2
5
8
A[x,8y] ⇤
7 8 9 4 3 5 2
9 k 4
5 2 6
2
if
k
=
n
then
return
true
1 3 6 7 2 9 8
1
2
4
for 2
integer
i
⇤
1
to
8
do
4 2 5 6 1 8 7
5 6
7 3
nx ⇤ x + X[i]
9 6 8 3 5 2 1
8 y +3Y [i] 2 1
ny ⇤
9 ny]4 = 70 then
6
if nx ⇥ 19and nx 7 n and ny ⇥ 1 and ny5 n1and2A[nx,
3 true
7 4 1 8 6 5
3 7 if cavallo(A,
8 n, k + 1, nx,9ny)2then return
6
5
3
1
4
9
4
8
9
7
3
2
A[x, y] = 0
return false
2 5 3
8 9 7
© Alberto Montresor
6 4 1
processSolution(S, n)
return(partrue
L’algoritmo risolutivo è mostrato con la procedura sudoku(). La tabella del Sudoku
if sudoku(S, i + 1) then return true
interi, presa in
8 zialmente
9 1 inizializzata)
4 7 6 viene memorizzata in una matrice S[0 . . . 8][0 . . . 8] di
S[x, y]
old
2 6 4 3 1 5
return false
33
© Alberto Montresor
5 7 3 9 2 8
1 3 6 7 2 9 8 5 4
boolean
4 2 check
5 (integer[
6 1 ][8] S, 7integer
3 x,9 integer y, integer c)
9for 6integer
8 j 3⇤ 05to 8 2do 1 4 7
5 1if S[x,
2 j] =
9 c then
4 7return
6 false
8 3
if S[j, y] = c then return false
7
4
boolean sudoku(integer[ ][ ] S, integer i)
S ET C
Set()
integer x
i mod 9
integer y
bi/9c
if i  80 then
if S[x, y] 6= 0 then
C.insert(S[x, y])
else
for integer c
1 to 9 do
if check(S, x, y, c) then C.insert(c)
integer old
S[x, y]
foreach c 2 C do
S[x, y]
c
if i = 80 then
Soluzione Esercizio 16.9 La procedura check(S, x, y, c) controlla che l’aggiunta del numero
7 casella
8 9 S[x,
4 y] 3non sia
5 in2contrasto
6 1con i valori già presenti.
c Sudoku
nella
3
{1, 2, . . . , n2 }, dove il Sudoku classico corrisponde a n = 3. In questo caso il costo della
procedura
Sudokuè superpolinomiale.
1
8
6
5
9
2
34
Generazione labirinti
16.5 Esercizi
u
Problemi
Esercizio 16.1 (Angoli ↵). Se dx e dy sono le differenze tra le ascisse e le ordinate dei punti
pi e p1u, calcolare
l’angolo un
↵ =
tan 1 dy/dx
la funzione
di libreria per l’arcotangente
Come generare
labirinto
in unacon
scacchiera
n·n?
richiede
parecchio tempo. Dato che ↵ serve solo nella fase di ordinamento dei punti dell’algou
Come uscire da un labirinto?
ritmo di Graham, si può utilizzare una quantità diversa dall’angolo ↵, più veloce da calcolare
euche produca lo stesso ordinamento. Si dimostri che dy/(dy + dx) è adatta allo scopo e si
% Controllo sulla colonna
% Controllo sulla riga
integer bx ⇤ ⌅x/3⇧
vo è mostrato
la procedura sudoku(). La tabella del Sudoku (parinteger bcon
y ⇤ ⌅y/3⇧
viene for
memorizzata
in 0una
S[0 . . . 8][0 . . . 8] di interi, presa in
integer ix ⇤
to 2matrice
do
for integer iy ⇤ 0 to 2 do
% Controllo sulla sottotabella
if S[bx · 3 + ix , by · 3 + iy ] = c then return false
Esempio:
return true
© Alberto Montresor
35
© Alberto Montresor
36
x y b x = 0, dalla quale è possibile ricavare b x se sono date
x ottenendo y x
Inviluppo
le
coordinateconvesso
di un punto p = (xp , yp ) che appartiene alla retta: b x = yp x xp y .
Consideriamo uno dei due semipiani, per esempio quello dato dalla disequazione
Un ultimo puzzle
✦
Problema
✦
✦
✦
✦
Si consideri ancora una scacchiera n·n, con n=2k
Trovare un algoritmo che trovi una possibile
ricopertura della scacchiera
✦
284
37
© Alberto Montresor
Inviluppo convesso
?
Un algoritmo banale ma inefficiente
✦
✦
Un poligono può essere rappresentato per mezzo dei suoi spigoli
a)
b) passa per una coppia
c)
d) che divide il piano in due
Si consideri
la retta che
di punti i,j,
semipiani chiusi
Figura 16.1: a) Un poligono non convesso; b) un poligono convesso; c) un insieme di punti; d) il loro
Se tutti i rimanenti n-2 punti stanno dalla stessa parte, allora lo spigolo
inviluppo ✦convesso.
Sij fa parte
dell’inviluppo convesso
✦
i
a) OK
x
xq
x
+ xp
y
⇤ 0.
y
yp
x
+ xp
y
⇤ 0,
Dati n punti p1, . . . , p(yn qnel ypiano,
con
3,pAlgoritmi
più piccolo
(xqn ≥ x
)trovare
eilStrutture
di Datipoligono
p) x
y ⇤ 0.
convesso che li contiene tutti
Pertanto, per ogni punto q che appartiene a tale semipiano, la precedente quantità (yq
yp ) x (xq xp ) y deve essere negativa o nulla, mentre per ogni punto q appartenente
all’altro semipiano la stessa quantità deve essere positiva o nulla. Ne consegue che due punti
q e q stanno dalla stessa parte se le rispettive quantità hanno lo stesso segno, ovvero se il loro
? o nullo.
prodotto è positivo
Consideriamo adesso l’operazione stessaparte(), che prende in input una retta (rappresentata da due punti p1 e p2 ) e due punti p e q, e restituisce true se essi stanno dalla stessa parte
rispetto alla retta (incluso il caso in cui almeno uno dei punti giaccia su di essa), e false se stana)
b)
c)
d)
no da parti opposte rispetto ad essa. I punti sono realizzati come record contenenti due campi
reali
x ea) y.
unanonretta
individuata
dai due
punti c)p1uned
p2 , edidue
punti
p e q, la funzione
Figura
16.1:
Un Dati
poligono
convesso;
b) un poligono
convesso;
insieme
punti;
d) il loro
© Alberto
Montresor
stessaparte
inviluppo
convesso.(p1 , p2 , p, q) verifica in tempo O(1) se le quantità discusse precedentemente hanno
lo
stesso
segno,
cioè se il loro prodotto è non negativo.
Inviluppo
convesso
38
boolean stessaparte(POINT p1 , POINT p2 , POINT p, POINT q)
real dx ⇧ p2 .x p1 .x
real dy ⇧ p2 .y p1 .y
i
real dx1 ⇧ p.x p1 .x
real dy1 ⇧ p.y p1 .y
S ij
real dx2 ⇧ q.x p2 .x
real dyi2 ⇧ q.y p2 .y
ij
return ((dx ·Sdy
dy · dx2 ) ⌅ 0)
j dy · dx1 ) · (dx · dy2
j
1
se i rimanenti n
S ij
© Alberto Montresor
yq
yp
y
b) KO
Figura 16.2:
a) Il segmento
Sij funzione,
è uno spigoloè dell’inviluppo
convesso;scrivere
b) il segmento
Sij non è unoper
Utilizzando
questa
un facile esercizio
una procedura
spigolo
dell’inviluppo
convesso.
viluppo convesso. Infatti, fissati due punti qualsiasi p e p , cioè un segmento S
i
j
x
INVILUPPO CONVESSO (CONVEX HULL)
a) OK
S ij
x
dalla quale segue che
Algoritmi e Strutture di Dati
✦
y
Un poligono nel piano bidimensionale è convesso se ogni segmento di retta che
Se un punto
q = (xdue
) appartiene
a tale semipiano,
allora deve
valere stesso, incluso il
congiunge
del poligono
sta interamente
nel poligono
q , yqpunti
bordo.
✦
Qualsiasi scacchiera di questo tipo con una cella rimossa può essere ricoperta da
triomini a forma di L
284
Definizione
j
b) KO
39
trovare l’ini
j
ij , per vedere
2 punti stanno dalla stessa parte rispetto alla retta che passa per Sij basta
Un algoritmo banale per trovare l’inviluppo convesso si basa sulla seguente caratterizzazione della soluzione. Un poligono può essere rappresentato per mezzo dei suoi spigoli, cioè
dei segmenti di retta che giacciono sul suo bordo. Si consideri allora un generico segmento
Sij che unisce due punti distinti pi e pj , 1 ⇥ i < j ⇥ n, e si consideri la retta che include
Sij . Tale retta divide il piano in due parti (dette semipiani chiusi, ognuno dei quali comprende
anche
laMontresor
retta). Se tutti i rimanenti n 2 punti stanno dalla stessa parte rispetto alla retta che
© Alberto
40
ramente termine, al più, quando si arriva a considerare la retta che passa per p1 e p2 , poiché
tali punti sono
vertici dell’inviluppo convesso di p1 , . . . , pi per ogni i, 2 ⇥ i ⇥ n. Queste
Algoritmo
di Graham
osservazioni suggeriscono il seguente algoritmo informale:
Algoritmo di Graham
✦
Algoritmo di Graham (1972)
✦
✦
S ET graham(POINT p1 , . . . , pn )
{ trova il punto “più basso a destra” e scambialo con p1 }
{ riordina p2 , . . . pn in base all’angolo formato rispetto all’asse orizzontale
quando sono connessi con p1 }
{ elimina gli eventuali punti “allineati” tranne i più lontani da p1 , aggiornando n }
{ inserisci p1 nell’inviluppo “corrente” e , se n ⇤ 2, inserisci anche p2 }
for integer i ⌅ 3 to n do
{ siano ph e pj , con h < j = i 1, gli ultimi due vertici dell’inviluppo “corrente” }
{ scandisci “a ritroso” i punti nell’inviluppo “corrente” ed elimina pj se
stessaparte(pj , ph , p1 , pi ) = false;
termina tale scansione se pj non deve essere eliminato }
{ aggiungi pi all’inviluppo “corrente” }
return inviluppo “corrente”
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
286
Algoritmi e Strutture di Dati
12
8
10
9
13
11
14
5
6
7
4
3
15
2
α
41
1
© Alberto Montresor
288 Figura 16.3: Ordinamento dei punti in base all’angolo
Algoritmo di Graham
Strutture diquando
Dati sono
formatoAlgoritmi
con l’assee orizzontale
connessi al punto p1 .
12
12
tenere fisso uno di tali punti, per
esempio p, ed eseguire stessaparte
(pi , pj , p, q) per n 3
8
8
10
10
volte al variare di q per ciascuno dei rimanenti n 3 punti. Pertanto verificare se un seg9
9
13
mento Sij è uno13spigolo dell’inviluppo
convesso
richiede O(n) tempo.
Poiché ci sono in
5
5
6
14
6
14
11
11
7 ij distinti, si possono individuare
totale n(n 1)/2 segmenti S
tutti gli spigoli dell’inviluppo
7
4
4
3
convesso con complessità O(n3 ).3
15
2
1
16.1.1 Algoritmo di
i = 3Graham
© Alberto Montresor
2
1
i=4
Figura 16.4: Esecuzione dell’algoritmo di Graham fino ad i = 8.
42
for integer i ⌅ 2 to n do
if p[i].y < p[min].y then min ⌅ i
p[1] ⇧ p[min]
{ riordina p[2, . . . n] in base all’angolo formato rispetto all’asse orizzontale
quando sono connessi con p[1] }
{ elimina gli eventuali punti “allineati” tranne i più lontani da p1 , aggiornando n }
integer j ⌅ iif(n ⇤ 2, 2, 1)
for integer i ⌅ 3 to n do
while not stessaparte(p[j], p[j 1], p[1], p[i]) do
j⌅j 1
j ⌅j+1
p[j] ⇧ p[i]
return j
15
L’algoritmo appena
illustrato non è molto efficiente,
perché esamina gli n punti in modo
12
12
8 esame sistematico dei
troppo caotico. Vediamo10come un
10 punti,8 basato su un ordinamento ed
9
un backtrack, permetta
di
progettare
un
algoritmo
più
efficiente,
proposto da Graham (1972).
9
13
13
5
6
14
14 si osservi
Innanzitutto,
che in
minima è un vertice
11quello con ordinata
6 un insieme di punti,
11
5
4
7
4
dell’inviluppo convesso. Inoltre, tracciando una retta orizzontale in tale punto e facendola ruo7
3
3 antiorario si incontrano in sequenza
tare intorno al 15
punto stesso in senso
tutti i rimanenti punti
15
2
2 nella Fig. 16.3, i punti
(uno per volta, se non ci sono due punti “allineati”). Come illustrato
1
si possono rinumerare in base
all’angolo che la retta 1passante per ciascun punto pi e quello
i =5
i=8
di ordinata minima (il punto p1 ) forma con l’asse orizzontale che passa per p1 . Se ci sono più
punti con ordinata minima, allora quelli con ascissa minima e massima, sono vertici dell’in-
La dimostrazione di correttezza dell’algoritmo segue facilmente per induzione su i in acCAPITOLO 16. BACKTRACK
289
cordo alle considerazioni fatte precedentemente. La fase di backtrack avviene all’interno del
ciclo for, dove si eliminano i punti che sono vertici dell’inviluppo convesso di p1 , . . . , pi 1 ,
è invece
n), perché
fase di ordinamento dei punti.
ma cheO(n
non log
lo sono
più perdominata
p1 , . . . , pidalla
.
© Alberto Montresor
Realizzando l’insieme di punti con un vettore p di n elementi di tipo POINT, l’algoritmo di
Esempio
(Algoritmo
Graham).
dell’algoritmo
Grahamp[1
è .illustrata
Graham
può16.3
essere
realizzatodicon
una pila L’esecuzione
simulata direttamente
con ladi
porzione
. . j] del
Algoritmo
di Graham
nella Fig.
16.4,
dove
evidenziati
gli spigoli
vettore,
scambiando
trasono
loro punti
del vettore
stesso.dell’inviluppo “corrente” (in nero), le rette
(tratteggiate), ed i punti che vengono eliminati ad ogni iterazione (con la croce), fino ad i = 8.
Si
noti che
l’aggiunta
del
p8 provoca l’eliminazione di due punti (p7 e p6 ), ma che ogni
integer
graham
(POINT
[ ] punto
p)
punto
è inserito
integer
min ⌅solo
1 una volta ed è eliminato al più una volta.
43
La testa della pila è individuata dall’indice j. La cancellazione di p[j] è effettuata semplicemente decrementando l’indice j all’interno del while. L’indice j è incrementato all’uscita
effettuare
il successivo inserimento di p[i], che avviene scambiando gli elementi p[j] e p[i],
©per
Alberto
Montresor
44
Algoritmo di Graham
✦
Complessità
✦
O(n log n), perché dominato dalla fase di ordinamento degli angoli
© Alberto Montresor
45