Newsgroup: it.comp.java
Titolo: Vi prego aiutatemi!

Deve creare un programma che sia in grado di costruire i percorsi per
passare da una stanza all'altra attraverso un museo.
Allora ho provato a cercare algoritmi su internet ma non ci ho capito
assolutamente niente, sono implementati spesso come applet o sono fatti in
modo tale da caricare la mappa dei nodi da file e ci sono molte classi
all'interno che non riesco a capire.
Io ho provato a fare qualcosa per gli affari miei la cosa è molto semplice.
Ho creato una classe Room che contiene i nomi delle stanze, gli id delle
stanze e i vicini delle stanze.
La mappa di prova che ho è molto semplice è un quadrato 3*3 formato da 9
quadrettini ognuno dei quali rappresenta una stanza con id che vanno da 0 a
8.
Ora io ho provato a fare in questo modo.
Ho creato un array di stringhe in cui verranno inseriti i percorsi e un
array di booleani per verificare se il percorso è stato trovato.
La verifica per i vicini è posta a true e nei percorsi inserisco l'id del
vicino(l'array dei percorsi è inizializzato con l'id della stanza).
Ora per i percorsi che non sono stati ancora determinati io non so come fare
a determinarli. Ho provato a fare nel modo che sotto mi illustro ma non
funziona nulla. Qualcuno ha qualche idea semplice?
Il costo per andare da una stanza all'altra è sempre 1 non ci sono grossi
calcoli da fare qualcuno può aiutarmi?
Grazie.
public class Room {
    private int id;  //id della stanza
    private String nome;
    private String percorsi[]= new String[9];
    private int vicini[]=new int[4]; //una stanza al massimo può avere 4
vicini
    private boolean verifica[]=new boolean [9];
    public Room() {
        id=100;
        nome="";
        periodo="";
        opera="";
        /*vicinoa=100;
        vicinod=100;
        vicinos=100;
        vicinods=100;*/
        for(int i=0; i<4; i++)
            vicini[i]=100;        //l'array di vicini è inizializzato a 100,
questo numero non dice nulla serve ad indicare che non ci sono vicini
        for(int i=0; i<9; i++)
            percorsi[i]="";
    }
    public Room(int a, String s, String p, String o){
        setId(a);
        setNome(s);
        for(int i=0; i<4; i++)
            vicini[i]=100;
        for(int i=0; i<9; i++){
            percorsi[i]="";
            percorsi[i]+=id;
        }
    }
    public void setRoom(int a, String s, String p, String o){
        setId(a);
        setNome(s);
        for(int i=0; i<9; i++){
            percorsi[i]="";
            percorsi[i]+=id;
        }
    }
    public void setId(int a){
        id=a;
    }
    public void setNome(String s){
        nome=s;
    }
    public void addVicino(int v){
        for(int i=0; i<4; i++){
            if(vicini[i]==100 && v!=100){
                vicini[i]=v;
                break;
            }
        }
    }
    public int getVicino(int v){
        return vicini[v];
    }
    public int getId(){
        return id;
    }
    public String getNome(){
        return nome;
    }
    public void Percorsi(Room museo[]){  //l'array museo contiene tutte le
stanza del museo
        inizializzaPercorsi(museo);
        while(verifyComplete()!=true){ //verifica se tutti i percorsi sono
stati trovati, se provo a eseguire il metodo Percorsi di un oggetto Room in
una stanza il programma non termina mai sembra andare in ciclo infinito
            for(int j=0; j<verifica.length; j++){
                if(verifica[j]==false){
                    for(int h=0; h<vicini.length; h++){
                        if(getVicino(h)!=100 &&
museo[getVicino(h)].verifyVicino(j)){
                            percorsi[j]+= " " +
museo[getVicino(h)].getPercorsi(j); //viene aggiunto il percorso del vicino
al percorso della stanza per arrivare alla destinazione x
                            verifica[j]=true;
                        }
                    }
                }
            }
        }
    }
  public boolean verifyComplete(){ //verifica se tutti i percorsi sono stati
trovati
      for(int i=0; i<9; i++){
          if(verifica[i]==false)
              return false;
      }
     return true;
  }
   public void inizializzaPercorsi(Room museo[]){
         verifica[id]=true; //il boolean corrispondente all'id della stanza
è messo a true
          for(int j=0; j<4; j++){
                for(int k=0; k<9; k++){
                    if(vicini[j]==museo[k].getId()){
                    percorsi[k]+=" " + k;
                    verifica[k]=true;  //sengala che i percorsi per i vicini
ci sono
                    }
                }
            }
   }
    public String getPercorsi(int i){
        return percorsi[i];
    }
    public boolean verifyVicino(int v){   //verifica se una data stanbza è
vicina di un'altra stanza
        for(int i=0; i<4; i++){
            if(vicini[i]!=100 && vicini[i]==v && v!=100)
                return true;
        }
        return false;
    }
}

 wrote in message
news:n3KWb.224860$VW.91...@news3.tin.it...


 Tommaso.
 Allora io ho la mappa di un museo come questa per esempio:
7-8-3
 |  |   |
6-4-2
 |  |   |
5-0-1
Dove le | e i - rappresentano i corridoi di collegamento tra le varie
stanze.
Io ho un array di Room. Ogni Room ha un id, un nome, i proprio vicini e il
numero i percorsi verso ogni altra stanza.
Il mio problema sroge nel determinare i percorsi verso altre stanze cioè nel
determinare ad esempio i percorsi da seguire per arrivare dalla stanza 0
alla stanza 7 o alla stanza 6 o alla stanza 3, per fare un esempio.
Io ho provato a realizzare la classe Room in questo modo:
public class Room {
    private int id;
    private String nome;
    private String percorsi[]= new String[9];//contiene tutti i percorsi
verso tutte le destinazioni
    private int vicini[]=new int[4];
    private boolean verifica[]=new boolean [9]; //se impostato a true indica
che il percorso verso la destinazione x è presente. Il percorso verso la
destinazione x lo si ottiene percorsi[x]
    public Room() {
        id=100;
        nome="";
        for(int i=0; i<9; i++){
            percorsi[i]="";
        }
    }
    public Room(int a, String s, String p, String o){
        setId(a);
        setNome(s);
        for(int i=0; i<4; i++)
            vicini[i]=100;   //il 100 indica che non ci sono vicini
        for(int i=0; i<9; i++){
            percorsi[i]="";
            percorsi[i]+=id;
        }
    }
    public void setRoom(int a, String s, String p, String o){
        setId(a);
        setNome(s);
        for(int i=0; i<9; i++){
            percorsi[i]="";
            percorsi[i]+=id;
        }
    }
    public void setId(int a){
        id=a;
        verifica[id]=true;
    }
    public void setNome(String s){
        nome=s;
    }
    public void addVicino(int v){
        for(int i=0; i<4; i++){
            if(vicini[i]==100 && v!=100){
                vicini[i]=v;
                verifica[v]=true;
                percorsi[v]+=" " + v;
                break;
            }
        }
    }
    public int getVicino(int v){
        return vicini[v];
    }
    public int getId(){
        return id;
    }
    public String getNome(){
        return nome;
    }
    public void Percorsi(Room museo[]){//crea i percorsi
        for(int l=0; l<museo.length-1; l++){ //si ripete il ciclo in modo
tale da determinare i percorsi verso tutte le destinazioni
            for(int j=0; j<verifica.length; j++){
                if(verifica[j]==false){//verifica se esiste il percorso
verso j
                    for(int h=0; h<vicini.length; h++){
                        if(vicini[h]!=100 &&
museo[getVicino(h)].verifica[j]){  //se il vicino è valido(cioè il numero
nell'array vicini è diverso da 100) e se il vicino ha il percorso verso la
destinazione j
                            percorsi[j]+= " " +
museo[getVicino(h)].getPercorsi(j);   //al percorso verso j(in cui è già
incluso l'idi della stanza) è aggiunto il percorso verso j tramite il vicino
cui ci si arriva, per esempio se sono nella stanza 8 e voglio arrivare alla
stanza 2(j), il percorso verso 1 è uguale al percorso verso 1 di 8(che è
uguale a 8) più il percorso verso 2 della stanza 3(che è uguale a 3 2)
quindi il percorso complessivo sarà 8 3 2, questa cosa sembra funzionare ma
c'è un piccolo problema, provandolo ho visto che per arrivare dalla stanza 0
alla stanza 3 o 7 il percorso non mi viene determinato correttamente dato
che il percorso risulta sempre uguale a 0. Se invece provo con la stanza 3 a
cercare il percorso verso la stanza 6 tutto funziona ma c'è un piccolo
problema infatti come percorso mi viene dato 3 2 1 0 4 6, che è notevolmente
più lungo rispetto a 3 8 7 6, come posso risolvere tali inconvenienti?
                            verifica[j]=true; //segnala che adesso c'è il
percorso
                            j=0; //permette di iniziare nuovamente il ciclo
in modo da scambiare tutti i messaggi di aggiornamento
                        }
                    }
                }
            }
        }
    }
    public String getPercorsi(int i){
        return percorsi[i];
    }
    public boolean verifyVicino(int v){
        for(int i=0; i<4; i++){
            if(vicini[i]!=100 && vicini[i]==v && v!=100)
                return true;
        }
        return false;
    }
    public boolean percorsoC(int v){
        return verifica[v];
    }
}
Grazie di tutto.

 ,
ho esaminato il tuo problema.
Ho raggiunto la conclusione che è un classico esempio di attraversamento di
un grafo,
dove i nodi sono le stanze e dove il client (ad es. il main) definisce i
link tra i nodi e il percorso
viene calcolato da un metodo che attraversa il grafo.
Secondo me cmq il tutto può essere ricondotto a 2 classi:
* una classe Room che rappresenta i nodi del grafo
* una classe Link che mette a disposizione le funzioni necessarie per
associare un link tra due stanze
e mette a disposizione un metodo che calcola un percorso.
Copio codice classe Room (chiamata Room2):
public static final int MAX = 4;
public String itsName;
public Object[] itsRoad ;
public Room2[] itsAdjacent ;
public Room2(String aName)
{
itsRoad = new Object[MAX];
itsName = aName;
itsAdjacent = new Room2[MAX];
initialize(itsRoad);
initialize(itsAdjacent);
}
public int firstFreePosition()
{
for (int i = 0; i < MAX; i++)
if (itsAdjacent[i] == null) return i;
return -1;
}
public boolean isNear(Room2 aRoom)
{
for (int i=0; i < MAX;i++)
{
if (itsAdjacent[i]==aRoom) return true;
}
return false;
}
private void initialize(Object[] anArray)
{
for (int i = 0; i < MAX; i++) anArray[i] = null;
}
}
Copio esempio codice classe Link:
public class Link
{
static Object[] myRoad = new Object[500];
private static Stack myStack = new Stack();
static public boolean addLink (Room2 firstRoom, Room2 secondRoom)
{
if (firstRoom.firstFreePosition() != -1 && secondRoom.firstFreePosition()
!= -1)
{
firstRoom.itsAdjacent[firstRoom.firstFreePosition()] = secondRoom;
secondRoom.itsAdjacent[secondRoom.firstFreePosition() ] = firstRoom;
return true;
}
return false;
}
public static Object[] findRoad(Room2 start, Room2 middle, Room2 end)
{
return null;
}
}