.dsy:it. - [Progetto] L'ape bottinatrice

Calendar

Members

Faq

Logout

.dsy:it. : Powered by vBulletin version 2.3.1

.dsy:it. > Didattica > Corsi A - F > Algoritmi e strutture dati > [Progetto] L'ape bottinatrice

Pages (18): « 1 2 [3] 4 5 6 7 » ... Last »

Last Thread Next Thread

Author

Thread Expand all | Contract all

Jaco

.novellino.

User info:

Registered: Jun 2004
Posts: 4 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno: 2...3
Time Online: 0:44:10 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

premetto che non ho ancora avuto molto tempo da dedicarci ma ora,d'accordo con maynard, proverò con un semplice albero.Non so se può essere superfluo ribadirlo(per alcuni posts) ma il piano esiste in funzione delle strutture dati che contengono i fiori e i campi,di per sè non è un problema implementare il piano in sè.

16-09-2005 16:24

Click here to Send Jaco a Private Message

maynard80

.novellino.

User info:

Registered: Jul 2007
Posts: 3 (0.00 al dì)
Location: Milano (e non interland, tendo a precisare)
Corso: informatica
Anno: SESTO
Time Online: 12 Days, 14:28:38 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by Jaco
premetto che non ho ancora avuto molto tempo da dedicarci ma ora,d'accordo con maynard, proverò con un semplice albero.Non so se può essere superfluo ribadirlo(per alcuni posts) ma il piano esiste in funzione delle strutture dati che contengono i fiori e i campi,di per sè non è un problema implementare il piano in sè.

Alberi RB non semplici alberi

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

16-09-2005 16:37

Click here to Send maynard80 a Private Message

drakend

.grande:maestro.

User info:

Registered: Oct 2002
Posts: 1857 (0.22 al dì)
Location:
Corso:
Anno:
Time Online: 11 Days, 16:15:18 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by maynard80
non capisco, la struttura dati è indipendente da queste cose, i nodi sono ordinati in base alla chiave (x,y) se un nodo non esiste non esiste il rispettivo fiore.
quando scorri l'albero per trovare il cammino sarà li e solo li che tra i parametri del cammino dici che sono permessi alcuni spostamenti (3 spostamenti) e memorizzi il percorso in una struttura di supporto dove andrà a finire solo il cammino prescelto.

Cioè tu vuoi far una specie di "albero di adiacenza"? Cioè un albero, rb o meno che sia, in cui in ogni nodo memorizzi una lista di puntatori agli elementi raggiungibili a partire da quel nodo?
Se è così ci avevo pensato pure io, però tieni conto di alcune cose:
1) devi farti un albero per ogni campo, a meno di stratagemmi particolari, e mettertelo in una lista.
2) gli algoritmi che calcolano i cammini massimi necessitano comunque di liste di adiacenza come input, per cui devi calcolarti le liste di adiacenza dalla struttura che usi ogni volta...

16-09-2005 17:21

Click here to Send drakend a Private Message

Frigging

.primate.

User info:

Registered: Mar 2005
Posts: 69 (0.01 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 8:27:03: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

... Rieditato il post... avevo dimenticato i che si poteva solo muovere in alto

Last edited by Frigging on 19-09-2005 at 07:30

16-09-2005 17:49

maynard80

.novellino.

Post actions:

Edit | Report | IP: Logged

Originally posted by drakend
Cioè tu vuoi far una specie di "albero di adiacenza"? Cioè un albero, rb o meno che sia, in cui in ogni nodo memorizzi una lista di puntatori agli elementi raggiungibili a partire da quel nodo?
Se è così ci avevo pensato pure io, però tieni conto di alcune cose:
1) devi farti un albero per ogni campo, a meno di stratagemmi particolari, e mettertelo in una lista.
2) gli algoritmi che calcolano i cammini massimi necessitano comunque di liste di adiacenza come input, per cui devi calcolarti le liste di adiacenza dalla struttura che usi ogni volta...

no no, semplicemente una struttura che memorizzi i pesi dei nodi dei fiori che esistono (l'ordinamento non ha importanza) ma essendo un rb albero il costo di ricerca sarà sempre log(n).
che me ne frega di sapere nel grafo come sono collegati, una volta che ho le coordinate xy come chiave so dove sono senza dover per forza mantenere nel grafo stesso la forma del prato.

una volta che so che in (1,1) c'è un nodo e voglio andare in (2,3) l'algoritmo (opportunemente definiti limiti di muovimento in X e Y che vanno controllati ricorsivamente) sa che può passare solo per (1,1)(1,2)(2,3) oppure (1,1)(2,2)(2,3), se queste strade esistono entrambe (sono presenti i nodi con le rispettive chiavi) sceglie quello con il peso maggiore (calcolato durante il viaggio stesso), diversamente non esiste un viaggio possibile.

in + tale algoritmo deve tenere traccia dei cammini esistenti per utilizzarli eventualmente in altri viaggi dove sono compresi, ma questa è un'aggiuta

l'albero RB mi serve solo per memorizzare i nodi esistenti e accedervi in maniera efficiente.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Last edited by maynard80 on 16-09-2005 at 18:02

16-09-2005 17:59

drakend

.grande:maestro.

User info:

Registered: Oct 2002
Posts: 1857 (0.22 al dì)
Location:
Corso:
Anno:
Time Online: 11 Days, 16:15:18 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by Frigging
Non possiamo usare, secondo me, gli algoritmi noti per il calcolo del cammino di peso massimo, in quanto prendendo in considerazione di utilizzare l'algoritmo di Floyd-Warshall che e' l'unico che prende in considerazione pesi negativi, non e' assicurata cmq la corettezza dell'algoritmo nel caso in cui esistano circuiti negativi.

Cmq secondo me questo progetto non e' poi cosi' facile implementarlo con una decente complessita'.

Capitolo 25.4 DAG-Shortest-Path, dal momento che il grafo formato dai vari fiori è orientato ed aciclico (si sale sempre verso l'alto). Alla fine del paragrafo c'è peraltro indicato il modo di calcolare i cammini critici: ah ovviamente supporta i pesi negativi, dal momento che sono presenti nel relativo esempio.

16-09-2005 19:25

Frigging

.primate.

User info:

Registered: Mar 2005
Posts: 69 (0.01 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 8:27:03: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by drakend
Capitolo 25.4 DAG-Shortest-Path, dal momento che il grafo formato dai vari fiori è orientato ed aciclico (si sale sempre verso l'alto). Alla fine del paragrafo c'è peraltro indicato il modo di calcolare i cammini critici: ah ovviamente supporta i pesi negativi, dal momento che sono presenti nel relativo esempio.

Scusa ... hai pienamente ragione ... e' che sono fuso mi ero completamente dimenticato che si poteva solo salire... ho buttato tre ore per nulla oggi pome uff!!!

Grazie mille

16-09-2005 21:26

Shimoda

.consigliere.

User info:

Registered: Feb 2003
Posts: 118 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno: 3
Time Online: 1 Day, 12:30:16 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

A prescindere dall'applicazione e quindi dal contesto dell'attuale progetto..
Che differenza c'è a livello pratico tra una lista ordinata e un RBAlbero?
E' solo una questione di efficienza. Se la lista è ordinata sia l'inserimento sia la ricerca nel caso peggiore hanno complessità O(n) mentre per l'RBAlbero è O(lg n).
E su input grandi non è poco.. la ricerca tra 10^9 elementi in un RBAlbero avviene nel caso peggiore in 30 passaggi contro i 10^9 della lista...
Tralaltro l'albero può essere (visto) usato allo stesso modo di una lista tramite le funzioni successivo() e precedente().

A chi ha scritto come ordinare i punti con due coordinate direi che si può fare in base all'ascissa, e a parità di ascissa in base all'ordinata.

__________________
"What the Caterpillar calls the end of the World,
the Master calls a Butterfly"
(Il manuale del messia, Illusioni, Richard Bach)

17-09-2005 02:21

Click here to Send Shimoda a Private Message

drakend

.grande:maestro.

User info:

Registered: Oct 2002
Posts: 1857 (0.22 al dì)
Location:
Corso:
Anno:
Time Online: 11 Days, 16:15:18 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by Shimoda
A chi ha scritto come ordinare i punti con due coordinate direi che si può fare in base all'ascissa, e a parità di ascissa in base all'ordinata.

Perché in base all'ascissa? Dovrebbe essere in base all'ordinata e, a parità di ordinata, in base all'ascissa.

17-09-2005 07:39

Shimoda

.consigliere.

User info:

Registered: Feb 2003
Posts: 118 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno: 3
Time Online: 1 Day, 12:30:16 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by Shimoda
A prescindere dall'applicazione e quindi dal contesto dell'attuale progetto..

Era solo un esempio su come gestire le 2 coordinate

__________________
"What the Caterpillar calls the end of the World,
the Master calls a Butterfly"
(Il manuale del messia, Illusioni, Richard Bach)

17-09-2005 16:24

drakend

.grande:maestro.

User info:

Registered: Oct 2002
Posts: 1857 (0.22 al dì)
Location:
Corso:
Anno:
Time Online: 11 Days, 16:15:18 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by Shimoda
Era solo un esempio su come gestire le 2 coordinate

Sì hai ragione, sono io che mi sono confuso: nell'albero tu puoi stabilire l'ordine che ti pare per i punti, che non necessariamente rifletta quello del piano cartesiano.
Ad ogni modo:

Qualcuno conosce un programma per disegnare RB alberi?!? Mi spiego: gli do in input la struttura dei nodi dell'albero (anche con una stringa in formato specifico, non è un problema) e lui me lo disegna, con i pallini e gli archi di collegamento, magari se ci si può specificare un etichetta è meglio!

17-09-2005 17:43

maynard80

.novellino.

Post actions:

Edit | Report | IP: Logged

a rigor di logica gli alberi binari sono efficaci come gli RB Alberi ed efficienti uguali, gli alberi RB sono bilanciati, ma i B Alberi sono molto + facili da implementare.

(questo me lo ha fatto notare Shimoda)

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

17-09-2005 19:29

drakend

.grande:maestro.

User info:

Registered: Oct 2002
Posts: 1857 (0.22 al dì)
Location:
Corso:
Anno:
Time Online: 11 Days, 16:15:18 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by maynard80
a rigor di logica gli alberi binari sono efficaci come gli RB Alberi ed efficienti uguali, gli alberi RB sono bilanciati, ma i B Alberi sono molto + facili da implementare.

(questo me lo ha fatto notare Shimoda)

Beh sai ci sono gli algoritmi già pronti di AlgoTeam: puoi benissimo basarti su quelli e personalizzare.

17-09-2005 20:59

maynard80

.novellino.

Post actions:

Edit | Report | IP: Logged

Originally posted by drakend
Beh sai ci sono gli algoritmi già pronti di AlgoTeam: puoi benissimo basarti su quelli e personalizzare.

beh bisogna conoscere bene il codice che si presenta,e poi per trovare errori ed anomalie...

cmq sia io degli alberi RB non ho mai capito come si gestiscono le rotazioni ed i cambi di colore....

in + ancora non riesco a racapezzarmi su quale sia la procedura per trovare il cammino migliore.... trovare semplicemente uno per uno i cammini e poi vedere quello con il peso maggiore mi pare una ca@@ata

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

17-09-2005 21:16

Jaco

.novellino.

User info:

Registered: Jun 2004
Posts: 4 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno: 2...3
Time Online: 0:44:10 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Dopo aver creato la struttura fiore e un'altra tipo lista che lo contenga sto cercando di implementare una tabella hash tipo a matrice con due array,cioè con una funzione hash che mi detetermini la locazione in base a x e y.in caso di collisione inserisco in testa nella lista.
..qualcuno mi dice che ne pensa?thx

18-09-2005 18:10

All times are GMT. The time now is 02:35.

Pages (18): « 1 2 [3] 4 5 6 7 » ... Last »

Last Thread Next Thread

Show Printable Version |

Email this Page |

Subscribe to this Thread |

Add to Bookmarks

Forum Jump:

Rate This Thread:

Forum Rules:

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON

Pagina generata in 0.058 seconds (74.19% PHP - 25.81% MySQL) con 24 query.