[C] Algoritmi e Strutture dati

[TorpedoBlu]

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?

[TorpedoBlu]

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?

[cionci]

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

[TorpedoBlu]

mhmm nelle specificche del progetto scondigliano una matrice

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

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.

[cionci]

La matrice che ho scritto sopra è per un prato...non per il piano !!!
Lì viene sconsigliata la matrice per il piano...

[TorpedoBlu]

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.

[cionci]

Originariamente inviato da TorpedoBlu

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.

Cancellazione di che ?!?!? Di un prato ? Ha un tempo O(n) con il metodo che ti dico io...

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

[cionci]

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

[TorpedoBlu]

Originariamente inviato da cionci

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

ti ringrazio tanto per i chiarimenti

ora però mi risulta difficile capire come calcolare il cammino migliore...

[cionci]

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 ?

[TorpedoBlu]

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

[cionci]

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

[TorpedoBlu]

Originariamente inviato da cionci

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

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?

[TorpedoBlu]

up

[TorpedoBlu]

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 è

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;

(tra l'altro non so come inserire il valore del dato, qui vedo solo la chiave ed il colore)

qualche anima pia che guarda il file in allegato e mi dice dove effettuare le modifiche

[TorpedoBlu]

up