 Travelling Scratch
Come costruire un’interfaccia grafica per studiare il problema del commesso
viaggiatore usando Scratch.
Lo scopo dell’esercitazione e’ quella di usare scratch per costruire un’interfaccia
grafica per studiare il problema del commesso viaggiatore (TSP).
Il testo dell’esercitazione e’ disponibile on-line all’indirizzo
http://www.disi.unige.it/person/DelzannoG/ORIENTAMENTO/Esercitazione.htm
Gli appunti sul problema TSP sono all’indirizzo: http://www.disi.unige.it/person/DelzannoG/ORIENTAMENTO/tsp_appunti.ppt
L’ambiente Scratch
Scratch e’ un ambiente didattico per imparare i concetti di base della
programmazione sviluppato al MIT (Massachusets Institute of Technology).
Scratch si puo’ scaricare ed installare gratuitamente dal
sito http://scratch.mit.edu/.
L’ambiente permette anche ai neofiti di costruire
programmi interattivi (es. videogame e storie) divertendosi ed imparando in
modo naturale concetti complicati (es. uso di variabili, costrutti iterativi
e condizionali, comunicazione tra personaggi, temporizzazione e movimento
degli oggetti). L’interfaccia ha varie finestre per definire
contemporaneamente immagini, scenografia, comportamento e suoni del vostro
videogame.
La prima finestra
a sinistra contiene tutte le operazioni disponibili per movimento,
controllo, suoni, ecc. La finestra in mezzo viene usata per definire il
comportamento (tramite script) dei personaggi (chiamati sprite). Per ogni
sprite si possono inserite diversi programmi (script) che specificano la
reazione a determinati eventi (es. cliccare la bandiera verde per iniziare il
gioco, cliccare un personaggio, ricevere un messaggio, avvicinarsi ad un
altro sprite, ecc). Gli script
si costruiscono usando dei blocchetti come nei Lego:
La forma e il colore dei blocchi dipende dal tipo di
operazione (es. blu per il movimento, oro
per il controllo, lilla
per l’aspetto, fucsia per il
suono).
La terza finestra definisce infine lo scenario grafico in
cui gli sprite si muovono ed interagiscono.
Per aprire scratch selezionate l’icona con il gattino sul
desktop … e iniziate a divertirvi!
Esercitazione: Costruire una GUI per TSP in
Scratch
Il nostro scopo e’ usare Scratch per poter studiare il problema TSP tramite una simulazione
all’elaborazione (che come abbiamo visto e’ indispensabile per istanze con
molti nodi del problema).
Nel nostro simulatore l’utente deve avere la possibilita’
di disporre i nodi a piacimento in uno spazio 2D. Usiamo quindi la distanza
tra due nodi come peso per il corrispondente arco (consideriamo quindi un
grafo completo rappresentabile in un piano).
Una volta definito il grafo, l’utente posiziona il
commesso viaggiatore (uno sprite Scratch) su uno dei nodi (il nodo iniziale).
Cliccando su un nodo N (la prossima citta’ da visitare) il
commesso si deve muovere automaticamente verso N se N risulta non essere
stato ancora visitato.
Durante la visita del grafo bisogna calcolare la lunghezza
del percorso.
Per facilitare il compito andiamo per gradi:
1.
Definire lo scenario
2.
Muovere il commesso viaggiatore verso un nodo
3.
Marcare i nodi visitati
4.
Mostrare la traccia del percorso
5.
Calcolare la lunghezza del percorso
In
un secondo tempo, dopo aver “testato” la nostra applicazione, aggiungeremo
altre feature:
1.
Memorizzare la lunghezza di un percorso
2.
Calcolare la lunghezza minima dei percorsi
3.
Inserire piu percorsi
Infine
proveremo (se rimane tempo) ad implementare una soluzione euristica basata
sull’algoritmo Nearest Neighbour.
Un piccolo aiuto
All’URL http://www.disi.unige.it/person/DelzannoG/ORIENTAMENTO/puzzle_tsp.sb
troverete un template per la prima parte dell’esercitazione.
Per ogni sprite troverete i blocchi dei corrispondenti script ma … in forma
di puzzle!
Definire lo scenario
Innanzitutto dobbiamo costruire lo scenario per la nostra simulazione di
TSP.
Abbiamo bisogno di uno sprite
che rappresenta il commesso viaggiatore e di un certo numero di sprite che
rappresentano le citta’ da visitare. Scegliete i costumi a piacere sia per il
commesso che per i nodi.
Ad esempio usando  per
il commesso viaggiatore e  ,  …
per i nodi
E gli archi? E le distanze?
In realta’ lo schermo di lavoro di Scratch puo’ essere visto come un piano 2D
(da x: [-240,+240], y:[-180,+180]). Possiamo usare la distanza tra i punti
(vi ricordate come e’ definita?) come peso per un arco.
Usando un costume predefinito possiamo chiarire meglio la geometria dello
schermo di Scratch.
Ogni sprite ha quindi una posizione rispetto al centro dello schermo.
La distanza da uno sprite A ad uno sprite B si puo calcolare automaticamente
usando il blocco  dal menu dei sensori (usato nella
finestra dei comandi di A bisogna specificare il nome di B).
Implicitamente quindi abbiamo definito un grafo completo!
I pesi degli archi sono rappresentati dalla distanze tra gli sprite numerati.
Muovere il commesso viaggiatore verso un nodo
Proviamo ora a muovere il commesso viaggiatore verso un
nodo.
Per fare questo possiamo usare il blocco  inserendo le coordinate di un
nodo.
Per
visualizzare la traccia durante il movimento possiamo usare uno sprite come
una penna che disegna sullo schermo.
Provate la sequenza  e 
Con opportuna configurazione della penna otterrette questo effetto:
Il gatto si trova ora sul nodo in posizione (0,0).
Interagire con l’utente
Per poter animare la nostra applicazione abbiamo bisogno
di specificare degli script che determinano il comportamento del
gatto-commesso e dei nodi.
Vogliamo associare il movimento del commesso (il gatto)
con l’evento “click sul nodo da visitare”.
Per poter eseguire questo task occorre che il nodo invii
un messaggio al gatto quando cliccato.
Il gatto deve anche ricevere le coordinate del punto verso cui muoversi.
Abbiamo bisogno dei seguenti tipi di script per il gatto e
per il nodo.
Script di inizializzazione attivati dalla Green
Flag  .
Sono eseguiti una sola volta quando parte la simulazione.
Servono per
inizializzare i parametri del gioco (posizioni, effetti grafici,
variabili).
Script per reagire ad eventi quali
·
click su uno sprite 
·
la ricezione di un messaggio 
Sono eseguiti quando si verifica il corrispondente evento.
Uno script puo’ inviare messaggi agli altri script usando
il comando  .
Inoltre abbiamo bisogno di contenitori (variabili) per
comunicare al commesso la le coordinate dove muoversi.
I contenitori si definiscono usando  dal menu Variabili.
Le nuove variabili create sono mostrate come segue  (questa ha nome “variabile”)
X ed Y devono essere visibili a tutti gli sprite.
Siamo pronti per rendere dinamico il gioco.
Quando lo sprite nodo viene iccato (blocco ):
- mette
le coordinate correnti (
e  )
nelle variabili X e Y;
- invia un messaggio “MUOVI” al
gatto e aspetta che il gatto completi lo spostamento (blocco
 ).
Quando il gatto riceve il messaggio “MUOVI” (blocco ):
- recupera
le coordinate del nodo (i
contenitori x e y) e le utilizza per muoversi verso il nodo (blocco
 )
Rimangono ancora alcuni problemi da risolvere.
Marcare i nodi visitati
Innanzitutto vogliamo che il gatto si sposti su un nodo
solo se non e’ stato gia’ visitato.
I nodi quindi devono avere due stati “visitato/non
visitato”.
Aggiungiamo allora un’altra variabile “visitato” (con valore
0/1) allo sprite nodo.
Aggiungiamo inoltre uno sprite di inzializzazione (blocco )
per inizializzare la variabile a 0 (blocco  ).
Nello sprite che invia i messaggi al gatto-commesso
dobbiamo allora inviare il messaggio “MUOVI” solo se la variabile ha valore 0
(il nodo non e’ visitato).
Per fare questo controllo possiamo usare il costrutto
condizionale  .
Nella condizione possiamo inserire un operatore di
confronto  tra la variabile visitato e il valore
0 (non visitato).
Se la condizione non e’ soddisfatta (il nodo e’ gia
visitato) il gatto-viaggiatore non deve muoversi.
Potremmo anche inviare un messaggio usando il costrutto 
E nel ramo else inserire il comando  che visualizza un messaggio (ad
esempio “Ho gia’ visitato il nodo!”).
Visualizzare il percorso
Vogliamo
ora visualizzare il percorso del commesso nel grafo cioe’ la traccia lasciata
dal gatto durante la visita. Per ottenere questo effetto possiamo usare la
“penna”.
La
configurazione iniziale della penna (spessore/colore) va specificata in uno
script di inizializzazione (blocco ) per
attivare la penna usiamo il comando
visto precedentemente.
Calcolare la lunghezza del percorso
Per poter calcolare la lunghezza del cammino percorso dal commesso
viaggiatore possiamo introdurre un altro contenitore (variabile) “LUNGHEZZA”.
Ad ogni spostamento possiamo usareil blocco e gli operatori aritmetici (es
sottrazione  e somma) per aggiornare la lunghezza
con la distanza con l’ultimo nodo visitato (es. usando  nello script dei nodi).
Se siete arrivati fino a questo punto…
Siete pronti ora a testare la nostra applicazione!
Duplicate lo sprite “nodo” (cambiando il costume numerando i nodi) in modo
che tutti i nodi abbiano gli stessi script.
Provate il vostro programma con diverse disposizioni dei nodi posizionando il
gatto sul nodo iniziale (il percorso e’ completo quando si torna al nodo
iniziale).
Se gli script sono fatti bene, il programma funziona indipendentemente dalla
posizione dei nodi.
Cercate ora delle configurazioni tali che l’algoritmi Nearest Neighbour
restituisce soluzioni non ottimali. Potete usare il vostro programma per
calcolare la distanza e visualizzare il percorso!
Una volta fatti i test aggiungiamo alcune feature al programma.
Ripetere l’esecuzione
Innanzitutto aggiungiamo
la possibilita’ di provare diversi percorsi senza dover far ripartire il
programma. Aggiungiamo allora un nuovo sprite che funge da bottone “RESET”.
Quando premete il bottone dovete cancellare la traccia del
percorso (blocco  ) e
re-inizializzare le variabili.
Potreste utilizzare un messaggio (inviato a tutti gli
sprite) per implementare questa operazione (quando premuto il bottone manda
il messaggio e gli sprite inizializzano il loro stato).
Avete gia’ tutti gli ingredienti per modificare il programma!
Memorizzare la lunghezza del percorso
Aggiungiamo ora la
possibilita’ di memorizzare la lunghezza del percorso calcolato.
Supponendo di poter ripetere diversi tentativi sarebbe comodo poter ricordare
tutte le lunghezze calcolate in precedenza e poterne calcolare il valore
minimo.
Questa estensione ci permette di introdurre il concetto di “lista” un tipo
particolare di contenitore che non contiene un solo valore (come la variabile
“lunghezza”) ma ne puo’ contenere appunto una lista di lunghezza arbitraria
(es. la sequenza 1,2,3,4,5).
Definiamo allora una lista con il comando  con nome “Lista”.
Inoltre aggiungiamo un nuovo bottone “STORE” per aggiungere il valore
corrente della variabile “lunghezza” nella lista “Lista”.
Possiamo usare il blocco  per aggiungere un valore ad una lista.
Aggiungiamo ora un ulteriore bottone “minimo” per calcolare il minimo tra i valori contenuti nella
lista. Per fare questa operazione occorre un minimo di attenzione.
Lo sprite associato al bottone “MINIMO” deve ispezionare tutti gli elementi
della lista e confrontarli con una variabile min inizializzata ad un valore
molto grande (es. 1000000).
Per fare questa operazione possiamo usare il blocco iterazione  specificando come numero di volte la
lunghezza della lista  .
Usiamo inoltre una variabile (locale al bottone) “indice” per ricordarci
la posizione corrente nella lista (1,2,…., fino alla lunghezza).
All’interno del blocco di iterazione dobbiamo confrontare l’elemento in
posizione “indice” con “minimo”.
Per il confronto possiamo usare
nuovamente il costrutto condizionale ,
l’operatore di confronto, e l’estrazione di un elemento da una lista  passando come argomento la variabile
“indice”.
Se l’elemento e’ minore della variable “minimo” allora lo memorizziamo in “minimo”
al suo posto. Poi incrementiamo “indice”.
Alla fine dell’iterazione la variabile “minimo” conterra’ la lunghezza
minima contenuta nella lista!
Se siete arrivati fino anche questo punto…
Provate a creare diversi percorsi e a memorizzare la loro distanza nella
lista e calcolare il minimo.
Avete a questo punto costruito un tool per aiutare l’utente ad analizzare
TSP.
In particolare l’utente potrebbe provare tutti i cammini e calcolarne la
lunghezza.
Se usata in questo modo… il bottone “minimo” dovrebbe suggerirvi una
possibile euristica.
Supponete di aver analizzato una serie di cicli e di aver memorizzato il
mimino tra le loro lunghezze. Se ora iniziate una nuova esplorazione … come potreste sfruttare il valore
della variabile “minimo”?
Modificate il programma in modo da inserire questa “euristica”.
Se avete fatto anche questo …
Siete pronti per definire una nuova versione del vostro programma per
“calcolare” un percorso minimo. Potreste ad esempio usare l’algoritmo Nearest
Neighbour:
Il gatto-commesso si sposta da nodo in nodo scegliendo sempre quello piu’
vicino fino a quando ha visitato tutti i nodi (piu’ semplice rispetto a
tornare al nodo iniziale).
Provate a studiare questo nuovo problema e ad implementare un prototipo in
Scratch (con l’aiuto degli esercitatori!!).
Ultima cosa!
Siete nominati ufficialmente Scratchers!
Registratevi sul sito di Scratch e condividete il vostro progettino su
Internet tramite il tasto  . La comunita’ di Scratch condivide
gia’ piu’ di 500.000 progetti. Mancano solo i vostri!
Se non l’avete ancora finito…scaricate Scratch a casa dal sito http://scratch.mit.edu/
caricare il progetto nel sito e mandateci una mail con l’URL del progetto. Le
nostre email sono giorgio@disi.unige.it
e davide@disi.unige.it.
E buon divertimento!
|