Newsgroup: it.comp.lang.c++
Titolo: Vi prego aiuto!

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.
Ho creato una classe Roomche 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:
 int getVicino(int v)//ritorna il numero di stanze vicine
 boolean verifyVicino(int v)//verifica se una data stanza è vicina
dell'oggetto in questione
 int getVicino(int v)//ritorna i vicini
I dati sono:
    private int id; //id stanza
    private string nome; //nome della stanza
    public string percorsi[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[4]; //array che contiene gli id delle stanze vicine,
al massimo una stanza può avere 4 vicini
    public bool verifica[9]; //array utilizzato per ndicare 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 che non vi spedisco perchè non so neanche io cosa fanno,  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:
 class Percorso {
    Percorso(Room r)//assegna r a start e determina i percorsi per i
vicini(per esempio i percosi tra la stanza 4 e la 6, la 4 e la 2, la 4 e la
0 e la 4 e la 8)
    void findRoad(Room end, Room museo[])//questo metodo verifica se il
percorso per la destinazione(la stanza end) è stato determinato o no, se non
è stato determinato chiama la funzione finRoad2
private:
    void findRoad2( Room end, Room museo[])//determina il percorso tra 2
stanze se queste hanno un vicino comune per esempio determina il percorso
tra la stanza 4 e la stanza 3 o tra la 0 e la 8, se le due stanze non hanno
un vicino comune si chiama la funzione findRoad3
    void findRoad3(Room end, Room museo[])//questa funzione non so come
implementarla non so cosa fare, l'array di Room museo contiene tutte le
stanze del museo ed è definito in un main
    Room start; // a questo oggetto viene assegnata la stanza passata al
costruttore
    Percorso::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
        }
    }
     void Percorso::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);
    }
    void Percorso::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);
    }
     void Percorso::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

 stanze di un museo.
Questo e' un problema molto noto e studiato dell'informatica.
Consiste, dato un grafo, nel trovare un percorso minimo
(rispetto alla lunghezza del percorso, ad esempio) che collega
due nodi. Cerca con google "shortest path" algoritm oppure
"shortest path" problem
trovi una marea di informazioni (e probabilmente
anche di implementazioni, visto che e' un problema
notissimo e piuttosto semplice da risolvere)
per esempio qui:
http://www.nist.gov/dads/HTML/shortestpath.html
ciao,
g.

 due nodi. Cerca con google "shortest path" algoritm oppure
volevo dire "algorithm" (con l'acca).
Ho dato per scontato che tu conosca i grafi.
Diciamo che un grafo e' un insieme di vertici
e un insieme di archi, dove ogni arco collega 2 vertici
tra di loro.
Nel tuo caso le stanze del museo sono i vertici del grafo
e se due stanze sono collegate direttamente allora c'e' un arco nel
grafo tra i due.
L'idea di trovare tutti i percorsi possibili (invece di quello minimo)
mi sembra diventi impraticabile per musei con un numero di
stanze ragionevole: direi che il numero di percorsi cresce
esponenzialmente rispetto al numero di stanze.
ciao,
g.