Laboratorio di Algoritmi
Progetto “Labirinto” (febbraio 2021)
Nota: La scadenza del progetto `e fissata per venerd`ı 15 febbraio compreso.
Nota: Si consiglia di verificare ogni tanto se questo documento `e stato aggiornato per correggere errori e rispondere a domande di altri studenti.
Il problema
Questo progetto non riguarda un problema pratico, ma una situazione ispirata a quei videogiochi in cui bisogna risolvere un enigma che richiede di intervenire su un ambiente virtuale e modificarlo portandolo in una situazione finale desiderata.
L’ambiente virtuale `e un labirinto, formato da camere e corridoi in un edificio a un solo piano. Si suppone di conoscere la pianta dell’edificio, sulla quale `e segnata la posizione dell’agente che si muover`a nell’ambiente per risolvere l’enigma e quella di un insieme di oggetti etichettati con lettere dell’alfabeto. Per semplicit`a, il labirinto
`
e descritto da una matrice di posizioni discrete, ciascuna individuata dal valore di due coordinate che indicano la riga (ovvero l’ordinata, misurata dall’alto verso il basso) e la colonna (ovvero l’ascissa misurata da sinistra verso destra). Due posizioni sono adiacenti se hanno una coordinata coincidente e l’altra che differisce per una sola unit`a. Quindi ogni posizione ha in generale quattro posizioni adiacenti, due sulla stessa riga e due sulla stessa colonna; ovviamente, le posizioni sui bordi dell’edificio ne hanno di meno. Si noti che le posizioni vicine in diagonale non sono adiacenti: questo avr`a conseguenze poco intuitive sui risultati. Ogni posizione della matrice pu`o essere libera, occupata da un muro, dall’agente o da un oggetto, ma non occupata contemporaneamente da entit`a diverse.
Il primo compito da svolgere `e analizzare il labirinto suddividendolo in camere.
Definiremo porta una posizione non occupata da muri, ma adiacente a due posizio- ni occupate da muri nella stessa riga o nella stessa colonna (l’agente e gli oggetti vengono ignorati, come se si trattasse di posizioni vuote. Una camera `e definita come una regione connessa massimale non occupata da muri o porte (considerando anche qui le posizioni dell’agente e degli oggetti come posizioni vuote). Il concetto di connessione deriva da quello di adiacenza fra due posizioni sopra enunciato. Una volta individuate le camere, bisogna determinarne l’area, il perimetro e la posizio- ne di riferimento. L’area `e il numero di posizioni che costituiscono la camera. Il perimetro `e il numero di posizioni occupate da muri o porte che risultano adiacenti alla camera1. La posizione di riferimento `e la posizione della camera che ha la pi`u piccola coordinata di riga, ovvero ordinata; se vi sono pi`u posizioni nella stessa riga, si considera quella con la pi`u piccola coordinata di colonna, ovvero ascissa. Le ca- mere vanno ordinate per area decrescente; in caso di aree coincidenti, si procede per perimetro decrescente; in caso di perimetri coincidenti per posizione di riferimento crescente (anche in questo caso, si considera prima la riga e poi la colonna).
Il secondo compito da svolgere `e muovere l’agente in modo da raggiungere gli oggetti e spostarli fino all’uscita, che `e l’unica porta che si trova ai bordi dell’edifi- cio (cio`e nella prima o ultima riga, oppure nella prima o ultima colonna). L’agente si muove una posizione alla volta in una delle quattro direzioni possibili, indicate convenzionalmente come nord (stessa colonna e riga precedente), est (stessa riga e colonna successiva), sud (stessa colonna e riga successiva) e ovest (stessa riga e co- lonna precedente). L’agente sposta gli oggetti “spingendoli”, cio`e raggiungendo una
1Considerare anche le porte ed escludere l’adiacenza in diagonale porter`a a risultati poco intuitivi, che per`o accettiamo per semplicit`a.
posizione adiacente a quella corrente dell’oggetto e muovendosi verso l’oggetto stes- so; questo si sposter`a di conseguenza, scorrendo nella stessa direzione dell’agente e rimanendo sempre nella posizione successiva. Per semplicit`a, l’agente deve spostare gli oggetti uno per uno, senza interrompere le operazioni su uno per agire su un altro, non pu`o spostarne due contemporaneamente formando un treno di oggetti e li deve spostare in ordine alfabetico crescente rispetto alle etichette. Ovviamente, questo compito si pu`o svolgere in generale in molti modi diversi. Si richiede di determinare il modo meno costoso, considerando che, se l’agente `e libero, uno spostamento di un passo ha un costo pari a 1 in direzione nord o sud e pari a 2 in direzione est oppure ovest; se invece l’agente sta spingendo un oggetto, uno spostamento di un passo dell’agente e dell’oggetto ha un costo pari a 8 in direzione nord o sud e pari a 15 in direzione est oppure ovest. Si noti che, ovviamente, gli oggetti non possono penetrare nei muri, e quindi l’agente che spinge un oggetto pu`o muoverlo fino a por- tarlo a contatto con il muro, ma non oltre. Inoltre, se un oggetto `e adiacente a un muro, l’agente pu`o farlo strisciare lungo il muro, ma non pu`o allontanarlo, perch´e non esiste una posizione libera fra oggetto e muro in cui infilarsi per spingere. Di conseguenza, se un oggetto raggiunge un angolo `e bloccato. Queste osservazioni dettagliate sono in effetti tutte implicite nelle regole di spostamento date all’inizio, e dovrebbero servire solo a rendere pi`u chiare e intuitive le regole stesse.
Il progetto
Il progetto prevede di realizzare un programma che legga da un file di testo la descrizione di un labirinto. Il labirinto `e descritto come una matrice rettangolare di caratteri che corrispondono alle posizioni: uno spazio bianco indica che la posizione
`e libera, una X che `e occupata da un muro, una A dall’agente, una lettera minuscola da un oggetto. Le righe e le colonne della matrice sono indicizzate a partire da 0 per la prima riga e colonna, cio`e l’angolo in alto a sinistra2. Il seguente esempio riporta un labirinto di 8 righe e 11 colonne, che contiene l’agente in posizione (5, 6) e tre oggetti, etichettati come f, h e m, rispettivamente in posizione (2, 5), (6, 3) e (5, 8). L’uscita `e nella posizione (0, 1).
X XXXXXXXXX
X XX X
X XXXf XXXX
X X
X XXXXXXX X
X A m X
X h X
XXXXXXXXXXX
Analisi del labirinto Il primo compito richiede di individuare le camere del labi- rinto, distinguendo fra muri, porte e posizioni interne alle camere (le quali compren- dono anche la posizione occupata dall’agente e dagli oggetti). L’esempio precedente mostra alcuni casi “degeneri” che risolveremo applicando esattamente le definizioni.
Per esempio, le posizioni (1, 1), (1, 4), (1, 7) e molte altre, che verrebbe pi`u naturale definire “nicchie” o “tratti di corridoio” o “porzioni di camera stretta”, sono per definizione porte. A questo punto, `e possibile introdurre la nozione di adiacenza, e quindi la nozione derivata di connessione, fra posizioni interne alle camere, in modo da individuare le camere stesse. Una volta individuate le camere basta applicare le definizione per determinare l’area, il perimetro e la posizione di riferimento di
2Durante il corso si `e sempre usata l’indicizzazione a partire da 1, ma partendo da 0 si possono trattare le righe della matrice come stringhe, se si vuole (non `e richiesto).
ciascuna. Quindi, occorre ordinarle per area decrescente, perimetro decrescente, colonna e riga della posizione di riferimento crescenti.
Il formato richiesto per l’uscita `e il seguente. Si indichi il numero delle camere seguito da uno spazio e dalla parola chiave camere. Per esempio:
4 camere
Poi si vada a capo e si descrivano le camere nell’ordine indicato riportando i seguenti risultati, una riga per camera, separati da singoli spazi:
1. la parola chiave camera seguita dal numero d’ordine, crescente da 1 al numero totale delle camere;
2. la parola chiave area seguita dall’area della camera;
3. la parola chiave perimetro seguita dal perimetro della camera;
4. la parola chiave posizioni seguita dall’elenco delle posizioni interne alla ca- mera in ordine di riga crescente e, a pari riga, di colonna crescente (in questo modo, la posizione di riferimento `e automaticamente in testa all’elenco); ogni posizione va indicata con la coppia degli indici di riga e colonna, racchiusi fra parentesi tonde e separati da una virgola.
Per esempio, la seconda camera del labirinto su riportato `e indicata come:
camera 2 area 6 perimetro 14 posizioni (1,5) (1,6) (2,5) (2,6) (2,5) (3,6) Suggerimento: conviene ragionare in termini di grafi e componenti connesse.
Spostamento degli oggetti Il secondo compito richiede di muovere l’agente in modo da raggiungere il primo oggetto in ordine alfabetico, e poi spingerlo sino al- l’uscita con il costo minimo. Il procedimento va ripetuto su ciascun altro oggetto, sempre in ordine alfabetico, immaginando che l’agente venga magicamente teletra- sportato di nuovo nella sua posizione iniziale. Si noti che, per ogni tragitto, gli oggetti gi`a spostati non esistono pi`u, mentre quelli non ancora spostati sono intoc- cabili, dato che le regole vietano di muoverli durante il tragitto dedicato all’oggetto corrente.
Il formato richiesto per l’uscita `e il seguente. Ogni riga si riferisce a un oggetto e contiene le seguenti informazioni, separate da spazi:
• l’etichetta dell’oggetto;
• il costo dello spostamento;
• il tragitto percorso dall’agente, rappresentato come una sequenza continua di lettere:
– n e N indicano che l’agente si muove verso nord, rispettivamente in modo libero o spingendo un oggetto;
– e e E indicano che l’agente si muove verso est, rispettivamente in modo libero o spingendo un oggetto;
– s e S indicano che l’agente si muove verso sud, rispettivamente in modo libero o spingendo un oggetto;
– o e O indicano che l’agente si muove verso ovest, rispettivamente in modo libero o spingendo un oggetto.
Per esempio, se l’agente si sposta verso est di due passi, il primo liberamente e il secondo spingendo l’oggetto m, si stampa la seguente riga.
m 11 eE
Ovviamente, questo tragitto non spinge l’oggetto fino all’uscita, e quindi non `e una soluzione valida.
Nel caso in cui non sia possibile spostare l’oggetto fino all’uscita (perch´e `e chiuso in una stanza non raggiungibile dall’agente o da cui non si pu`o accedere all’uscita, o perch´e `e in una posizione che termina necessariamente in uno stallo), si stamper`a una riga contenente:
• l’etichetta dell’oggetto;
• la parola chiave bloccato
Suggerimento: `E abbastanza intuitivo che il problema riguardi la ricerca di un cam- mino di costo minimo in un grafo. D’altra parte, la presenza degli oggetti impedisce di considerare semplicemente un grafo che associ nodi alle posizioni dell’agente nel labirinto e archi alle coppie di nodi adiacenti. Infatti, lo stesso nodo potrebbe essere raggiungibile o no a seconda della posizione dell’oggetto (che non `e costante). Inol- tre, lo stesso arco pu`o essere utilizzabile o no a seconda della posizione dell’oggetto e avere costi diversi a seconda che venga percorso dall’agente libero o spingendo un oggetto. Suggerisco di considerare un grafo astratto in cui ogni nodo corrisponde a una coppia di posizioni lecite (quella dell’agente e quella dell’oggetto) e ogni arco ad uno spostamento fra coppie di posizioni “adiacenti” che rispetti le regole. Ovvia- mente, tale grafo ha molti nodi (probabilmente per lo pi`u inutili), e questo affligge la complessit`a dell’algoritmo risultante3.
Esempio Riprendiamo l’esempio da 8 righe e 11 colonne.
X XXXXXXXXX
X XX X
X XXXf XXXX
X X
X XXXXXXX X
X A m X
X h X
XXXXXXXXXXX
Il labirinto comprende 4 camere, di cui le due pi`u piccole sarebbero pi`u propria- mente definibili come “angoli di corridoio”, ma sono classificate come camere per mantenere semplici le definizioni.
4 camere
camera 1 area 18 perimetro 22 posizioni (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7) (5,8) (5,9) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7) (6,8) (6,9)
camera 2 area 6 perimetro 10 posizioni (1,5) (1,6) (2,5) (2,6) (3,5) (3,6) camera 3 area 1 perimetro 4 posizioni (3,1)
camera 4 area 1 perimetro 4 posizioni (3,9)
dove le informazioni sulla prima camera vanno a capo per motivi di spazio, ma dovrebbero invece proseguire di seguito.
3Ovviamente, non `e vietato usare modelli alternativi, `e probabile che vi siano modelli pi`u efficienti e sono disponibile a ragionarne. Discuterli nella relazione `e anche senz’altro lecito e utile. Diciamo che mi pare un po’ azzardato realizzarli, giocando sull’esito di un progetto che `e
Dei tre oggetti, il secondo `e bloccato, mentre il primo e il terzo vengono sposta- ti verso l’uscita con due tragitti che partono dalla posizione iniziale dell’agente e terminano all’uscita.
f 158 seeennnooonnoSesOOOOeeeeeeesssoonoooooonNNNN h bloccato
m 164 seeenOOOOOOOsoNNNNNN
Si noti come ogni volta che l’oggetto deve cambiare direzione, l’agente si muova liberamente per portarsi nella nuova posizione adatta a spingere l’oggetto, a volte con deviazioni complicate (`e il caso dell’ultima svolta dell’oggetto f).
Chiarimenti
In questa sezione saranno riportate le risposte a domande e dubbi.
