Newsgroup: it.scienza.informatica
Titolo: Aiuto 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.
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

     Grazie e scusate
Prego,
ciao buon lavoro.
Daniele.

 o qualcosa del genere quando eseguo il programma
Immagina il museo come un grafo: le stanze e i corridoi sarebbero
rispettivamente i nodi e gli archi. Quindi il problema è semplicemente
trovare il cammino minimo tra una coppia di nodi. Per farlo esistono
soluzioni già pronte (Prim, Dijkstra ecc.), che devi necessariamente
studiarti su un libro di algoritmi.
L'algoritmo di forza bruta è decisamente da evitare, lo credo bene che
va in stack overflow...