.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Progetto] L'ape bottinatrice (http://www.dsy.it/forum/showthread.php?threadid=21329)

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è.

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è.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

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.

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

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...

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

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'.

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.

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)

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.

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

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

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

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 !

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)

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

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

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