Si consiglia la visione delle attività “La stanza cinese“, “Un robot su Marte” e “Introduzione alle funzioni” .

Si consiglia la visione dell’attività del gruppo Bebras “Mi dia il resto!” reperibile qui: Bebras dell’informatica — Quesiti d’esempio

Materiale

46 mattoncini o fogli di carta

almeno 2 fogli di carta aggiuntivi

2 biro

Età

A partire dai 10 anni

Numero di giocatori

11

Competenze acquisite

Obiettivi di apprendimento al termine della classe quinta della scuola primaria

Ambito algoritmi
O-P5-A-1. Utilizzare il ragionamento logico per spiegare il funzionamento di alcuni semplici algoritmi

Ambito algoritmi
O-P5-A-2. Risolvere problemi mediante la loro scomposizione in parti più piccole

Ambito programmazione
O-P5-P-2. Scrivere cicli per ripetere una stessa azione mentre permane una condizione verificabile in modo semplice

Ambito programmazione
O-P5-P-3. Riconoscere che una sequenza di istruzioni può essere considerata come un’unica azione oggetto di ripetizione o selezione

Ambito programmazione
O-P5-P-5. Esplorare l’uso della selezione a due vie per attuare azioni mutuamente esclusive all’interno di programmi semplici

Obiettivi di apprendimento al termine della classe terza della scuola secondaria di primo grado

Ambito programmazione
O-M-P-2. Scrivere programmi che usano l’annidamento di cicli e selezioni

Ambito programmazione
O-M-P-3. Utilizzare in modo semplice meccanismi modulari, come funzioni e procedure

Ambito programmazione
O-M-P-4. Scrivere programmi anche utilizzando variabili di tipo semplice

Attività per introdurre la classe a due tipologie di algoritmi informati: gli algoritmi greedy e l’algoritmo A*.

E’ consigliato svolgere questa attività all’aperto (ad esempio nel cortile della scuola) oppure in palestra.

1. Introdurre la classe all’attività spiegando che le gru sono uccelli migratori dell’Africa e che, in questo contesto, due gru sono appena arrivate in una nuova regione mai visitata prima. Siccome in Africa predomina la savana, le due gru hanno bisogno di trovare un’oasi per potersi abbeverare. Vogliono perciò scoprire la strada più breve per raggiungere l’oasi. Per fortuna, lungo il percorso incontrano altre gru le quali, vivendo in quella regione da più tempo, conoscono il luogo e sanno quindi fare una stima della distanza (in chilometri) dal punto in cui si trovano fino all’oasi (quindi, una stima dei chilometri rimanenti per raggiungere l’oasi).

2. Per questa attività è necessario scegliere 11 studenti della classe, oppure formare più squadre da 11 studenti ognuna. Di questi 11, due corrispondono alle due gru protagoniste della storia, mentre gli altri nove alle gru che incontrano lungo i loro spostamenti e che forniscono loro le stime (quindi, “le gru informate”).

L’attività si divide in due parti, da eseguire nell’ordine in cui vengono presentate.

1. Disporre i bambini secondo lo schema indicato nella pagina successiva. Nella figura, ogni cerchio si chiama nodo e ogni linea tra due nodi viene denominata arco: per comodità, i nodi vengono indicati con una lettera maiuscola (ad esempio A,B…), gli archi con le lettere maiuscole dei due estremi (come AB, BE…). Nel nodo A si trovano dunque i due bambini che impersonificano le gru protagoniste, mentre il nodo K rappresenta l’oasi (la si può indicare con un foglio di carta o altri oggetti). Perciò, i restanti 9 bambini (“le gru informate”) si posizionano in corrispondenza dei nodi B,C,D,E,F,G,H,I,J (le lettere servono solo per indicare dove collocare gli alunni e per facilitare la spiegazione, i bambini non devono ricordare la propria lettera).

2. Ogni bambino ha associato un numero (indicati in rosso nella figura), che deve memorizzare, eventualmente scrivendolo su un foglio. Spiegare che questi numeri indicano la stima della distanza in chilometri dal punto in cui si trova quella specifica gru fino all’oasi. Un’ulteriore osservazione riguarda i numeri associati al nodo A e al nodo K: cosa rappresentano? Spiegare ai bambini che la cifra associata al nodo A indica la stima iniziale delle due gru: secondo loro l’oasi dista 20 Km dal punto di partenza. Invece in K vi è il numero 0 perchè ormai si è arrivati a destinazione, quindi la stima della distanza è nulla (siccome in K non c’è nessun bambino che possa memorizzare quel numero, lo si può scrivere su un foglio lasciato a terra).

3. Spiegare che ogni arco ha un numero a esso associato (sono i numeri di colore nero): questo numero indica la distanza (sempre espressa in chilometri) tra una gru informata e l’altra. Le gru protagoniste infatti, ogni volta che percorrono un tratto di strada (cioè un arco), sono a conoscenza di quanti chilometri abbiano effettivamente percorso. Posizionare quindi, lungo ogni arco, tanti mattoncini (o fogli di carta, a seconda di cosa si preferisca usare) quanto è il numero indicato nella figura sottostante (ad esempio tra A e B dovranno essere disposti 2 mattoncini, tra B e D 4 mattoncini e così via…). Far notare che le stime (i numeri in rosso) potrebbero non essere del tutto precise (cioè corrispondenti alla lunghezza esatta della strada rimanente per l’oasi). Ad esempio, la gru in H dice che secondo lei mancano 2 Km all’oasi, ma in realtà la lunghezza effettiva è di 3 Km (data dall’arco HK); la gru in F è convinta che all’oasi, dal punto in cui si trova, manchino 7 Km, ma se si sommano le distanze delle due possibili strade, ovvero FI+IK=3+5=8 km e FJ+JK=1+6=7 km, si nota che la stima non è sempre del tutto esatta. Tuttavia, questo non è un problema per arrivare alla soluzione corretta del gioco, siccome le stime si avvicinano comunque alla distanza precisa (le gru informate non dicono numeri completamente a caso). Anche la stima iniziale, pari a 20 Km, si scoprirà essere inesatta (del resto, è difficile per le due gru indovinare la distanza corretta, non conoscendo il percorso).

4. Consegnare ai due bambini che rappresentano le gru un foglio e una biro a testa.

Spiegare ai bambini che si trovano nel nodo A che, per arrivare all’oasi tramite la strada più breve, devono seguire questi passi:

1. Siccome da ogni nodo partono non più di due archi, uno dei due bambini procede lungo l’arco alla sua sinistra e interroga il bambino che incontra al nodo successivo, il quale gli risponderà con la propria stima.
2. L’altro bambino fa la medesima cosa, seguendo però l’arco sulla destra.
3. I bambini confrontano poi i due numeri ottenuti e decidono di spostarsi nel nodo in cui si trova il bambino che ha fornito la stima più bassa, riportandone il numero sul foglio; e così via fino ad arrivare all’oasi. (Ovviamente, se da un nodo parte un solo arco, entrambi i bambini devono passare obbligatoriamente per quell’arco e scrivono sul foglio la stima fornita dal bambino incontrato al nodo successivo).
4. Alla fine è richiesto quale percorso è stato scelto.

Confrontare il risultato fornito dai due bambini con la soluzione riportata di seguito.

La stima iniziale, pari a 20, non va considerata, in quanto si parte obbligatoriamente dal punto A. Si sceglie quindi l’arco alla sinistra dei bambini, arrivando in C (siccome la stima in C è pari a 8 e quella in B è 10, quindi 8<10). Seguendo lo stesso principio, da C si sceglie l’arco di destra, spostandosi perciò in F (la stima in F è 7, mentre in G è 10). Da F si prosegue in I (perchè la stima in I è 4, in J è 5) e infine si arriva in K, ovvero all’oasi (siccome da I parte un unico arco diretto in K). La sequenza percorsa è perciò ACFIK. Spiegare agli studenti che la lunghezza effettiva del percorso è data dalla somma dei mattoncini che sono stati superati, quindi AC+CF+FI+IK = 5+1+3+5 = 14 Km.

Fare notare agli studenti che questa non è la migliore soluzione a costo minimo che si possa ottenere (dove con “costo”, in questo esercizio, ci si riferisce al numero dei chilometri): la soluzione ottimale è data dalla sequenza ABEHK, con una lunghezza uguale a AB+BE+EH+HK = 2+4+3+3 = 12 Km.

Tuttavia, applicando il meccanismo spiegato non si potrà mai ricavare questa soluzione in quanto si è obbligati a scegliere C invece che B al primo passo. Si può fare di meglio? Sì, con il nuovo approccio illustrato nella seconda parte del gioco.

A questo punto, il meccanismo che devono adottare i due bambini cambia: bisogna anche tenere conto della distanza già percorsa. Per semplificare, chiamiamo i due bambini Alice e Mattia. Perciò, le istruzioni che devono seguire sono le seguenti:

1. Se vi sono due possibili alternative, Alice sceglie di andare a sinistra ed esegue le seguenti azioni:
   1. somma la lunghezza dell’arco davanti a sè con la lunghezza della strada già percorsa (cioè il numero dei mattoncini già superati)
   2. chiede al bambino che vede al nodo successivo la sua stima per l’oasi.
   3. la risposta a quest’ultima domanda va sommata al calcolo del punto a.

Le somme possono essere effettuate sul foglio che è stato fornito (dove è consigliato anche annotare le lunghezze degli archi attraversati).

2. Mattia esegue le stesse azioni ma seguendo l’arco a destra.
3. In seguito, i due bambini si consultano e scelgono di proseguire lungo l’arco da cui è stata ricavata la somma più bassa.

(Se invece vi fosse un solo arco, entrambi i bambini proseguono lungo quell’arco, sommando la sua lunghezza al numero dei mattoncini già superati e alla stima fornita dal bambino incontrato al nodo successivo).

4. Alla fine, bisogna comunicare quale percorso è stato scelto e la sua lunghezza.

Per facilitare la comprensione, di seguito viene spiegata nel dettaglio la parte iniziale del gioco: Alice e Mattia partono dal nodo A.

1. Alice decide di proseguire lungo l’arco alla sua sinistra (quello che porta al nodo C). A questo punto:
   1. segna sul foglio la lunghezza dell’arco AC, pari a 5; non deve sommare questo numero ai mattoncini già attraversati, in quanto non si è ancora spostata dal nodo iniziale
   2. chiede al bambino che si trova in C quanto dista l’oasi: la risposta è 8
   3. quindi Alice esegue la somma 5+8=13, sempre sul suo foglio
2. Nel frattempo, Mattia sceglie l’arco a destra (che permette di arrivare al nodo B):
   1. scrive perciò sul proprio foglio la lunghezza dell’arco AB (uguale a 2) e, come per Alice, non deve aggiungere il numero dei mattoncini già superati, per lo stesso motivo
   2. domanda al bambino nel nodo B quale sia la sua stima per l’oasi: la risposta è 10
   3. il calcolo da eseguire è dunque 2+10=12
3. Alice e Mattia si consultano e capiscono che l’arco di destra è più conveniente, poichè 12 (il numero ottenuto dal calcolo di Mattia, il quale aveva scelto l’arco di destra) è minore di 13 (la somma ricavata da Alice per l’arco di sinistra). Entrambi si spostano quindi nel nodo B.

Vediamo ancora una parte del procedimento.

4. Alice sceglie l’arco alla sua sinistra (quindi verso il nodo E):
   1. scrive sul foglio che l’arco BE è lungo 4. Questo numero va sommato al numero dei mattoncini già superati, che per il momento è pari a 2 (ovvero alla lunghezza dell’arco AB, l’unico già attraversato), ottenendo quindi 4+2=6.
   2. domanda al bambino in E la sua stima per l’oasi: la risposta è 5
   3. quindi Alice esegue la somma 6+5=11, sempre sul suo foglio
5. Intanto, Mattia opta per l’arco alla sua destra (che porta al nodo D):
   1. scrive sul proprio foglio che la lunghezza dell’arco BD è pari a 4, la quale va sommata al numero dei mattoncini già attraversati (che è uguale a 2, come visto per Alice). Quindi la somma da fare è 4+2=6
   2. chiede al bambino nel nodo D la sua stima per l’oasi, il quale gli risponde che è uguale a 7
   3. Mattia esegue perciò la somma 6+7=13
6. Alice e Mattia si confrontano e scelgono di proseguire lungo l’arco alla loro sinistra, siccome 11 (la somma ottenuta da Alice) è minore di 13 (il totale ricavato da Mattia). Entrambi si spostano quindi nel nodo E.

In seguito si prosegue sempre secondo questo meccanismo (la soluzione è comunque riportata nella sezione successiva). Da tenere presente (per i bambini potrebbe non essere intuitivo) che si deve sommare sempre e solo la nuova stima, mentre le stime dei nodi già attraversati non vengono più considerate.

Verificare se i due bambini (Alice e Mattia), per arrivare alla soluzione, hanno seguito il seguente ragionamento.

• Innanzitutto, nel nodo A non è stato ancora percorso nessun chilometro, quindi l’operazione da fare sarebbe 0+20=20 (questa operazione è superflua siccome, come spiegato prima, nei passi successivi non si terrà conto delle stime precedenti, ma solo delle lunghezze degli archi già percorsi).
• A questo punto, Alice sceglie l’arco alla sua sinistra (verso C) e Mattia quello alla sua destra (verso B) e ognuno di essi chiede la stima al bambino situato nel nodo che raggiungono. Mattia effettua il calcolo 2+10 (dove 2 è la lunghezza dell’arco AB, 10 la stima del bambino in B), che fa 12. Alice invece ottiene 5+8=13. Si prosegue quindi verso B, siccome 12<13.

• Trovandosi in B, Mattia prosegue verso D (effettuando il calcolo 2+4+7=13, dove 2 è la lunghezza dell’arco AB, 4 la lunghezza di BD e 7 la stima del bambino in D), Alice verso E (ricavando 2+4+5=11, con 2 che è la lunghezza di AB, 4 quella di BE, 5 la stima del bambino in E). Poichè 11<13, ci si sposta in E.
• Da E c’è un’unica strada possibile verso H e il calcolo sarebbe: 2+4+3+2= 11 (2 è la lunghezza di AB, 4 di BE, 3 di EH, 2 la stima del bambino in H).
• Arrivati in H, si prosegue verso K (la destinazione finale) lungo l’unico arco presente (effettuando il calcolo 2+4+3+3+0=12, dove 0 è la stima nel nodo K).

La soluzione ottimale è perciò la sequenza ABEHK, che ha una lunghezza effettiva pari a 2+4+3+3=12 Km.

Far notare alla classe che con questo secondo meccanismo, che considera anche le distanze già percorse, si è riusciti ad ottenere la strada più breve per l’oasi, quando col procedimento introdotto nella prima parte risultava impossibile!

Riassumere velocemente i meccanismi dell’attività, scrivendo alla lavagna il testo in corsivo:

1. nella prima parte, ad ogni passo, i due bambini seguono questo ragionamento:

scegli il nodo con la stima più bassa tra quelli che hai davanti

2. nella seconda parte l’approccio cambia: oltre alla stima del nuovo nodo, si deve anche tenere conto della distanza già percorsa. Il calcolo che effettua lo studente ad ogni passo si può quindi esprimere con la seguente formula:

(somma degli archi già percorsi) + la lunghezza dell’arco davanti a sè + la stima del prossimo nodo. Di seguito, confrontandosi con l’altro studente, si sceglie ogni volta il risultato minore.

Spiegare agli studenti che i due meccanismi corrispondono a due tipologie di algoritmi informati (molto importanti nell’ambito dell’Intelligenza Artificiale). A differenza degli algoritmi non informati (come la visita in profondità con backtracking studiata nell’attività “Gli otto polpi”), quelli informati possono trovare una soluzione migliore usando della conoscenza specifica del problema, chiamata funzione di valutazione. In un algoritmo di questo tipo, ogni stato del problema ha una sua funzione di valutazione e, di volta in volta, si seleziona lo stato con la funzione di valutazione minima (nel caso delle gru informate, gli stati corrispondono ai vari nodi in cui si posizionano i bambini). A seconda del meccanismo utilizzato nell’attività, la funzione di valutazione ha una definizione differente (nella pagina successiva sono riportate le spiegazioni nel dettaglio dei due approcci). Una componente della funzione di valutazione è l’euristica: è il costo stimato della soluzione più conveniente che, dal nodo (o stato) in cui ci si trova, conduce all’obiettivo. Spiegare alla classe che, nell’attività, l’euristica corrisponde alla stima della distanza che separa una specifica gru dall’oasi (quindi la stima fornita da ogni gru informata).

Il primo approccio corrisponde a una classe di algoritmi informati detti algoritmi golosi (“greedy” in inglese), il secondo a uno specifico algoritmo informato chiamato A* (si legge “A star”).

1. Gli algoritmi golosi sono chiamati così perchè, ad ogni passo, scelgono sempre lo stato più promettente per raggiungere l’obiettivo (in quanto si pensa che così facendo, si arrivi all’obiettivo più velocemente). Perciò, negli algoritmi golosi, i concetti di funzione valutazione e di euristica coincidono:

funzione di valutazione = euristica

Dunque nell’attività, lo stato più promettente corrisponde al nodo in cui la gru informata fornisce la stima per l’oasi (quindi l’euristica) più bassa. Infatti i due bambini sceglievano sempre di proseguire verso il nodo con la stima inferiore (se avevano due nodi tra cui scegliere). Questo tipo di algoritmi però non è sempre ottimale: abbiamo visto nella prima parte del gioco che questo procedimento obbliga i bambini a percorrere la sequenza ACFIK, invece che la sequenza ABEHK (che risulta essere la strada più breve), proprio perchè gli algoritmi golosi si basano esclusivamente sull’euristica (cioè su quanto un nodo sia promettente per arrivare alla destinazione).

2. L’algoritmo A* è più preciso degli algoritmi golosi, in quanto tiene anche in considerazione il costo (cioè la distanza in chilometri) per raggiungere il nodo in cui ci si trova nello specifico momento, oltre all’euristica. Ovvero:

funzione di valutazione = costo del percorso dal nodo iniziale al nodo attuale + euristica

Quindi, nella seconda parte, si sceglieva il nodo con la funzione di valutazione minima perché i due bambini decidevano di spostarsi nel nodo in cui la somma dei mattoncini già superati e della stima fornita era inferiore. Così facendo, si riusciva ad arrivare all’oasi lungo la strada effettivamente più breve (quindi ABEHK), in quanto la stima che si otteneva ogni volta era più esatta rispetto a quella calcolata nel primo approccio.

Volendo, come attività finale, si può organizzare la classe in gruppi affinchè provino a scrivere le funzioni per i due meccanismi del gioco, se gli studenti conoscono a sufficienza i concetti di funzione, parametro, variabile, istruzione condizionale e ciclo.

La seguente funzione esprime in maniera semplice e intuitiva il primo approccio (anche se alcune istruzioni sono ripetitive):

GOLOSO(S,G) {
  1.posizionati in S
  2.nuova_stima = 0
  3.finché tu e il tuo compagno non siete arrivati in G {
    4.se davanti a te c’è più di un arco {
      5.scegli un arco diverso da quello del tuo compagno
      6.prosegui lungo l’arco scelto
      7.chiedi al bambino nel nodo raggiunto la sua stima per l’oasi
      8.riferisci la stima al tuo compagno
      9.scegliete la stima più bassa
    }
    10.altrimenti {
      11.scegliete entrambi lo stesso arco
      12.proseguite lungo l’arco scelto
      13.chiedete al bambino nel nodo raggiunto la sua stima per l’oasi
    }
    14.segna sul foglio la stima ottenuta
    15.nuova_stima = la stima appena scritta sul foglio
    16.posizionati nel nodo con la stima scelta
  }
  17. comunica la strada percorsa (data dalle lettere dei nodi attraversati)
}

Il parametro S indica il nodo iniziale, lo start (nel gioco, il nodo A), il parametro G invece si riferisce al goal (quindi l’oasi, posizionata in corrispondenza del nodo K). Si utilizza la variabile nuova_stima, che indica la stima ricavata dal bambino appena interrogato nel nuovo nodo (le variabili usate vanno sempre inizializzate a 0 all’inizio di una funzione).

In particolare, si è pensato di usare un’istruzione condizionale per distinguere il caso in cui vi siano due archi tra cui scegliere (quindi un bambino andrà in quello di sinistra, l’altro in quello di destra), dal caso in cui ve ne sia uno solo (dunque tutti e due i bambini proseguono lungo quell’arco). Per rendere l’algoritmo più compatto e meno ripetitivo, si può pensare di non trattare separatamente i due casi, ma di considerare solo quello più generico:

GOLOSO(S,G) {
  1.posizionati in S
  2.nuova_stima = 0
  3.finché tu e il tuo compagno non siete arrivati in G {
    4.scegli un arco tra quelli davanti a te
    5.prosegui lungo l’arco scelto
    6.chiedi al bambino nel nodo raggiunto la sua stima per l’oasi
    7.riferisci la stima al tuo compagno
    8.scegliete la stima più bassa
    9.segna sul foglio la stima ottenuta
    10.nuova_stima = la stima appena scritta sul foglio
    11.posizionati nel nodo con la stima scelta
  }
  12. comunica la strada percorsa (data dalle lettere dei nodi attraversati)
}

Una possibile funzione per il secondo meccanismo può essere la seguente:

A*(S,G) {
  1.posizionati in S
  2.nuova_stima = 0, totale = 0, nuovo_arco = 0
  3.finché tu e il tuo compagno non siete arrivati in G {
    4.se davanti a te c’è più di un arco {
      5.scegli un arco diverso da quello del tuo compagno
      6.prosegui lungo l’arco scelto
      7.conta il numero dei mattoncini lungo l’arco
      8.chiedi al bambino nel nodo raggiunto la sua stima per l’oasi
      9.aggiungi il numero dei mattoncini calcolato all’istruzione 7. e la stima
      ottenuta nell’istruzione 8. a totale
      10.riferisci il valore di totale al tuo compagno
      11.scegliete il valore di totale più basso
    }
    12.altrimenti {
      13.scegliete entrambi lo stesso arco
      14.proseguite lungo l’arco scelto
      15.contate il numero dei mattoncini lungo l’arco
      16.chiedete al bambino nel nodo raggiunto la sua stima per l’oasi
      17.aggiungete il numero dei mattoncini calcolato all’istruzione 15. e la
      stima ottenuta nell'istruzione 16. a totale
    }
    18.segna sul foglio il numero dei mattoncini usato per calcolare totale
    19.nuovo_arco = il numero appena scritto sul foglio
    20.segna sul foglio la stima usata per calcolare totale
    21.nuova_stima = la stima appena scritta sul foglio
    22.sottrai nuova_stima da totale
    23.segna sul foglio il valore di totale
    24.posizionati nel nodo su cui hai calcolato il valore di totale
  }
  25.comunica il valore di totale
}

I parametri sono sempre S e G, mentre, oltre a nuova_stima, sono state aggiunte le variabili totale (per memorizzare il risultato della somma dei mattoncini già percorsi e della nuova stima) e nuovo_arco (che indica il numero dei mattoncini lungo l’arco appena percorso).  Nelle istruzioni 9 e 17 si aggiorna il valore di totale (sommando al suo valore precedente il numero dei mattoncini nell’arco appena percorso e la stima appena ottenuta); i valori di nuovo_arco e nuova_stima vengono aggiornati dopo le istruzioni condizionali siccome, nel caso if, non è detto che il totale appena calcolato sia effettivamente il minimo, va prima confrontato con il compagno. In particolare, all’istruzione 22, è necessario sottrarre nuova_stima da totale, in quanto, ad ogni passo, bisogna considerare soltanto la stima del nuovo bambino, non tutte le precedenti (quindi si rimuove già il valore della stima attuale in preparazione al passo successivo). Concludendo, all’istruzione 25 si ritorna il valore di totale.

Anche in questo caso, possiamo ottenere una funzione più concisa evitando di separare il caso in cui davanti a sè si vedano due archi, da quello in cui se ne veda solo uno. Di seguito è riportata la nuova funzione.

A*(S,G) {
  1.posizionati in S
  2.nuova_stima = 0, totale = 0, nuovo_arco = 0
  3.finché tu e il tuo compagno non siete arrivati in G {
    4.scegli un arco tra quelli davanti a te
    5.prosegui lungo l’arco scelto
    6.conta il numero dei mattoncini lungo l’arco
    7.chiedi al bambino nel nodo raggiunto la sua stima per l’oasi
    8.aggiungi il numero dei mattoncini calcolato all’istruzione 6. e la stima ottenuta nell’istruzione 7. a totale
    9.riferisci il valore di totale al tuo compagno
    10.scegliete il valore di totale più basso
    11.segna sul foglio il numero dei mattoncini usato per calcolare totale
    12.nuovo_arco = il numero appena scritto sul foglio
    13.segna sul foglio la stima usata per calcolare totale
    14.nuova_stima = la stima appena scritta sul foglio
    15.sottrai nuova_stima da totale
    16.segna sul foglio il valore di totale
    17.posizionati nel nodo su cui hai calcolato il valore di totale
  }
  18.comunica il valore di totale
}

Per concludere, come nell’attività degli 8 polpi, si possono porre queste domande alla classe: 

• qual è il problema espresso in questo gioco? Trovare la strada più breve per l’oasi;
• cosa sono gli stati? Sono i nodi in cui vengono posizionati i bambini;
• quali sono le azioni? Spostarsi da un nodo all’altro percorrendo un arco;
• qual è l’obiettivo? Arrivare all’oasi attraverso la strada più breve;
• qual è lo stato iniziale? Il nodo A;
• qual è lo stato obiettivo? Il nodo K;
• qual è la funzione costo? Il costo corrisponde al numero dei chilometri (e quindi dei mattoncini) percorsi.