|
|
|
![]() |
|
Strumenti |
![]() |
#1 |
Senior Member
Iscritto dal: Sep 2003
Città: Milano
Messaggi: 4623
|
[C] Algoritmi e Strutture dati
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 qualcuno ne mastica?
__________________
Ho trattato con : lahiri, czame, RC, allXXX, dfruggeri, JMM, Paperone, xej, Pappez, iperfly, Red81, Playmake, ryan78, Rob66, XP2200, Peach1200, faberjack, Stewie82, supermario_bros, hft500, Axelscorpio, pipes lee, Piccolospazio, RohanKish, miki66, kabira85 |
![]() |
![]() |
![]() |
#2 |
Senior Member
Iscritto dal: Sep 2003
Città: Milano
Messaggi: 4623
|
dunque, per quanto riguarda la struttura dei prati non so ancora cosa utilizzare, è chiaro che sovraposti o meno no ci interessa molto (quando inserisci un prato se nessuno dei fiori gia esiste non è sovrapposto a nessuno e incremento la variabile globale di 1, se è sovrapposto qualche fiore il numero di campi non aumenta e il peso di quel fiore è sommato a quello gia esistente in quel punto)
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. voi che dite?
__________________
Ho trattato con : lahiri, czame, RC, allXXX, dfruggeri, JMM, Paperone, xej, Pappez, iperfly, Red81, Playmake, ryan78, Rob66, XP2200, Peach1200, faberjack, Stewie82, supermario_bros, hft500, Axelscorpio, pipes lee, Piccolospazio, RohanKish, miki66, kabira85 |
![]() |
![]() |
![]() |
#3 |
Senior Member
Iscritto dal: Apr 2000
Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29
Messaggi: 53971
|
Per i prati userei una matrice...
Ad esempio: struct prato { int x0; int y0; int x1; int y1; int **fiori; }; struct lista_prati { struct prato *p; struct lista_prati next; }; Ovviamente fiori sarà una matrice allocata dinamicamente... Trovare la qualità di un fiore ti fai una funzione int fiore(int x, int y); che scorrerà tutti i prati e se x e y appartengono ad un prato (anche più di uno) si somma il valore contenuto nella matrice dei fiori al totale... Per il cammino...fare un albero non è male, ma attento ad usare la ricorsione...i cammini possibili sono tanti... |
![]() |
![]() |
![]() |
#4 |
Senior Member
Iscritto dal: Sep 2003
Città: Milano
Messaggi: 4623
|
mhmm nelle specificche del progetto scondigliano una matrice
Codice:
Si richiede di implementare una struttura dati effciente che permetta di eseguire le operazioni seguenti (si tenga presente che la minima porzione rettangolare di piano contenente tutti i prati può essere molto grande rispetto al numero di prati e fiori presenti nel piano, quindi non e' sicuramente efficiente rappresentare il piano mediante una matrice). 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.
__________________
Ho trattato con : lahiri, czame, RC, allXXX, dfruggeri, JMM, Paperone, xej, Pappez, iperfly, Red81, Playmake, ryan78, Rob66, XP2200, Peach1200, faberjack, Stewie82, supermario_bros, hft500, Axelscorpio, pipes lee, Piccolospazio, RohanKish, miki66, kabira85 |
![]() |
![]() |
![]() |
#5 |
Senior Member
Iscritto dal: Apr 2000
Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29
Messaggi: 53971
|
La matrice che ho scritto sopra è per un prato...non per il piano !!!
Lì viene sconsigliata la matrice per il piano... |
![]() |
![]() |
![]() |
#6 |
Senior Member
Iscritto dal: Sep 2003
Città: Milano
Messaggi: 4623
|
mi consigli di utilizzare una matrice per ogni prato? mhmm alla fine potrei utilizzare un unica struttura per tutti i prati (mantenendo una variabile globale che mi dica quanti Campi)
una matrice fatta nel modo che mi dici ha cmq un tempo di ricerca\inserimento\cancellazione superiore al RB-Albero, semplicemente sono indeciso per quanto riguarda l'algoritmo di ricerca del cammino ottimo.
__________________
Ho trattato con : lahiri, czame, RC, allXXX, dfruggeri, JMM, Paperone, xej, Pappez, iperfly, Red81, Playmake, ryan78, Rob66, XP2200, Peach1200, faberjack, Stewie82, supermario_bros, hft500, Axelscorpio, pipes lee, Piccolospazio, RohanKish, miki66, kabira85 |
![]() |
![]() |
![]() |
#7 | |
Senior Member
Iscritto dal: Apr 2000
Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29
Messaggi: 53971
|
Quote:
lista_prati è una lista che contiene tutti i prati... Se ti viene data una coordinata cancelli tutti i prati che includono quella coordinata...basta scorrere la lista (O(n)) e verificare, prato per prato, se la coordinata è cmprese nelle coordinate del prato (O(1)) |
|
![]() |
![]() |
![]() |
#8 |
Senior Member
Iscritto dal: Apr 2000
Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29
Messaggi: 53971
|
Qualsiasi operazione sulla lista dei prati di inserimento, cancellazione, calcolo della qualità di un fiore ha un tempo max O(n)...e si può fare banalmente in modalità non ricorsiva...e sono operazioni semplicissime da realizzare, max 6-7 istruzioni...
|
![]() |
![]() |
![]() |
#9 | |
Senior Member
Iscritto dal: Sep 2003
Città: Milano
Messaggi: 4623
|
Quote:
![]() ora però mi risulta difficile capire come calcolare il cammino migliore...
__________________
Ho trattato con : lahiri, czame, RC, allXXX, dfruggeri, JMM, Paperone, xej, Pappez, iperfly, Red81, Playmake, ryan78, Rob66, XP2200, Peach1200, faberjack, Stewie82, supermario_bros, hft500, Axelscorpio, pipes lee, Piccolospazio, RohanKish, miki66, kabira85 |
|
![]() |
![]() |
![]() |
#10 |
Senior Member
Iscritto dal: Apr 2000
Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29
Messaggi: 53971
|
Spiegami un po' meglio... Devi cercare un cammino minimo... Se ci sono più cammini minimi a parità di passi devi trovare quello con qualità massima ?
|
![]() |
![]() |
![]() |
#11 |
Senior Member
Iscritto dal: Sep 2003
Città: Milano
Messaggi: 4623
|
dunque si, dal punto di vista della lunghezza del cammino, visto che ci si può muovere solo in diagonale e o verso l'alto (nord-est/nord/nord-ovest), i cammini esistenti tra 2 punti non potendo tornare indietro sono tutti uguali.
quindi se ci sono 1 o + cammini deve scegliere quello con il peso maggiore (la somma dei pesi di ogni fiore).
__________________
Ho trattato con : lahiri, czame, RC, allXXX, dfruggeri, JMM, Paperone, xej, Pappez, iperfly, Red81, Playmake, ryan78, Rob66, XP2200, Peach1200, faberjack, Stewie82, supermario_bros, hft500, Axelscorpio, pipes lee, Piccolospazio, RohanKish, miki66, kabira85 |
![]() |
![]() |
![]() |
#12 |
Senior Member
Iscritto dal: Apr 2000
Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29
Messaggi: 53971
|
Hai mai sentito parlare di back tracking ?
Allora...parti dal nodo iniziale...e scegli i possibili nodi destinazione... Un nodo è ammissibile se c'è un fiore sopra (non so se questa supposizione è giusta)... Per tutti i nodi ammissibili calcoli la distanza geometrica fra il nodo ammissibile e quello di destinazione... Ti muovi sul nodo a distanza geometrica minore... Se ad un certo punto da un nodo non iresci a trovare un nodo ammissibile che non sia già stato visitato elimini torni al nodo precedente ed elimini il nodo corrente dal percorso... Arrivato al nodo finale ti memorizzi il percorso fatto, la somma dei fiori e il numero di passi fatti... Torni indietro all'ultimo nodo ammissibile, lo elimini e torni ancora al nodo ammissibile precedente...scegli di muoverti in un nodo ammissibile che ha distanza minima fra quelli ammissibili e così via... Ogni volta che arrivi al nodo finale se il numero dei passi è minore di quello precedente (se è uguale a discriminare è la somma dei fiori) memorizzi il percorso e togli l'ottimo precedente... Attenzione che un nodo può essere attraversato da percorsi diversi... Ad esempio due percorsi diversi possono avere gli stessi nodi tranna che per un nodo diverso... |
![]() |
![]() |
![]() |
#13 | |
Senior Member
Iscritto dal: Sep 2003
Città: Milano
Messaggi: 4623
|
Quote:
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?
__________________
Ho trattato con : lahiri, czame, RC, allXXX, dfruggeri, JMM, Paperone, xej, Pappez, iperfly, Red81, Playmake, ryan78, Rob66, XP2200, Peach1200, faberjack, Stewie82, supermario_bros, hft500, Axelscorpio, pipes lee, Piccolospazio, RohanKish, miki66, kabira85 |
|
![]() |
![]() |
![]() |
#14 |
Senior Member
Iscritto dal: Sep 2003
Città: Milano
Messaggi: 4623
|
up
__________________
Ho trattato con : lahiri, czame, RC, allXXX, dfruggeri, JMM, Paperone, xej, Pappez, iperfly, Red81, Playmake, ryan78, Rob66, XP2200, Peach1200, faberjack, Stewie82, supermario_bros, hft500, Axelscorpio, pipes lee, Piccolospazio, RohanKish, miki66, kabira85 |
![]() |
![]() |
![]() |
#15 |
Senior Member
Iscritto dal: Sep 2003
Città: Milano
Messaggi: 4623
|
qui c'è il codice degli alberiRB, vorrei modificarlo per avere la possibilità di gestirlo con una coppia di chiavi (ascissa e ordinata) e non una sola
la struttura principale per capirci è Codice:
typedef int key; typedef enum { red, black } color; struct rbnode { key v; color c; struct rbnode *left, *right, *up; }; typedef struct rbnode rbnode; typedef struct { rbnode *root, *nil; } rbtree; qualche anima pia che guarda il file in allegato e mi dice dove effettuare le modifiche
__________________
Ho trattato con : lahiri, czame, RC, allXXX, dfruggeri, JMM, Paperone, xej, Pappez, iperfly, Red81, Playmake, ryan78, Rob66, XP2200, Peach1200, faberjack, Stewie82, supermario_bros, hft500, Axelscorpio, pipes lee, Piccolospazio, RohanKish, miki66, kabira85 |
![]() |
![]() |
![]() |
#16 |
Senior Member
Iscritto dal: Sep 2003
Città: Milano
Messaggi: 4623
|
up
__________________
Ho trattato con : lahiri, czame, RC, allXXX, dfruggeri, JMM, Paperone, xej, Pappez, iperfly, Red81, Playmake, ryan78, Rob66, XP2200, Peach1200, faberjack, Stewie82, supermario_bros, hft500, Axelscorpio, pipes lee, Piccolospazio, RohanKish, miki66, kabira85 |
![]() |
![]() |
![]() |
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 07:30.