dungedra
04-02-2013, 05:09
In un aeroporto vi sono n gate, ciascuno dei quali è individuato da un codice
I gate possono essere collegati tra loro per mezzo di corridoi bidirezionali ciascuno avente un certo costo di manutenzione. (il costo di manutenzione rappresenta il peso dell’arco)
ipotizzare un funzionamento a regime):
funzione “risparmio della spesa” che restituisce se esiste l’elenco minimo dei corridoi da lasciare attivi per garantire che tutti i gate siano raggiungibili da ogni altro gate e tale da assicurare un costo minimo di manutenzione totale.
inizio risoluzione:
public class gate{
protected String codice;
public gate(String codice){
this.codice=codice;
}
}
public class aereoporto {
private GrafoNOLP G;
private Vettass<gate> v;
public aereoporto(int n){
G=new GrafoNOLP(n);
v=new Vettass<gate>(n);
}
public LinkedList<Arco> risparmioSpesa(){
LinkedList<Arco>L=new LinkedList();
.
.
.
return L;
}
}
essendo che mi viene richiesto il costo di trasferimento minimo, cioè il peso minimo,mi verrebbe in mente di usare Dijkstra…pero non saprei come fare a ricavarmi gli archi da non cancellare e da fare rimanere attivi…
per quanto riguardava di fatto di essere raggiungibili da ogni altro gate, pensavo di usare la funzione esisteCammmino, ciclando i nodi del grafo attraverso un ciclo for annidato…
è un po tutto campato in aria, ma non chiedo la risoluzione anche se sarebbe ben accetta, ma qualche idea che mi chiarisca come fare..
per il grafo posso utilizzare i seguenti metodi
Si possono usare i package standard di Java (Vedere in particolare il package java.util
su http://java.sun.com/j2se/1.4.2/docs/api/java/util/package-summary.html). Per tutto il
resto fare riferimento ai testi consigliati.
package Grafi;
public interface Grafo {
public int numNodi(); // restituisce num. nodi
public int numArchi(); // restituisce num. archi
public LinkedList<Arco> archi(); // rest. elenco archi del grafo
public LinkedList<Arco> adiacenti(int v); // rest. lista degli archi uscenti da v
public boolean esisteArco (int x, int y); // verifica esistenza arco fra x ed y
public boolean aggiungiArco(int x, int y); // ins. arco fra x ed y
public boolean rimuoviArco(int x, int y); // rimuove arco fra x ed y
public ArrayList<Boolean>VisitaDFS(int x); // DFS (similm. BFS)a partire da x
public ArrayList<Integer>Dijkstra(int x); // Dijkstra a partire da x
public boolean esisteCammino (int x, int y); // ver. esistenza cammino fra x ed y
}
-------------------------------------------------------------------------------
Le classi GrafoOL, GrafoOM, GrafoNOL, GrafoNOM implementano l’interfaccia Grafo
-------------------------------------------------------------------------------
public class Arco {
public int orig, dest;
public Arco(int x, int y) {orig = x; dest = y;}
}
-------------------------------------------------------------------------------
public class ArcoP extends Arco{
public int orig, dest, peso;
public ArcoP(int x, int y, int p) {super(x,y); peso = p;}
}
-------------------------------------------------------------------------------
public class GrafoOLP extends GrafoOL implements Grafo;
// restituisce true se l'arco esiste col peso specificato altrimenti false
public boolean esisteArcoPesato (int x, int y, int p);
// inserisce arco fra x ed y col peso specificato
public void aggiungiArcoPesato (int x, int y, int p);
// rimuove arco fra x ed y e fissa il peso a 0
public void rimuoviArcoPesato (int x, int y);
rimuoviArco(x,y); matricePesi[x][y] = 0;
// restituisce il peso dell'arco
public int peso(int x,int y);
-------------------------------------------------------------------------------
public class GrafoOMP extends GrafoOM implements Grafo;
// La stessa interfaccia di GrafoOLP. Idem per GrafoNOLP e GrafoNOMP
----------------------------------------------------------------------------------------
GrafoOM g = new GrafoOM(100); // Esempio di uso del costruttore
// scansione degli adiacenti del nodo 0
ListIterator<Arco> e = g.adiacenti(0).listIterator();
while (e.hasNext()){
Arco a = e.next();
g.rimuoviArco(a.orig, a.dest);
}
// scansione del grafo per nodi
for (int i = 0; i < g.numNodi(); i++)
; // ...
GrafoOLP g1 = new GrafoOLP(100);
// scansione del grafo per archi per impostarli tutti a 1
ListIterator<Arco> e1 = g1.archi().listIterator();
while (e1.hasNext()){
ArcoP a = (ArcoP) e1.next();
a.peso = 1; // errato
g1.aggiungiArcoPesato(a.orig, a.dest, 1); // corretto
}
-------------------------------------------------------------------------------------
public class Vettass<T>; // Vettore associativo
Interfaccia simile a java.util.Map.
I gate possono essere collegati tra loro per mezzo di corridoi bidirezionali ciascuno avente un certo costo di manutenzione. (il costo di manutenzione rappresenta il peso dell’arco)
ipotizzare un funzionamento a regime):
funzione “risparmio della spesa” che restituisce se esiste l’elenco minimo dei corridoi da lasciare attivi per garantire che tutti i gate siano raggiungibili da ogni altro gate e tale da assicurare un costo minimo di manutenzione totale.
inizio risoluzione:
public class gate{
protected String codice;
public gate(String codice){
this.codice=codice;
}
}
public class aereoporto {
private GrafoNOLP G;
private Vettass<gate> v;
public aereoporto(int n){
G=new GrafoNOLP(n);
v=new Vettass<gate>(n);
}
public LinkedList<Arco> risparmioSpesa(){
LinkedList<Arco>L=new LinkedList();
.
.
.
return L;
}
}
essendo che mi viene richiesto il costo di trasferimento minimo, cioè il peso minimo,mi verrebbe in mente di usare Dijkstra…pero non saprei come fare a ricavarmi gli archi da non cancellare e da fare rimanere attivi…
per quanto riguardava di fatto di essere raggiungibili da ogni altro gate, pensavo di usare la funzione esisteCammmino, ciclando i nodi del grafo attraverso un ciclo for annidato…
è un po tutto campato in aria, ma non chiedo la risoluzione anche se sarebbe ben accetta, ma qualche idea che mi chiarisca come fare..
per il grafo posso utilizzare i seguenti metodi
Si possono usare i package standard di Java (Vedere in particolare il package java.util
su http://java.sun.com/j2se/1.4.2/docs/api/java/util/package-summary.html). Per tutto il
resto fare riferimento ai testi consigliati.
package Grafi;
public interface Grafo {
public int numNodi(); // restituisce num. nodi
public int numArchi(); // restituisce num. archi
public LinkedList<Arco> archi(); // rest. elenco archi del grafo
public LinkedList<Arco> adiacenti(int v); // rest. lista degli archi uscenti da v
public boolean esisteArco (int x, int y); // verifica esistenza arco fra x ed y
public boolean aggiungiArco(int x, int y); // ins. arco fra x ed y
public boolean rimuoviArco(int x, int y); // rimuove arco fra x ed y
public ArrayList<Boolean>VisitaDFS(int x); // DFS (similm. BFS)a partire da x
public ArrayList<Integer>Dijkstra(int x); // Dijkstra a partire da x
public boolean esisteCammino (int x, int y); // ver. esistenza cammino fra x ed y
}
-------------------------------------------------------------------------------
Le classi GrafoOL, GrafoOM, GrafoNOL, GrafoNOM implementano l’interfaccia Grafo
-------------------------------------------------------------------------------
public class Arco {
public int orig, dest;
public Arco(int x, int y) {orig = x; dest = y;}
}
-------------------------------------------------------------------------------
public class ArcoP extends Arco{
public int orig, dest, peso;
public ArcoP(int x, int y, int p) {super(x,y); peso = p;}
}
-------------------------------------------------------------------------------
public class GrafoOLP extends GrafoOL implements Grafo;
// restituisce true se l'arco esiste col peso specificato altrimenti false
public boolean esisteArcoPesato (int x, int y, int p);
// inserisce arco fra x ed y col peso specificato
public void aggiungiArcoPesato (int x, int y, int p);
// rimuove arco fra x ed y e fissa il peso a 0
public void rimuoviArcoPesato (int x, int y);
rimuoviArco(x,y); matricePesi[x][y] = 0;
// restituisce il peso dell'arco
public int peso(int x,int y);
-------------------------------------------------------------------------------
public class GrafoOMP extends GrafoOM implements Grafo;
// La stessa interfaccia di GrafoOLP. Idem per GrafoNOLP e GrafoNOMP
----------------------------------------------------------------------------------------
GrafoOM g = new GrafoOM(100); // Esempio di uso del costruttore
// scansione degli adiacenti del nodo 0
ListIterator<Arco> e = g.adiacenti(0).listIterator();
while (e.hasNext()){
Arco a = e.next();
g.rimuoviArco(a.orig, a.dest);
}
// scansione del grafo per nodi
for (int i = 0; i < g.numNodi(); i++)
; // ...
GrafoOLP g1 = new GrafoOLP(100);
// scansione del grafo per archi per impostarli tutti a 1
ListIterator<Arco> e1 = g1.archi().listIterator();
while (e1.hasNext()){
ArcoP a = (ArcoP) e1.next();
a.peso = 1; // errato
g1.aggiungiArcoPesato(a.orig, a.dest, 1); // corretto
}
-------------------------------------------------------------------------------------
public class Vettass<T>; // Vettore associativo
Interfaccia simile a java.util.Map.