CHE COLORE SCEGLI?
Competenze richieste:
È richiesta la conoscenza dei concetti relativi ai Grafi e Teoria dei Grafi. Si consiglia la visione dell’attività “Quanti ponti…Dai attraversiamoli tutti!“
Materiale
Età
Numero di giocatori
Competenze acquisite
Attività che introduce il Minimum Spanning Tree e l’algoritmo di Joseph Kruskal.
INTRODUZIONE:
Ora che abbiamo scoperto che cosa sono i grafi e come possono nascondersi dietro a semplici giochi o rompicapo, utilizziamoli per fare ancora un’ultima attività.
Proiettare la seguente figura e la legenda alla classe o eventualmente riprodurli alla lavagna, utilizzando dei gessetti colorati. Munitevi di un bel sacchetto di caramelle.
Lo scopo del gioco è quello di individuare un insieme di linee tra tutte quelle presenti in figura in modo tale da raggiungere tutti i puntini neri; per fare tale operazione dovete spendere meno caramelle possibili. Tutte le caramelle che spendete nel trovare la soluzione, verranno sottratte dal sacchetto, e quindi poi ne resteranno meno per la classe.
Regola per maggiore chiarezza:
- è consentito cambiare linea/colore solo se siamo in corrispondenza di uno dei puntini neri, se in altre parti della figura vediamo degli incroci di linee (esempio al centro della figura l’incrocio del Giallo, Rosso, Blu), ma senza il puntino nero, in quel determinato caso bisogna obbligatoriamente proseguire con la linea con cui si è arrivati a quel punto, non è possibile cambiarla, perché in quel punto non c’è alcun puntino nero.
| Colore Linea | Costo (Caramelle) |
| Giallo | 1 |
| Rosso | 2 |
| Viola | 3 |
| Verde | 4 |
| Blu | 5 |
Domanda per la classe:
Le figure seguenti, rappresentano tre possibili soluzioni al nostro gioco, qual è il costo di ogni soluzione?
Alcuni esempi:
L’insegnante prima può mostrare e spiegare alla classe i seguenti esempi per facilitare la sfida agli studenti.
Esempio 1 per l’insegnante:
Il Percorso mostrato in figura è una soluzione valida perché considerando un qualsiasi puntino nero, riesco a raggiungere tutti gli altri puntini neri presenti. È formato dalle seguenti linee: Blu, Viola, Blu, Verde, Viola. Il costo di questa soluzione è pari a 5 + 3 + 5 + 4 + 3 = 20 caramelle.
Esempio 2 per l’insegnante:
Il Percorso mostrato in figura non è una soluzione valida, perché non considera tutti i puntini presenti, in questo caso c’è un puntino che non è connesso al resto della figura.
Esempio 3 per l’insegnante:
Il Percorso mostrato in figura non è una soluzione valida, perché ricordandoci la regola vista prima (è possibile cambiare linea/colore solo se ci troviamo su un puntino nero); in questa soluzione, considerando un qualsiasi puntino nero, in nessun modo riesco a raggiungere tutti gli altri puntini neri presenti.
Per aiutare e semplificare la spiegazione, togliendo gli incroci formati dalle linee, la figura di prima noi la possiamo anche vedere nel seguente modo:
Vedendola in questa versione semplificata è facile capire che la soluzione non è valida; in sostanza manca ancora un collegamento che ci permetta di unire le due parti della figura.
Ora tocca a voi, di seguito troviamo tre soluzioni valide, quante caramelle richiedono le seguenti soluzioni?
Quesito 1:
Linee: ?
Costo: ?
Quesito 2:
Linee: ?
Costo: ?
Quesito 3:
Linee: ?
Costo: ?
Soluzione:
Soluzione quesito 1:
Linee: Viola, Verde, Blu, Verde, Giallo
Costo: 3 + 4 + 5 + 4 + 1 = 17 Caramelle
Soluzione quesito 2:
Linee: Viola. Giallo, Viola, Blu, Viola
Costo: 3 + 1 + 3 + 5 + 3 = 15 Caramelle
Soluzione quesito 3:
Linee: Viola, Verde, Rosso, Verde, Giallo
Costo: 3 + 4 + 2 + 4 + 1 = 14 Caramelle
Per ora, contando anche quella spiegata dall’insegnante, abbiamo già visto quattro possibili soluzioni del gioco; di costo rispettivamente 20 – 17 – 15 – 14 caramelle. Potete notare che già l’ultima soluzione vista è molto meno dispendiosa rispetto alla prima.
Domanda per la classe:
Si potrebbe fare ancora di meglio? In modo tale da usare ancora meno caramelle? Provate voi a cercare qualche altra soluzione; quale strategia si potrebbe utilizzare? Quali sono le linee più convenienti da utilizzare per raggiungere tutti i puntini utilizzando meno caramelle possibili?
L’insegnante può lasciare loro del tempo ed eventualmente osservare le soluzioni trovate man mano dagli studenti e a patto che siano corrette e meno costose di quelle già viste prima, può condividerle con la classe.
Al termine, può suggerire alla classe che una buona strategia da seguire, per provare a fare la scelta migliore o una tra le migliori, sarebbe quella di considerare le linee colorate seguendo la legenda, a partire dalle linee che richiedono meno caramelle fino ad arrivare alla soluzione e quindi eventualmente scartare quelle che richiedono parecchie caramelle. Ovvero iniziare a considerare prima tutte le linee di colore giallo, poi quelle di colore rosso, poi viola, poi verde e infine le blu. Ovviamente a patto che la linea in questione sia utile per raggiungere l’obiettivo del gioco.
Spiegazione dettagliata: la strategia vincente potrebbe essere la seguente:
1
Iniziamo a considerare il colore che richiede meno caramelle, ovvero le linee di colore giallo, nella figura proiettata ne troviamo 2 e sono entrambe utili perché collegano tre puntini isolati della figura.
2
Abbiamo finito? No. Passiamo quindi al secondo colore che richiede meno caramelle, ovvero andiamo a considerare le linee di colore rosso; anche in questo caso come nel precedente sono entrambe utili perché collegano 3 puntini isolati della figura.
3
Abbiamo finito? No. (Fate attenzione a non cadere nel tranello, a prima vista sembra di aver finito il nostro gioco perché non vediamo più nessun puntino nero isolato; ma ora ci ritroviamo esattamente come nella situazione dell’esempio 3 spiegato in precedenza dall’insegnante. La figura per ora ancora non è una soluzione valida, manca ancora una linea per renderla tale).
Passiamo quindi al terzo colore meno dispendioso, ovvero andiamo a considerare le linee di colore viola, in questo caso però facciamo attenzione, non tutte e 3 le linee viola sono utili. O meglio, è utile solo una qualsiasi delle tre linee viola presenti. Qualsiasi linea che noi scegliamo ci darà una soluzione equivalente/alternativa alle altre due.
4
Abbiamo finito? Sì il gioco è risolto, le linee scelte ci permettono di raggiungere tutti i puntini neri della figura. Quindi le linee rimanenti non le consideriamo. Le tre soluzioni alternative che abbiamo visto quanto costano?
|
Linee: Rossa, Rossa, Viola, Gialla, Gialla Linee: Rossa, Rossa, Viola, Gialla, Gialla Linee: Gialla, Gialla, Viola, Rossa, Rossa |
Costi: 2 + 2 + 3 + 1 + 1 = 9 Caramelle Costi: 2 + 2 + 3 + 1 + 1 = 9 Caramelle Costi: 1 + 1 + 3 + 2 + 2 = 9 Caramelle |
Domanda per la classe:
Si può fare di meglio? Trovare un modo per risolvere il medesimo gioco e spendere ancora meno caramelle?
No, quella così trovata è la soluzione migliore per il gioco proposto.
Dopo aver capito il meccanismo, riprendete la figura iniziale dell’attività, provate a fare dei cambiamenti, invertire i colori delle linee oppure a cambiare la disposizione delle linee o addirittura create una nuova figura utilizzando la vostra fantasia e ripetete l’intera sfida.
ANCHE QUESTA È INFORMATICA!
Ora che già abbiamo scoperto che cosa sono i Grafi nelle due attività precedenti, sicuramente non vi sorprenderà sapere che l’immagine che l’insegnante vi ha mostrato in questa attività la possiamo trasformare senza troppe difficoltà in un grafo, questa volta però sopra ad ogni arco scriviamo un numero.
Questo numero si riferisce a quante caramelle servono scegliendo quella linea, ovviamente il numero di caramelle è dato in base al colore che la linea aveva nell’attività (dalla legenda: Giallo = 1, Rosso = 2, Viola = 3, Verde = 4, Blu = 5 caramelle).
Svolgendo l’attività si è scoperto che delle volte per risolvere un gioco o un problema può esistere più di una sola possibilità; e abbiamo anche visto che non sono sempre tutte equivalenti tra di loro.
Tante volte, non ci basta trovare una semplice soluzione, magari vogliamo trovare quella migliore tra tutte quelle presenti, in modo tale che nessun’altro possa fare meglio di noi, al massimo ci eguaglierà.
In Informatica il problema di trovare un percorso/soluzione minimo/migliore è chiamato Minimal Spanning Tree.
Esistono molti algoritmi che possono essere applicati sui grafi, come ad esempio quello di trovare la distanza meno costosa/minima tra due punti oppure come nel nostro caso, di trovare il cammino meno costoso/più corto che tocca tutti i punti del grafo.
Tra i vari algoritmi uno efficiente per i problemi di Minimal Spanning Tree è il seguente:
- Si considerino tutti i vertici del grafo isolati, ovvero senza alcun arco che li colleghi.
- Uno alla volta, si aggiungono gli archi seguendo l’ordine crescente del loro costo andando a connettere i vertici isolati o parti non ancora completamente connesse.
Questo algoritmo è chiamato algoritmo di Joseph Kruskal, molto utilizzato in informatica.
Quindi tornando al nostro grafo e applicando su di esso l’algoritmo di Kruskal che abbiamo appena visto, avremo i seguenti passi:
1
Situazione di partenza
Questo è il grafo visto prima, su cui ora applicheremo l’algoritmo di Kruskal.
2
Come richiesto dall’algoritmo il primo passo è quello di andare a isolare tutti i puntini del nostro grafo e quindi rimuovere tutte le linee.
3
Il passo successivo da svolgere è quello di andare a considerare le linee seguendo l’ordine crescente dei numeri di caramelle. Ricorda: meno caramelle si utilizzano per risolvere l’esercizio, più caramelle rimangono per l’intera classe.
4
Iniziamo quindi dalle linee che sottraggono 1 sola caramella dal sacchetto. Ad esempio quella che collega i punti A e F.
5
Ci sono altre linee la cui scelta richiede 1 caramella?
Sì quella che collega i punti D e F.
6
Ci sono altre linee la cui scelta richiede 1 caramella? No.
– L’algoritmo continua –
Passiamo quindi ora alle linee che sottraggono 2 caramelle dal sacchetto.
Ad esempio quella che collega i punti B e E
7
Ci sono altre linee la cui scelta richiede 2 caramelle?
Sì quella che collega i punti C e E.
8
Ci sono altre linee la cui scelta richiede 2 caramelle? No.
– L’algoritmo continua –
Passiamo quindi ora alle linee che sottraggono 3 caramelle dal sacchetto.
Ad esempio quella che collega i punti B e D
9
Soluzione trovata! L’algoritmo di Kruskal termina!
Fine – Quella trovata è una delle possibili soluzioni migliori.
Costo della soluzione trovata da Kruskal:
1 + 1 + 2 + 2 + 3 = 9 Caramelle
Tale soluzione combacia con quella trovata prima nell’attività svolta dagli studenti.
L’algoritmo di Kruskal dà conferma a quello che avevamo visto nell’attività precedente, ovvero per risolvere questo gioco ci servono nel caso migliore 9 caramelle.
Non male, visto che per la soluzione peggiore che risolvere questo gioco (riportata nella seguente immagine) sarebbero servite 21 caramelle.
