[Algoritmi] problemi con un progetto d'esame

[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


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

[TorpedoBlu]

up

[Scoperchiatore]

Praticamente ti divide le funzioni lui...

Cmq, a prima vista non mi sembrano alberi ma grafi, tra l'altro totalmente connessi.

Viaggio dovrà fare backtracking sulla posizione scelta. Io la farei ricorsiva, mi sembra più facile.

Bisogna ragionare se il problema presenta l'ottimalità locale. Secondo te cell'ha?
Ottimalità locale = se da un punto p prendo sempre il massimo vicino, alla fine arrivo al percorso migliore? Oppure ci potrebbero essere dei casi in cui, prendendo un valore minore del massiom fra i vicini, riesco a ottenere un cammino ancora più vantaggioso?

Intanto prova a pensare a questo.

[TorpedoBlu]

no l'ottimalità locale no è presente

[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