Corsi precedenti

Prima Esercitazione in Laboratorio

Scrivere e testare una classe Java per la risoluzione di labirinti.

Un labirinto è una matrice le cui celle possono essere stanze (attraversabili) oppure pareti (non attraversabili). Ogni cella è identificata da una coppia di numeri naturali compresi fra e . Risolvere un labirinto tra la cella e la cella significa trovare un percorso che parta dalla cella , si muova per celle adiacenti (orizzontalmente o verticalmente) e libere (cioè stanze), e raggiunga la cella di destinazione .

La classe Labirinto deve contenere i seguenti metodi pubblici:

• Labirinto(int n): costruttore; n è la dimensione del labirinto. Inizialmente tutte le celle sono stanze.
• void impostaParete(int i, int j): fa sì che la cella (i, j) sia una parete.
• boolean risolviLabirinto(int is, int js, int id, int jd) cerca un percorso tra la cella (is, js) e la cella (id, jd). Restituisce true se e solo se un percorso siffatto esiste.
• int dammiPosizioneNelPercorso(int i, int j): se la cella (i, j) fa parte del percorso trovato dall’ultima invocazione del metodo risolviLabirinto, allora restituisce un intero che indica la posizione della stanza (i, j) all’interno del percorso trovato. La posizione è 1 per la stanza (is, ds), 2 per la stanza adiacente visitata immediatamente dopo, e così via. Se la cella (i, j) non fa parte del percorso, restituisce 0.

Effettuare test numerosi e frequenti. In particolare, scrivere un metodo main che crei il seguente labirinto (dove una cella grigia corrisponde ad una parete), lo risolva tra la cella (0, 0) e la cella (4, 4), e infine stampi il labirinto (in modo che sia facilmente intellegibile) con il percorso trovato.

Infine, calcolare la complessità computazionale del metodo risolviLabirinto in funzione della dimensione dell’input.

Suggerimenti per la risoluzione

Ricorsione

Si consiglia di risolvere il problema facendo uso della ricorsione. Infatti, osserviamo che esiste un percorso tra una stanza e la stanza se e soltanto se esiste un percorso tra una stanza adiacente ad e .

Dunque il metodo ricorsivo potrebbe effettuare le seguenti operazioni:

• verificare se coincide con (passo base della ricorsione: la destinazione è stata raggiunta). Se sì, restituire true.
• altrimenti:
  • per ciascuna cella adiacente a che sia una stanza e che non sia stata già visitata, cercare ricorsivamente se esiste un percorso da a . Se sì, restituire true.
  • infine, se abbiamo visitato tutte le stanze adiacenti senza successo, vuol dire che non esiste un percorso che porta a destinazione: restituire false.

Scrivere lo pseudocodice dell’algoritmo richiesto, e poi trasformarlo in codice Java. *Se si incontrano difficoltà*, continuare a leggere.

Rappresentazione dell’informazione

Rappresentazione del labirinto: il labirinto, evidentemente, può essere rappresentato usando una matrice di booleani (stanza/parete).

Marcatura delle stanze: tramite un’altra matrice di booleani si possono marcare le stanze visitate. Marcheremo una stanza all’inizio della visita di (ovvero dell’attivazione ricorsiva del risolutore a partire dalla stanza ). Osserviamo che, una volta che una stanza è stata marcata, è inutile (anzi, dannoso) esplorarla nuovamente: la marcatura non dovrà più essere rimossa.

Rappresentazione del percorso trovato: utilizzare una matrice di interi, inizializzata con zeri. Passare al metodo ricorsivo, come (ulteriore) parametro, la posizione della stanza visitata all’interno del percorso. Inizialmente tale posizione è 1; successivamente, se si sta visitando la stanza -esima del percorso, le visite ricorsive delle stanza adiacenti avranno come posizione . La posizione deve essere confermata (cioè scritta nella matrice) se e soltanto se la visita ha successo, cioè se e soltanto se l’attivazione attuale del metodo restituisce true.

Suggerimento S.O.S.: Pseudocodice

boolean risolviLabirintoRicorsivo(int i, int j, int id, int jd, int k) {
 
	if(!isStanza(i,j))  //Se non siamo su una stanza: es. parete o fuori dal labirinto
		return false;
 
	if(marca[i][j]) //Se la cella attuale è già marcata, non la visitiamo di nuovo
		return false;
 
	marca[i][j] = true;
 
	percorso[i][j]=k; //toglieremo questa marcatura se dovremo restituire false
 
	if(i==id && j==jd) //Caso base: destinazione raggiunta
		return true;
 
 
 
	//Per ogni cella adiacente: (iAd, jAd) in {(i, j-1), (i, j+1), (i-1, j), (i+1, j)}
	//invocare il metodo risolviLabirintoRicorsivo(iAd, jAd, id, jd, k+1).
	//Se questo restituisce true,
	//restituire true.
	[...]
 
 
	//Altrimenti:
	//non abbiamo trovato il percorso perché non esiste
 
	percorso[i][j]=0; //Togliamo la marcatura come parte del percorso
	return false;
 
}
 

Esercizi consigliati

E’ molto importante essere in grado di risolvere agevolmente gli esercizi seguenti.

Rappresentare un insieme di numeri (per esempio interi) utilizzando le seguenti tre rappresentazioni:

1. tramite array non ordinato
2. tramite array ordinato
3. tramite lista collegata

Nelle prime due rappresentazioni, per semplicità, si faccia uso di array sovradimensionati rispetto agli insiemi da rappresentare.

Per ciascuna rappresentazione, si scrivano e si testino dei metodi che effettuino le cinque operazioni seguenti:

1. creazione dell’insieme vuoto
2. creazione di un insieme con un unico elemento i
3. verifica di appartenenza di un elemento i ad un insieme
4. unione di due insiemi (creando e restituendo un nuovo insieme)
5. intersezione di due insiemi (creando e restituendo un nuovo insieme)

Commenti dei visitatori

Accedi per lasciare commenti.