.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [PROGETTO] Percorsi Colorati (http://www.dsy.it/forum/showthread.php?threadid=36135)

 
qualcuno ha già fatto la parte che riguarda il percorso ottimo?

__________________
by Ð@rk§h@ÐØw

Ciao a tutti.
Una domandina...qualcuno mi può spiegare perchè nell'output di esempio, al comando:

p anna 0 0 7 3
il programma risponde "Non esiste un percorso"??
Probabilmente ho sbagliato a riempire il grafico....però non mi sembra proprio...a nessuno risulta strano come a me??
Grazie mille a tutti

Io il tutto l'ho implementato in codesta guisa:
tabellone => matrice allocata dinamicamente
coppie_colori => lista dinamica contenente i due colori
agente => struttura contenente il nome e la la lista coppie_colori

Ora sono riuscito a generare un albero che partendo dall'inizio mi genera tutti i possibili cammini. Sono in ballo per eliminare dall'albero i rami che non portano a destinazione. dopodichè stenderò l'algoritmo per il percorso minimo, e quelli di fetch per i vari input.
Pensavo di usare Dijkstra ma occorrono i grafi e ormai ho realizzato l'albero...

Avrei anche io una domandina...
Se le mie coppie colori sono:
{ (giallo,rosso) ; (viola,rosso) }
posso dire giallo <=> viola o le coppie sono anche ordinate e quindi varrebbe se e solo se
{ (giallo,rosso) ; (rosso,viola) }

Ho mandato anche una mail al prof ma non ho ancora avuto risposta.
Fatemi sapere.

Monska

__________________
Che tu possa avere sempre il vento in poppa,
che il sole ti risplenda in viso,
e che il vento del destino ti porti in alto a danzare con le stelle.

cavolo bella domanda, è interessante perchè io avevo pensato di non salvarmi le coppie colore ma solamente i colori differenti

per dire ho un utente ZZ con la relazione (giallo,verde); aggiungo una nuova relazione (verde,azzurro), io avro' nella lista delle relazioni dell'utente ZZ soltanto (giallo,verde,azzurro) non salvati a coppie..

Giumarini mi dispiace ma io non ti posso aiutare per ora..

io non credo proprio siano ordinate

__________________
Khelidan

Altra piccola domandina (che tanto domandina non è, a dire il vero :oops.
Premetto che ho preso in mano il progetto ieri, quindi sono ancora decisamente in alto mare.
Io stavo pensando di usare un grafo per implementare le relazioni tra colori per ogni agente, e per il piano cartesiano (in realtà l'insieme di punti) usare un albero rb.
Solo una cosa non mi è affatto chiara....come si può, con questa soluzione, riuscire a trovare un percorso di costo ottimo tra due punti? Non vedo come sia possibile, partendo da un albero rb....qualcuno che abbia già affrontato il problema??
Grazie per le delucidazioni!

Allora io ho fatto in questo modo:
dalla matrice "scacchiera" sto passando a un albero con tutti i percorsi, dall'albero tolgo tutti i rami "secchi" e quindi ho un albero con solo i percorsi che mi portano alla soluzione.
Calcolo i costi di tutte le soluzioni e scelgo la minima.
So che "algoritmicamente" parlando non è la cosa più giusta ma per come ho implementato fino a ora devo fare così. Non posso rifare tutto!!!

Ho un'altra domandina...:
{ (giallo,verde) ; (verde,viola) ; (viola,rosso) }
giallo <=>rosso?????
cioè posso fare infiniti passaggi per andare dal giallo al rosso oppure deve essere una cosa "diretta" quindi varrebbe solo:
giallo<=>viola
verde<=>rosso

Grazie mille.

Monska

__________________
Che tu possa avere sempre il vento in poppa,
che il sole ti risplenda in viso,
e che il vento del destino ti porti in alto a danzare con le stelle.

Originally posted by Monska

Ho domandina...:
{ (giallo,verde) ; (verde,viola) ; (viola,rosso) }
giallo <=>rosso?????
cioè posso fare infiniti passaggi per andare dal giallo al rosso oppure deve essere una cosa "diretta" quindi varrebbe solo:
giallo<=>viola
verde<=>rosso

Grazie mille.

Monska

Allora a me il prof ha detto che non c'è senso nella lista. Quindi
{ (giallo,verde) ; (viola,verde) }
giallo <=> viola

Però non ho ancora avuto delucidazione sui passaggi multipli quindi quelli della domanda

Originally posted by Monska
Ho un'altra domandina...:
{ (giallo,verde) ; (verde,viola) ; (viola,rosso) }
giallo <=>rosso?????
cioè posso fare infiniti passaggi per andare dal giallo al rosso

__________________
Che tu possa avere sempre il vento in poppa,
che il sole ti risplenda in viso,
e che il vento del destino ti porti in alto a danzare con le stelle.

errori su output nel test

 
ciao.

allora ho mandato in esecuzione il programma e l'output che ottengo è il seguente:

Non esiste percorso da (0,0) a (2,0) per anna
Non esiste percorso da (0,0) a (2,0) per anna
Non esiste percorso da (0,0) a (2,0) per anna
(2
0, 0
1, 0
2, 0
)

(2
0, 3
1, 3
2, 3
3, 3
4, 3
4, 2
5, 2
5, 1
5, 0
5, -1
)

Non esiste percorso da (0,3) a (5,-1) per bruno

(3
0, 3
1, 3
2, 3
3, 3
3, 2
3, 1
3, 0
3, -1
4, -1
5, -1
)

anna: giallo = rosso
bruno: giallo != rosso

(5                  1° qui il testo dice che Non esiste percorso da (0,0) a (7,3) per anna
0, 0
0, 1
0, 2
0, 3
1, 3
2, 3
3, 3
4, 3
5, 3
6, 3
7, 3
)

Non esiste percorso da (8,-2) a (0,3) per carlo                  2° qui invece il testo dice che esiste un percorso.

carlo: rosso = verde
dario: rosso != verde

(3
8, -2
7, -2
6, -2
5, -2
4, -2
3, -2
2, -2
1, -2
0, -2
0, -1
0, 0
0, 1
0, 2
0, 3
)

(4
10, 3
9, 3
8, 3
7, 3
6, 3
5, 3
4, 3
3, 3
2, 3
1, 3
0, 3
-1, 3
-1, 2
-1, 1
-1, 0
)

Non esiste percorso da (1,1) a (3,-1) per dario                  3° anche qui dice invece che esiste un percorso.


 

mentre quello sul testo è il seguente:

Non esiste percorso da (0,0) a (2,0) per anna
Non esiste percorso da (0,0) a (2,0) per anna
Non esiste percorso da (0,0) a (2,0) per anna

( 2
0, 0
1, 0
2, 0
)

( 2
0, 3
1, 3
2, 3
3, 3
3, 2
3, 1
3, 0
3, -1
4, -1
5, -1
)

Non esiste percorso da (0,3) a (5,-1) per bruno

( 3
0, 3
1, 3
2, 3
3, 3
3, 2
3, 1
3, 0
3, -1
4, -1
5, -1
)

anna: giallo = rosso
bruno: giallo != rosso

Non esiste percorso da (0,0) a (7,3) per anna                  1°

( 5                  2°
8, -2
8, -1
8, 0
8, 1
8, 2
7, 2
6, 2
6, 3
5, 3
4, 3
3, 3
2, 3
1, 3
0, 3
)

carlo: rosso = verde
dario: rosso != verde

( 3
8, -2
7, -2
6, -2
5, -2
4, -2
3, -2
2, -2
1, -2
0, -2
0, -1
0, 0
0, 1
0, 2
0, 3
)

( 4
10, 3
9, 3
8, 3
7, 3
6, 3
5, 3
4, 3
3, 3
2, 3
1, 3
0, 3
-1, 3
-1, 2
-1, 1
-1, 0
)

( 1                  3°
1, 1
2, 1
3, 1
3, 0
3, -1
)


quindi alla fine sono solo 3 i risultati che sono diversi.

ora. per quanto riguarda il punto 1° il cammino esiste. ho fatto il controllo su carta. cosi ho risposto anche a Giumarini che aveva questo dubbio.

qualcuno di voi può controllare se vi viene anche a voi il mio stesso output.


Grazie.



DS.

__________________
by Ð@rk§h@ÐØw

Monska usi le strutture e gli algoritmi che vuoi..

se vuoi implementare con una matrice usi la matrice, ricordati però che l'uso di strutture dati poco efficcienti incide (non troppo) sul voto

è scritto anche sulla prima dispensa del prof aguzzoli..


Consigli per il progetto d’esame

-i temi riguardano problemi computazionalmente difficili: l’uso improprio delle strutture dati comporta un voto basso
- l’interfaccia utente e' quasi nulla
- la portabilita' e un fattore importante
- l’annesso tecnico e' importante
- i commenti al codice sono importanti

se si usa una matrice non so se dia il progetto sufficiente,è la cosa peggiore che si possa fare

__________________
Khelidan

ragazzi ho iniziato col codice, sto facendo la funzione input ed ho problemi con la lettura del contenuto del file di testo contenente i colori

apro il file con fopen e poi per leggere il contenuto come diavolo faccio, non riesco, a volte addirittura mi dà errore di scrittura in memoria e si blocca tutto..

voi come fate a leggere correttamente il contenuto del file..

Perchè? È la cosa più facile usare una matrice! Alla fine la alloco dinamicamente quindi zero spreco e massima accessibilità ai dati!!!
Vabbè comunque se è così darò una aggiustatina al codice!

Monska

__________________
Che tu possa avere sempre il vento in poppa,
che il sole ti risplenda in viso,
e che il vento del destino ti porti in alto a danzare con le stelle.

Se leggi bene il testo sconsiglia lui stesso l'uso di una matrice...