OMBRELLONI E SECCHIELLI
Competenze richieste:
Si consiglia la visione delle attività “La parata dei pinguini” e “L’arca dei vincoli“.
Si consiglia la visione dell’attività del gruppo Bebras “Mi dia il resto!” reperibile qui: Bebras dell’informatica — Quesiti d’esempio
Materiale
Età
Numero di giocatori
Competenze acquisite
Attività relativa ai problemi di soddisfacimento dei vincoli per studenti dai 10 anni in su.
OMBRELLONI E SECCHIELLI
PREPARAZIONE:
Consegnate ad ogni studente una copia della scheda sugli ombrelloni e i secchielli.
DESCRIZIONE DELL’ATTIVITÀ – ISTRUZIONI:
- Spiegare alla classe l’obiettivo del gioco: posizionare sulla griglia 18 secchielli, seguendo delle regole specifiche.
- Scrivere quindi alla lavagna le seguenti regole, in modo che siano chiare alla classe e i bambini possano consultarle al momento del bisogno:
– ogni ombrellone deve avere vicino (in orizzontale o in verticale) il suo secchiello
– i secchielli non possono essere posizionati vicini (in orizzontale, in verticale e nemmeno in diagonale).
Come aiuto, ai lati della griglia sono indicati dei numeri: indicano quanti secchielli bisogna inserire in quella specifica riga o colonna (ad esempio, nella prima riga partendo dall’alto è segnato un 2, perciò in quella riga si dovranno posizionare due secchielli, rispettando le regole elencate prima).
La soluzione è una sola (ed è mostrata nella scheda successiva a quella da consegnare ai bambini).
- Lasciare un quarto d’ora alla classe per provare a risolvere il rompicapo.
- Allo scadere del tempo, proiettare la soluzione in modo che gli alunni possano valutare se hanno risolto correttamente il gioco o se hanno commesso degli errori.
- Al termine, avviare la discussione finale.
RISOLUZIONE DEL GIOCO:
Spiegare alla classe che esistono 3 meccanismi principali per risolvere il rompicapo, elencati di seguito, e chiedere quali siano stati sfruttati completamente o anche solo in parte.
Un primo approccio, molto semplice, è quello di posizionare in maniera casuale tutti e 18 i secchielli, preoccupandosi poi di controllare se le regole del gioco sono state rispettate. E’ intuibile che questo meccanismo sia inefficiente (e nessun bambino dovrebbe averlo usato), siccome è molto difficile “indovinare” la corretta disposizione di ben 18 secchielli entro pochi tentativi.
Nel secondo criterio, ogni volta che si posiziona un secchiello, si controlla se esso rispetta le regole:
- se le rispetta, si può proseguire e sistemare un altro secchiello
- altrimenti: si prova a sistemare quel secchiello in un’altra casella:
- se nella nuova casella rispetta le regole, si può andare avanti posizionando un nuovo secchiello
- altrimenti, se non si riesce a sistemare quel secchiello in nessun’altra posizione: si prova a spostare il secchiello ancora precedente e così via….
Si tratta di un approccio sicuramente più efficiente del primo, in quanto permette di risparmiare molti tentativi inutili: ogni volta che si sceglie dove mettere un secchiello si controlla se le regole del gioco sono state mantenute, in caso contrario si provvede subito a risolvere il problema.
Il terzo meccanismo riprende il secondo, ma con l’aggiunta di alcuni “accorgimenti”, o “trucchetti”. Coinvolgere la classe chiedendo quali dei seguenti accorgimenti siano stati utilizzati:
1
Innanzitutto, ancora prima di provare a posizionare dei secchielli, si possono scartare tutte le caselle di una riga o di una colonna a cui è associato il numero 0: sicuramente in nessuna di quelle caselle ci sarà un secchiello. Nella figura sopra, le caselle scartate sono colorate di rosso chiaro.
2
Ricordando la prima regola (ogni ombrellone deve avere vicino, in orizzontale o in verticale, il suo secchiello), si possono scartare le caselle che si trovano “in diagonale” tra gli ombrelloni, in quanto nessun ombrellone avrà il suo secchiello su una casella in diagonale, ma solo in orizzontale o in verticale. Inoltre, si possono anche eliminare le caselle che non si trovano vicino a nessun ombrellone, come mostrato nella figura sopra.
3
Combinando le caselle eliminate nelle due immagini precedenti, si ottiene quanto mostrato nella figura sopra.
Quindi, abbiamo scartato numerose caselle ancora prima di posizionare i secchielli!
4
In aggiunta, quando è stata completata una riga o una colonna (cioè sono stati posizionati tanti secchielli quanto è il numero indicato), se vi sono rimaste delle caselle vuote, queste possono essere tranquillamente scartate. Partendo dalla situazione dell’ultima immagine, possiamo inserire un secchiello con certezza nella penultima riga (partendo dall’alto), quinta colonna (partendo da sinistra). Infatti, l’ombrellone alla sua destra ha un’unica casella disponibile per poter posizionare il suo secchiello. Di conseguenza, siccome quella riga ha associato il numero 1 ed è già stato collocato un secchiello, le altre caselle non ancora occupate possono essere eliminate.
5
Basandosi sulla seconda regola (i secchielli non possono essere posizionati vicini, in orizzontale, in verticale e nemmeno in diagonale), ogni volta che si colloca un secchiello in una certa casella, si possono di conseguenza eliminare le caselle vicine (orizzontalmente, verticalmente e diagonalmente). Proseguendo dalla situazione della figura precedente, si nota che l’ombrellone nella terzultima riga (dall’alto) e settima colonna (da sinistra), ha un’unica casella disponibile per il secchiello, alla riga superiore. Per questo motivo, la casella colorata in rosso scuro (sopra il secchiello) può essere scartata a priori.
6
Inoltre, dopo aver associato un secchiello a un ombrellone, si possono rimuovere le caselle vuote attorno a quest’ultimo (sia in orizzontale che in verticale, sfruttando quindi la prima regola del gioco), facendo attenzione che non vi siano altri ombrelloni vicini che potrebbero avere un secchiello in una di quelle caselle. Nell’esempio sopra riportato, dopo aver posizionato i 3 secchielli nell’ultima riga (si va sul sicuro siccome vi sono solo tre caselle libere e il numero indicato per quella riga è proprio 3), si può eliminare la casella (colorata di rosso scuro) sopra all’ombrellone sulla sinistra (penultima riga dall’alto, terza colonna da sinistra), siccome non vi sono altri ombrelloni nelle prossimità che potrebbero avere un secchiello proprio in quella casella.
7
Infine, si può sfruttare questo criterio molto intuitivo: sicuramente diventa più semplice risolvere il rompicapo se si dispongono prima i secchielli degli ombrelloni con meno caselle libere attorno (altrimenti la probabilità di sbagliare aumenta). Nella figura sopra, si riprende lo stato precedente e in violetto sono evidenziate tutte le caselle in cui vi sono sicuramente dei secchielli, poichè i relativi ombrelloni hanno vicino un’unica casella libera.
In seguito, se nessun altro secchiello ha solo una casella in cui essere posizionato, ci si focalizzerà su quelli che ne hanno due e così di seguito.
Si può quindi concludere che, grazie a questi “trucchetti”, si riesce a risolvere il rompicapo molto più velocemente, avendo numerosi tentativi in meno da provare!
DISCUSSIONE:
Spiegare alla classe cos’è un problema di soddisfacimento dei vincoli (detto anche CSP, dall’inglese “Constraint Satisfaction Problem”): si tratta di un problema in cui sono esplicitamente rappresentati dei vincoli e questi ultimi devono essere sempre rispettati.
In particolare, un CSP ha 3 componenti:
- un insieme di variabili
- un insieme di domini (uno per ogni variabile), dove un dominio comprende un certo numero di valori possibili
- un insieme di vincoli.
Quindi, lo scopo del CSP è fare degli assegnamenti: ad ogni variabile va assegnato un valore appartenente al suo dominio (e si parla in questo caso di un assegnamento completo), facendo attenzione a rispettare i vincoli imposti dal problema (ottenendo un assegnamento consistente). Se valgono entrambi i tipi di assegnamento, si ottiene una soluzione per il CSP.
Per quanto riguarda il nostro gioco, possiamo chiamare vincoli le due regole scritte alla lavagna (e anche la regola che afferma che in ogni riga e in ogni colonna ci devono essere tanti secchielli quanto è il numero indicato). Le variabili del problema sono i 18 secchielli e i loro domini sono tutte le caselle della griglia in cui possono essere posizionati i secchielli (quindi tutte le caselle dove non si trova già un ombrellone o un altro secchiello). Un assegnamento, perciò, consiste nell’associare ad ogni secchiello una casella della griglia. Si arriva alla soluzione quando tutti i 18 secchielli sono stati assegnati ad una casella nel rispetto dei vincoli.
Esporre quindi alla classe i seguenti tre algoritmi per la risoluzione di un CSP, che corrispondono ai tre meccanismi elencati nella parte di risoluzione del gioco.
Primo algoritmo
L’algoritmo per il primo meccanismo è detto Generate and Test ed è un algoritmo di forza bruta (che significa semplicemente che si provano tutte le soluzioni in maniera casuale, fino a quando non si arriva alla soluzione corretta).
Secondo algoritmo
Il secondo meccanismo corrisponde alla visita in profondità con backtracking (già approfondita nell’attività “Gli otto polpi”). Si tratta di un meccanismo migliore del Generate And Test, siccome, a differenza di quest’ultimo, i vincoli vengono verificati ogni volta che si posiziona un secchiello, non dopo averli sistemati tutti e 18.
Terzo algoritmo
Il terzo approccio (che è poi quello maggiormente usato nei CSP e che permette di risolvere al meglio il gioco), si basa sulla visita in profondità con backtracking con l’inserimento di una particolare fase di inferenza, detta propagazione dei vincoli.
Il termine “inferenza” significa, genericamente, “ricavare una conclusione da un insieme di dati” ed è un concetto sfruttato non solo nell’Intelligenza Artificiale, ma anche in altre discipline come la Logica e la Statistica.
Nei CSP si fa inferenza tramite la propagazione dei vincoli: ovvero, si sfruttano i vincoli del problema per ridurre il numero dei valori possibili che possono essere assegnati ad una variabile, la quale a sua volta può ridurre i valori possibili di un’altra variabile e così di seguito. Nel gioco degli ombrelloni e dei secchielli la propagazione dei vincoli si può utilizzare in diverse occasioni, che corrispondono agli accorgimenti 1, 2 e 3 visti nella sezione di risoluzione del gioco.
Da notare che, rispetto all’algoritmo del Generate and Test e alla visita in profondità con backtracking (senza inferenza), con questi accorgimenti si sfruttano i vincoli prima di posizionare i secchielli; negli altri due algoritmi invece, si controllava se i vincoli erano rispettati dopo aver posizionato i secchielli. Chiedere alla classe quale dei due ragionamenti è il più vantaggioso e perchè. La risposta è che, analizzando i vincoli prima degli assegnamenti (ovvero prima di posizionare un secchiello in una casella), si possono scartare già molti valori (quindi molte caselle), evitando assegnamenti inutili e magari anche sbagliati, perciò l’approccio con la propagazione dei vincoli è più efficiente.
Per l’inferenza si può sfruttare l’approccio del forward checking: quando si fa una scelta di un assegnamento di un valore a una variabile, si propaga questa scelta alle variabili immediatamente vicine. Nel nostro gioco, il forward checking si applica nei trucchetti numero 4 e numero 5.
Si può fare un ultimo confronto con gli studenti riguardo alle euristiche di scelta: si tratta di scelte (di variabili o valori su cui focalizzarsi) che vengono effettuate durante la visita in profondità con backtracking per arrivare prima alla soluzione. Tra le tante euristiche di scelta, una che può risultare utile al nostro gioco è l’euristica MRV (dall’inglese “Minimum Remaining Values”): consiste nel preferire le variabili (quindi i secchielli) con il minor numero di valori (in termini di caselle disponibili) rimasti nel proprio dominio (ovvero non ancora scartate). L’euristica MRV viene applicata nell’accorgimento numero 6, infatti ci si concentra prima sui secchielli che hanno un’unica casella disponibile, poi si passerà a quelli con due caselle disponibili e così di seguito.
Come ultima osservazione è importante ricordare che l’inferenza e le euristiche di scelta si applicano alla visita in profondità con backtracking: quindi, se si raggiunge un punto in cui non si sa dove posizionare un secchiello per un certo ombrellone, si ritorna all’ombrellone precedente e si prova a spostare il relativo secchiello in un’altra locazione e così via.
