Laboratorio di Algoritmi e Strutture Dati
Risoluzione di Problemi
con gli algoritmi Ricorsivi
Proff. Francesco Cutugno e Luigi Lamberti
2009-2010
Problem Solving
Sia assegnato un Problema (useremo anche il termine Sistema)
rappresentato da :
• un insieme (finito) di variabili discrete V = {X1, X2, … Xn}
• ciascuna associata ad un dominio D1, D2, … Dn
• un insieme di vincoli (relazioni tra variabili): R = {C1, C2,… Cm}
Lo Stato è una combinazione dei valori delle variabili che
definiscono il problema {Xi = vi  i=1,n} ;
Lo Spazio degli Stati, insieme di tutte le possibili combinazioni
dei suddetti valori, non coincide con il semplice prodotto
cartesiano dei domini, per la presenza dei vincoli.
Lo Stato Iniziale è la condizione di partenza del nostro
problema (in base alla formulazione fissata).
Un’Azione (o mossa legale) è l’assegnazione di un valore ad
una variabile nel rispetto dei vincoli; la modifica di una
variabile, porta il Sistema descritto da uno stato ad un
altro (transizione).
Il numero delle azioni possibili (input del Sistema) è
limitato superiormente dalla cardinalità del prodotto dei
domini.
La Soluzione (o Stato Obiettivo) è una particolare
assegnazione completa delle variabili, soddisfacente
tutti i vincoli; la soluzione può non essere unica.
Un Processo è la sequenza di azioni che conduce il Sistema
da uno stato ad un altro; il Processo risolutivo, sarà la
sequenza di azioni per giungere dallo Stato iniziale allo
Stato Finale atteso.
Diagramma degli Stati
A1
Stato1
A2
A5
A3
Stato2
Stato4
Stato3
A4
A6
A7
L’evoluzione di un Sistema è descritta da un Grafo con un Nodo
per ciascuno stato e un Arco uscente per ogni azione possibile in
quello stato: la destinazione indica la transizione effettuata.
Il diagramma degli stati diventa improponibile al crescere della
complessità del problema.
Il grafo può contenere cicli e può essere complicato dimostrare
che l'algoritmo di ricerca termina.
Albero di Ricerca
Stato1
A1
Stato2
A3
Stato4
A4
Stato5
A2
Stato3
A5
A6
Stato6
Stato7
A7
Stato5
La gestione del problema è rappresentabile anche tramite un
albero (che chiameremo Albero di Ricerca) ove la radice è lo
Stato Iniziale, mentre le eventuali soluzioni sono da ricercarsi
nelle foglie.
Si elimina il problema dei cicli, ma lo stesso nodo potrebbe essere
generato più volte.
Salvare Pecora e Cavoli
Problema: un Agricoltore va al mercato con un Lupo, una Pecora e un
grosso Cavolo; deve attraversare un fiume su una barca tanto
piccola da poter portare un solo oggetto per volta.
Variabili: detto 0 il lato di partenza del Fiume e 1 il lato di arrivo,
avremo 4 variabili, ciascuna con due possibili valori:
A  {0,1}, L  {0,1}, P  {0,1}, C  {0,1}
Vincoli:
Lupo, Pecora e Cavolo non sanno attraversare il fiume da soli;
il Lupo mangia la Pecora, se non c’è l’Agricoltore
la Pecora mangia il Cavolo, se non c’è l’Agricoltore.
Azioni:
l’Agricoltore può attraversare il fiume da solo (A = 1-A),
o con un passeggero A=1-A L=1-L, A=1-A P=1-P, A=1-A C=1-C,
che sia dal suo stesso lato (non tutte le azioni sono legali).
Spazio Stati: Abbiamo 16 stati possibili con le combinazioni ALPC.
0000 è lo stato iniziale; 1111 è lo stato obiettivo (finale);
0110, 0011, 0111, 1001, 1100, 1000 sono stati da evitare;
i restanti sono possibili stati intermedi
AL
A
0 000
AP
1 010
AL
0 010
AP
0 011
1 011
0 100
1 110
AC
A
1 001
1 100
1 000
A
AC
AL
AP
AC
1 101
0 001
A
0 110
0 111
0 101
AP
1 111
Backtracking
Partendo dallo stato raggiunto, ad ogni passo si assegna un
valore ad una variabile, rispettando i vincoli, eseguendo così
una Transizione :
• Se è stato raggiunto lo stato finale, segnaliamo la soluzione.
• Se è possibile avanzare ulteriormente,
ripetiamo l’analisi partendo dallo stato attuale.
• In caso di fallimento (vicolo cieco, violazione dei vincoli,
ritorno ciclico ad un nodo già visitato) si torna indietro.
• Se si ritorna allo stato iniziale senza aver trovato la
soluzione, vuol dire che il problema è irrisolubile
Supponiamo che il problema non preveda possibili percorsi
ciclici, possiamo ipotizzare il seguente algoritmo:
funzione Ricerca ( Stato_Attuale )
{
Risultato = ‘Fallimento’
E = Elenco Azioni possibili secondo i vincoli //
}
mosse legali
per ogni Azione A  E, mentre Risultato = ‘Fallimento’
{
Esegui A
se Nuovo_Stato = Stato_Obiettivo
Risultato = ‘Soluzione’
altrimenti
Risultato = Ricerca ( Nuovo_Stato )
se Risultato = ‘Fallimento’
Annulla esecuzione di A // backtracking
}
restituisci Risultato
Sudoku
Usiamo una griglia quadrata di 81 celle:
9 righe orizzontali per 9 colonne verticali;
inoltre, la griglia è divisa in 9 riquadri 3x3
(gruppi) di 9 celle ciascuno.
Ciascuna riga, colonna e riquadro 3x3
contiene tutti i numeri da 1 a 9.
Pertanto in nessuna riga, colonna o riquadro
può esserci un numero ripetuto.
Nella matrice, ogni cella vale 0 se è libera, da 1 a 9 se occupata.
Chiameremo Gruppi i 9 riquadri 3x3 interni.
Detta (r,c) una cella della Tavola, le coordinate della cella in alto a
sinistra del suo gruppo di appartenenza saranno:
rg = (r / 3) * 3 = r - r % 3
cg = (c / 3) * 3 = c - c % 3
Il gruppo sarà composto dalle nove celle (i,j) con
rg <= i <= rg+2 e cg <= j <= cg+2
/*=======================================================
Esempio base per la risoluzione di un Sudoku.
Manca un’interfaccia utente e
il caricamento dello schema iniziale
--------------------------------------------------------*/
main (void)
{ int Tav [9][9], // Tavola di gioco
Nvuote;
// Numero di caselle vuote nella tavola
IniziaTavola
StampaTavola
(Tav, &Nvuote);
(Tav);
if (Nvuote<1 || !VerificaVincoli(Tav))
printf("\n Il problema e` mal posto ! \n");
else if (! CercaSudoku(Tav,Nvuote) )
printf("\n NON esistono soluzioni ! \n");
else
{ printf("\n Soluzione trovata. \n");
StampaTavola (Tav);
}
getch();
}
/* Esamina la tavola, con ALMENO con una cella vuota, provando a
riempire una qualsiasi cella vuota, ove il valore sia possibile.
OUTPUT: 1 soluzione trovata e copiata sulla Tavola da gioco
0 nessuna soluzione possibile
-----------------------------------------------------------------*/
int CercaSudoku
( int Tav[][9],
// Tavola da esaminare
int Nvuote
// Numero di caselle vuote nella tavola > 0
)
{ int r, c,
// riga e colonna della cella da occupare
N,
// valore da inserire
i, j,
Trovato = 0;
r = -1;
for (i=0 ; i<9 && r == -1 ; i++)
for (j=0 ; j<9 && r == -1 ; j++)
if (Tav[i][j] == 0) {r=i; c=j;}
// cerca una cella vuota
// termina se trova una vuota
for (N=9; N && !Trovato; N--)
if ( VerificaLegalita(Tav, r, c, N) ) // se è possibile inserire N
{ Tav[r][c] = N;
// se era l'ultima casella vuota, la soluzione è stata trovata
Trovato = (Nvuote == 1) ? 1 : CercaSudoku (Tav, Nvuote-1);
// se non è praticabile, annulla la mossa (backtracking)
if (! Trovato) Tav[r][c] = 0;
}
return Trovato;
}
/* Valuta la legalità di un inserimento di un nuovo valore in una
casella vuota, esaminando la riga la colonna e il gruppo.
OUTPUT: 0 non è possibile inserire il valore nella cella
1 il gioco può proseguire alla ricerca di soluzioni
---------------------------------------------------------------*/
int VerificaLegalita
( int Tav[][9],
// Tavola di gioco
int r,
int c,
// riga e colonna della cella da occupare
int N
// valore da inserire
)
{ int i, j,
rg, cg,
// angolo del gruppo di appartenenza
Congrua;
// 0 = tavola inconguente
Congrua = 1;
for (j=0; j<9; j++)
if (Tav[r][j] == N) Congrua = 0;
for (i=0; i<9; i++)
if (Tav[i][c] == N) Congrua = 0;
// esamina la riga
// esamina la colonna
rg = r - r % 3;
// esamina il riquadro
cg = c - c % 3;
for (i=0; i<3; i++)
for (j=0; j<3; j++)
if (Tav[rg+i][cg+j] == N) Congrua = 0;
return Congrua;
}
/*-----------------------------------------------------------Valuta la congruenza dell`intero schema di gioco
OUTPUT: 0 La tabella contiene incongruenze
1 il gioco può proseguire alla ricerca di soluzioni
--------------------------------------------------------------*/
int VerificaVincoli
( int Tav[][9]
// Tavola di gioco
)
{ int r, c, N,
Congrua = 1;
// 0 = tavola inconguente
for (r=0 ; r<9 ; r++)
for (c=0 ; c<9 ; c++)
if ( Tav[r][c] )
// esaminiamo ogni elemento gia` inserito
{ N = Tav[r][c];
Tav[r][c] = 0;
Congrua &= VerificaLegalita (Tav, r, c, N);
Tav[r][c] = N;
}
return Congrua;
}
Problemi di ottimizzazione
Occorre cercare la migliore tra più soluzioni possibili,
secondo una certa metrica. Il fallimento varrà -∞
funzione Ricerca ( Stato_Attuale )
{
E = Elenco Azioni possibili secondo i vincoli
V = elenco dei valori corrispondenti a ciascuna azione
per ogni Azione Ai  E
{ Esegui Ai
se Nuovo_Stato = Soluzione
Vi = Valore della Soluzione
altrimenti
Vi = Ricerca ( Nuovo_Stato )
}
se E ≠ 
altrimenti
}
Risultato = max (Valori)
Risultato = -∞ (Fallimento)
restituisci Risultato
Giochi con Avversario
I Giochi a 2 giocatori “a conoscenza completa ” devono avere le
seguenti caratteristiche:
• Il gioco è definito da una serie di regole
che definiscono le mosse lecite.
• Le mosse sono fatte alternativamente da 2 giocatori A e B.
• Ogni giocatore ha informazioni complete sullo stato
del gioco in ogni istante.
• Non c’è intervento del caso (sistema deterministico).
• Uno Stato Terminale rappresenta una situazione di
Vittoria, Sconfitta o Pareggio per un giocatore.
Diremo che un gioco è Equo, quando nessuno dei due giocatori
può vincere se l’avversario gioca “al meglio ”.
Procedura Neg-Max
Usiamo il backtracking ricorsivo per trovare la mossa migliore;
ad ogni passo verrà scelta la mossa che è più conveniente per A o per B.
La funzione di valutazione capovolge il parere dell’avversario, negando il
risultato restituito dalla successiva istanza ricorsiva.
Stabilito un valore positivo per la vittoria, uno negativo per la sconfitta
e Zero per il pareggio:
•
•
•
A esamina lo stato attuale del gioco e cataloga le possibili mosse.
A esegue ad una ad una le mosse possibili.
•
Se la mossa è terminale, assegna il valore (es. +1, -1,
0).
•
Se la mossa non è terminale, consegna lo stato del gioco a B
chiedendo il suo parere (ricorsione).
•
B risponderà secondo il suo punto di vista:
ad esempio restituirà +1 se è certo di vincere.
•
A trasforma il parere di B, assumendo -1 per quella mossa.
A conclude l’analisi indicando come miglior mossa quella che ha il
valore più alto dal suo punto di vista.
Tic-Tac-Toe
Ciascuno dei due giocatori inserisce a turno una
pedina del proprio colore sul tavolo di gioco, fino
a formare un Tris, ovvero una fila di tre pedine
dello stesso colore, in orizzontale, in verticale o
in diagonale: vince chi realizza per primo un tris;
riempito il campo senza tris, la partita è Pari.
Struttura Dati:
Tavola[10]
scacchiera del gioco; sono usate le caselle da [1] a [9]
ogni casella vale 0 se vuota, 1 o 2 se occupata.
Nvuote
numero delle caselle ancora vuote a disposizione
Who
giocatore che deve muovere: 1 o 2
DoveGioco
casella della prossima mossa da eseguire
Finito
0 = gioco in corso
1 = gioco finito (vinto 1)
2 = gioco finito (vinto 2)
3 = gioco finito in pareggio
27 = gioco finito per abbandono
/*====================================================================
Esempio base per il gioco del Tris tra due giocatori scelti tra:
-) Umano ( tramite keyboard )
-) PC
( tramite sub di valutazione mossa ).
Manca un’interfaccia utente e la possibilità di scegliere chi inizia.
---------------------------------------------------------------------*/
main (void)
{ int Tavola[10],
// scacchiera di gioco
Nvuote,
// numero delle caselle vuote (con valore 0)
Who,
// giocatore che deve muovere: 1 o 2
DoveGioco,
// mossa da fare da parte di Who
i,
// indice generico
Finito;
// 0 = gioco in corso
// 1,2 = gioco finito (vinto 1 o 2)
// 3 = gioco finito in pareggio
// 27= gioco finito per abbandono
for (Nvuote = i= 9; i; Tavola[i--]=0 ); // pulizia scacchiera
StampaTavola (Tavola);
// visualizza la tavola
Who = 1;
// muove per primo il PC assegnato a 1
Finito = 0;
while (! Finito)
{
if (Who == 1) // mossa decisa dalla funzione di valutazione
{ ValutaMossa (Tavola, Nvuote, Who, &DoveGioco);
}
else // Who == 2: mossa del giocatore umano tramite keyboard
else
// Who == 2: mossa del giocatore umano tramite keyboard
{ DoveGioco = 0;
do
{ i = getch();
if (i == 27)
// se si vuole abbandonare il gioco
Finito = 27;
else if (i>=49 && i<=57 && Tavola[i-48]==0) //solo case vuote
DoveGioco = i-48;
}
while (!DoveGioco && !Finito);
}
if (!Finito)
{ Tavola[DoveGioco] = Who;
if ( VerificaTris(Tavola) )
Finito = Who;
else if (Nvuote == 1)
Finito = 3;
else
{ Who = 3 - Who; Nvuote --;
}
}
StampaTavola
(Tavola);
// se non c'è stato un abbandono
// occupa la casella
// mossa vincente
// se unica vuota, pareggio
// passa all'avversario
// Visualizza il campo di gioco
}
while (!Finito);
printf ("Partita terminata"); getch();
}
/*==========================================================
Verifica se esiste un tris qualsiasi sulla tavola di gioco
Considerando i valori 1 e 2 in binario, 10 e 01, l’AND di
tre caselle è diverso da zero solo se sono uguali.
Output :
1 l'ultima mossa effettuata ha prodotto un Tris
0 non esistono tris sulla tavola
---------------------------------------------------------*/
int VerificaTris
( int *Tav
// scacchiera di gioco
)
{ int Fatto;
Fatto = ( Tav[1]
Tav[4]
Tav[7]
Tav[1]
Tav[2]
Tav[3]
Tav[1]
Tav[7]
return Fatto;
}
&
&
&
&
&
&
&
&
Tav[2]
Tav[5]
Tav[8]
Tav[4]
Tav[5]
Tav[6]
Tav[5]
Tav[5]
&
&
&
&
&
&
&
&
Tav[3]
Tav[6]
Tav[9]
Tav[7]
Tav[8]
Tav[9]
Tav[9]
Tav[3]
||
||
||
||
||
||
||
);
//
//
//
//
//
//
//
//
1ø rigo
2ø rigo
3ø rigo
1ø colonna
2ø colonna
3ø colonna
diagonale /
diagonale \
/* Valutazione della mossa migliore in un dato stato del gioco.
si ferma nell'analisi quando trova una mossa vincente.
Output: valore della scacchiera vista da Who che deve muovere
-1 sconfitta, 0 pareggio, +1 vittoria.
*/
int ValutaMossa
( int *Tav,
// scacchiera di gioco
int Nvuote,
// numero delle caselle vuote (valore 0)
int Who,
// giocatore che deve muovere: 1 o 2
int *DoveMeglio
// casella della mossa migliore
)
{ int i,
// indice sulle caselle della scacchiera
Dove,
// miglior contromossa dell'avversario
Vale,
// valore della contromossa
MaxVale;
// valore della miglior mossa possibile
for (MaxVale = -INFINITO, i=9; i && MaxVale<1; i--)
if (Tav[i]==0)
// se la casella è vuota
{ Tav[i] = Who;
// occupa la casella
if ( VerificaTris(Tav) )
// se si è creato un tris
Vale = +1;
// mossa vincente
else if (Nvuote == 1)
// se unica vuota, pareggio
Vale = 0;
else
// chiede il parere dell'avversario
Vale = -ValutaMossa (Tav, Nvuote-1, 3-Who, &Dove);
if (Vale > MaxVale)
{ MaxVale = Vale; *DoveMeglio = i;}
Tav[i] = 0;
// libera la casella
}
return MaxVale;
}
Hexagon 19
Sia assegnata una scacchiera con 19
caselle esagonali (inizialmente vuote).
Due giocatori (Nero e Bianco)
collocano alternativamente una pedina
in una casella vuota; il primo che è
costretto ad occupare due caselle
adiacenti, ha perso la partita.
1. Costruire una procedura che valuti la mossa migliore da compiere
in qualsiasi situazione di gioco (considerando che anche l’avversario
giocherà sempre “al meglio”), utilizzando il Backtracking ricorsivo.
2. Utilizzare la suddetta procedura per stabilire se si può sicuramente
vincere giocando per primi o per secondi (un pareggio è impossibile).
3. Consentire ad un umano di giocare contro il computer,
sia pure con un’interfaccia spartana.
Bibliografia Web
http://it.wikipedia.org/wiki/Ricorsione
http://www.cad.polito.it/~bernardi/
corsi/APA_IVREA/APA2/W4/minmax.pdf
http://www.di.unipi.it/~simi/
AI/SI2007/Lucidi/games.pdf
http://www.cs.unibo.it/~cianca/
wwwpages/chesssite/tozzi.pdf