PDA

Visualizza la versione completa : [ALGORITMO] Alberi binari, liste di adiacenze, calcolo dei cammini...


torpedoblu
18-09-2005, 21:55
per l'universitÓ ci hanno dato da fare un progetto per il corso di algoritmi

http://homes.dsi.unimi.it/~fiorenti/labalg04/ape.pdf

si tratta di usare strutture dati tipo alberi binari, liste di adiacenze, algoritmi per il calcolo dei cammini


il cammino Ŕ sempre lungo come la differenza Y1-Y0, da ogni fiore ci si sposta al + in tre altri fiori ui verticale, questo mi induce a pensare che tutti i cammini possibili siano un albero ternario e quello migliore sia quello con la foglia + pesante.


il collega con cui faccio il progetto Ŕ convinto nell'usare gli RB alberi in quanto sono efficienti e per qualsiasi operazione impiegano un tempo log(n)...

ma l'implementazione di un RB albero mi spaventa...

per quanto riguarda poi l'algoritmo per il calcolo del cammino migliore non saprei cosa usare.

dunque le sole mosse ammissibili sono
X1=X0 || X1=X0+1 || X1=X0-1
Y1=Y0+1

quindi ci si muove solo in 3 direzioni (diagonale destra|sinistra o verticale)
per questo pensavo ad un albero ternario per l'insieme dei cammini possibili

a questo punto se ci sono + di un cammino possibile bisogna scegliere quello con il peso maggiore.

ammesso di fare una lista di liste, come Ŕ possibile?


sono confuso

Matteo982
20-09-2005, 22:41
io non so che dirti...devo giusto fare l'esame di algoritmi complementi venerdý ma purtroppo sono su una nave che fa acqua da tutte le parti...sicuramente altri ne sapranno di pi¨! :cry:

Ciao. :ciauz:

Loading