Newsgroup: it.comp.java
Titolo: Sto impazzendo!

Scusate se vi rompo le scatole ma dopo questo messaggio non mi vedrete più.
Io stavo cercando di creare un metodo che calcoli il percorso minimo tra 2
stanze di un museo. A questo proposito ringrazio Tommaso Torti che è stato
gentilissimo.
Ho creato una Classe stanza che contiene il nome della stanza, l'id della
stanza, i vicini della stanza e le funzioni per verificare se una
determinata stanza è vicino oppure no, oltre ai metodi set e get.
Questi sono i metodi principali della classe stanza, escludento i set ed i
get:
 public int getVicino(int v)//ritorna il numero di stanze vicine
public boolean verifyVicino(int v)//verifica se una data stanza è vicina
dell'oggetto in questione
public int getVicino(int v)//ritorna i vicini
I dati sono:
    private int id; //id stanza
    private String nome; //nome della stanza
    public String percorsi[]= new String[9]; //array che dovrebbe contenere
i percorsi verso tutte le stanze del museo, il percorso per la stanza X è
contenuto in percorsi[X]
    private int vicini[]=new int[4]; //array che contiene gli id delle
stanze vicine, al massimo una stanza può avere 4 vicini
    public boolean verifica[]=new boolean [9]; //array utilizzato per
indicare che il percorso per la stanza con id=X è stato
determinato(verifica[X]=true) o no verifica[X]=false
Ovviamente ci sono i metodi set e get per is e nome e c'è il metodo per
inserire un vicino.
Per determinare il percorso ho provato a creare una classe Percorso, solo
che non so come fare a determinare tutti i percorsi perchè so determinare
solo i percorsi più scemi, ho provato in vari modi uno più assurdo
dell'altro ma o non funzionano o mi viene dato stack overflow o qualcosa del
genere quando eseguo il programma, quindi sono fermo da settimane ormai(lo
so sono stupido ma abbiate pazienza vi prego). Qua vi mostro la classe
Percorso che ho creato che calcola solo una parte dei percorsi, ad esempio
se utilizzo un museo con questa disposizione di stanze:
 7-8-3
  |  |   |
 6-4-2
  |  |   |
 5-0-1
Con quello che ho scritto posso determinare percorsi come per esempio quello
tra 7 e 8(sono vicini quindi è immediata la cosa), tra 7 e 3(hanno un vicino
in comune e quindi è abbastanza semplice) ma non tra 7 e 2 per esempio o tra
7 e 0 per esempio. Ora questo è quello che ho fatto nella classe Percorso:
public class Percorso {
    private Room start; //viene assegnata la classe passata del costruttore
    public Percorso(Room r){
        for(int i=0; i<r.getNumVicini(); i++){
            r.verifica[r.getVicino(i)]=true;//viene preso l'id dei vicini di
r(l'id dei vicini è contenuto nell'array vicini) e viene settato a true la
verifica del percorso per quel vicino
            r.percorsi[r.getVicino(i)]=r.getId() " " +
r.getVicino(i);//viene inserito il percorso per il vicino nell'array
percorsi
        }
    }
     public void findRoad(Room end, Room museo[]){
         if(!(start.verifica[end.getId()])) //verifica se il percorso è
stato determinato o no, se il percorso non è stato determinato si richiama
la funzione finRoard2, l'array museo che viene passato è un array che
contiene tutte le stanze del museo.
             findRoad2(start, end, museo);
    }
    private void findRoad2( Room end, Room museo[]){//questa funzione
determina il percorso tra 2 stanze, se queste hanno un vicino in comune
        for(int i=0; i<start.getNumVicini(); i++){   //questi deu cicli for
annidati servono per verificare se ci sono vicini comuni
            for(int j=0; j<end.getNumVicini(); j++){
                if(start.getVicino(i)==end.getVicino(j) &&
start.verifica[end.getId()]==false){ //se il vicino della stanza start è
uguale al vicino della stanza end e se il percorso per la stanza end non è
stato determinato
                    start.verifica[end.getId()]=true;//porre a true la
verifica per il percorso della stanza end
                    start.percorsi[end.getId()]=start.getId()+ " " +
start.getVicino(i) + " " + end.getId();//setta il percorso per end pari a
l'id di start più l'id del vicino comune più l'id della destinazione
                }
            }
        }
          if(start.verifica[end.getId()]==false)//se il percorso per la
destinazione desiderata non è stato trovato invocare la funzione findRoad3
              findRoad3(start, end, museo);
    }
    private String findRoad3(Room end, Room museo[]){//ecco il probelam
questa funzione non so cosa fargli fare non so come implementarla qualcuno
ha qualche idea che possa essermi utile?
}
    Grazie e scusate

 [CUT]
it.comp.programmare
it.scienze.informatica
-- 
/**
  * Mattia Belletti - Undergraduate student @ 
cs.unibo.it
  * ICQ: 33292311   - email: 
mbel...@cs.unibo.it
  * IRC: BluShine   - site(s): 
http://cs.unibo.it/~mbellett
  * Linux registered user 299762 @ Linux registered machine 213003
  */

Carissimo,
come già ti ho accennato, la soluzione al tuo problema è semplice e basata
sul concetto
di grafo e algoritmi di attraversamento del grafo.
Cerca su google le parole chiave "graph", "java","depth-first search"
e via dicendo.
Da qualche parte troverai del codice da cui prendere spunto. Tuttavia ti
copio sotto del codice che ho estratto dal libro MWSS: Data Structures and
Algorithms in
Java di Robert Lafore .
Solo qualche osservazione:
1 ) E' sufficiente che rinomini la classe Vertex con il nome Room,
eventualmente modificando
un po' la sua struttura. Ad esempio identificando ogni stanza con una
stringa ed eventualmente
aggiungendo altre informazioni che ti possono servire.
2 ) Rinomina la classe Graph con il nome Museo.
3 ) Giusto per non toglierti tutto il gusto dell' esplorazione, sono
possibili (e auspicabili)
i seguenti miglioramenti:
a ) il metodo dfs() parte da un vertice predefinito. Sarebbe carino
calcolare il percorso
data una stanza iniziale e fermare l' attraversamento quando trova quella
finale
b ) la classe Graph usa una matrice di adiacenza, soluzione semplice e abb.
chiara ma decisamente
non performante. Puoi usare una lista di adiacenza, facendo sì che ogni
vertice memorizzi
una lista (in java puoi usare la classe Vector) dei vertici a lui adiacenti.
4 ) Prova il codice sotto con il seguente esempio (ovvero quello che hai
postato graficamente tu!):
Graph theGraph = new Graph();
theGraph.addVertex('0');
theGraph.addVertex('1');
theGraph.addVertex('2');
theGraph.addVertex('3');
theGraph.addVertex('4');
theGraph.addVertex('5');
theGraph.addVertex('6');
theGraph.addVertex('7');
theGraph.addVertex('8');
theGraph.addEdge(7,8);
theGraph.addEdge(7,6);
theGraph.addEdge(6,4);
theGraph.addEdge(5,6);
theGraph.addEdge(5,0);
theGraph.addEdge(0,1);
theGraph.addEdge(0,4);
theGraph.addEdge(1,2);
theGraph.addEdge(4,2);
theGraph.addEdge(8,4);
theGraph.addEdge(8,3);
theGraph.addEdge(3,2);
System.out.print("Visits: ");
theGraph.dfs(); // depth-first search
System.out.println();
-------------------------------------------------
public class Vertex
{
public char label;
public boolean wasVisited;
public Vertex(char lab)
{
label = lab;
wasVisited = false;
}
}
------------------------------------------------
public class StackX
{
private final int SIZE = 20;
private int[] st;
private int top;
public StackX() // constructor
{
st = new int[SIZE]; // make array
top = -1;
}
public void push(int j) // put item on stack
{ st[++top] = j; }
public int pop() // take item off stack
{ return st[top--]; }
public int peek() // peek at top of stack
{ return st[top]; }
public boolean isEmpty() // true if nothing on stack
{ return (top == -1); }
} // end class StackX
------------------------------------------------------------
public class Graph
{
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int nVerts; // current number of vertices
private StackX theStack;
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int j=0; j<MAX_VERTS; j++)
for(int k=0; k<MAX_VERTS; k++)
adjMat[j][k] = 0;
theStack = new StackX();
}
public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end)
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
public void displayVertex(int v)
{
System.out.print(vertexList[v].label);
}
public void dfs() // depth-first search
{ // begin at vertex 0
vertexList[0].wasVisited = true; // mark it
displayVertex(0); // display it
theStack.push(0); // push it
while( !theStack.isEmpty() ) // until stack empty,
{
// get an unvisited vertex adjacent to stack top
int v = getAdjUnvisitedVertex( theStack.peek() );
if(v == -1) // if no such vertex,
theStack.pop();
else // if it exists,
{
vertexList[v].wasVisited = true; // mark it
displayVertex(v); // display it
theStack.push(v); // push it
}
}
for(int j=0; j<nVerts; j++) // reset flags
vertexList[j].wasVisited = false;
}
public int getAdjUnvisitedVertex(int v)
{
for(int j=0; j<nVerts; j++)
if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
return j;
return -1;
}
}

