.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [PROGETTO] "Mappe 2" (http://www.dsy.it/forum/showthread.php?threadid=23982)

Originally posted by darkAntAreS
io ho fatto sottopercorso!!!
un consiglio: NON fare l'errore di calcolarti ogni sottopercorso da ogni punto..ragiona su come è fatto un sottopercorso e da dove deve, per forza di cose, partire per essere tale...
nel caso peggiore a me viene (nlogn)/2, ma bisogna essere proprio sfigati...e nel caso medio viene circa n/2

per quelli che hanno gia fatto la struttura base.. potete dirmi se il ragionamento che ho in testa regge e come la vedete voi?

avevo in mente 2 strutture
- un albero binario per i i punti a cui vengono variati i valori tramite la funzione "valore"
- un grafo che memorizza il percorso della mappa in base alla specifica e 1 algoritmo del cammino minimo.

non riesco ancora a capire cosa associare al piano e alla mappa..

mettiamo che faccio una funzione con il prototipo Piano new_piano(int m, int n, char *nome);
cosa deve ritornarmi alla struttura piano? tutti i valori dei punti del piano è da escludere..
l'unica cosa che mi viene in mente è fagli tornare i valori dei punti presi da file e memorizzati in un array e magari la struttura che contiene le varie mappe del piano..

riguardo appunto la struttura che raggruppa tutte la mappe posso benissimo usare o una lista o un array.

e infine la mappa sarà appunto un grafo.

se qualcuno mi illumina la retta via gliene sarei grato! grazie

Originally posted by Simeon
Mmm forse ho capito, anche quei tempi li possono essere un'indizio .

Quindi tu hai finito tutto o devi fare riduci?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Originally posted by maynard80
illumina anche chi non ha capito..please

Originally posted by Simeon
Ma forse intendeva il fatto che per un percorso pi ... pj i dev'essere i>= j e quindi non devi guardarti tutti i punti... boh! Bluffavo, non lo so ancora perche sto rifinendo riduci()

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Originally posted by maynard80
e mica è vero, se il punto di indice i e quello di indice j sono 2 punti adiacenti??nonostante magari nel percorso della mappa non c'è un hop che li collega..

bhe, senza sbilanciarmi troppo

considerate che, se cercate i percorsi a partire da un punto P(i) e P(i-1) è >=0, bhe, in un ciclo precedente avreste potuto controllare i percorsi da P(i-1) che sono sicuramente maggiori di quelli da P(i)...

riduci l'ho fatto, ma ci mette troppo, quindi sto ragionando per velocizzarlo un po'...e per farlo sto pensando ad un albero come appoggio (a sinistra se vai in una direzione, a destra se vai verso l'altra...)

per la struttura di memorizzazione delle mappe l'albero è ottimo, visto che, se lo si ordina sui nomi delle mappe, la ricerca è molto veloce...l'unico problema si incontra con l'eliminazione di un nodo interno, ma basta leggere gli esempi del libro che lo spiegano benissimo

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Originally posted by darkAntAreS

riduci l'ho fatto, ma ci mette troppo, quindi sto ragionando per velocizzarlo un po'...

bhe, io non mi sto confrontando coi tempi del mio processore...è ovvio che se piazzo un algoritmo come il mio attuale riduci, a meno che non metto i 2 punti a distanze immani, la differenza di tempo non è apprezzabile...più che altro sto facendo i calcoli della complessità dei tempi degli algoritmi...
quindi il discorso di velocizzare le cose si basa sull'algoritmo, non sull'implementazione...

forse ho trovato il metodo per ridurlo a m*n (con m e n intese come le differenze tra le coordinate dei punti)

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Originally posted by darkAntAreS
bhe, io non mi sto confrontando coi tempi del mio processore...è ovvio che se piazzo un algoritmo come il mio attuale riduci, a meno che non metto i 2 punti a distanze immani, la differenza di tempo non è apprezzabile...più che altro sto facendo i calcoli della complessità dei tempi degli algoritmi...
quindi il discorso di velocizzare le cose si basa sull'algoritmo, non sull'implementazione...

forse ho trovato il metodo per ridurlo a m*n (con m e n intese come le differenze tra le coordinate dei punti)

domanda stupidissima e veloce:
se uso un albero binario di ricerca e come chiavi uso le coordinate x,y di un punto come faccio a discriminare le chaivi per farle andare o nel sottoalbero sinistro o quello destro?

Originally posted by tandrea85
domanda stupidissima e veloce:
se uso un albero binario di ricerca e come chiavi uso le coordinate x,y di un punto come faccio a discriminare le chaivi per farle andare o nel sottoalbero sinistro o quello destro?

Originally posted by YoMo
Io ho ordinato in base alla coordinata x ed, in caso di uguaglianza, in base alla y. Non sembrano esserci problemi, neanche cn le rotazioni (ho usato un rbtree).

Ma se per trovare il sottopercorso migliore io scandisco l'array che contiene il percorso UNA SOLA VOLTA... è tempo lineare vero ?

Se si, e se il mio algoritmo funziona, ho trovato una soluzione in tempo lineare.

Dubito molto fortemente della seconda ipotesi però...

se riesci si, è tempo lineare...ma non riesco a immaginarlo...bhe, se funziona sei un grande

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"