.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Progetto] L'ape bottinatrice (http://www.dsy.it/forum/showthread.php?threadid=21329)

..la necessità di utilizzare la sentinella è per la gestione degli alberi RB, ho scelto quella come struttura, mi sbaglio?

Se usi l'RB e' necessaria la sentinella in quanto devi rappresentare le foglie NIL come nere, altrimenti non rispetteresti una delle proprieta' del red-black tree.

Originally posted by Frigging
Se usi l'RB e' necessaria la sentinella in quanto devi rappresentare le foglie NIL come nere, altrimenti non rispetteresti una delle proprieta' del red-black tree.

quindi nessuno ha fatto come me... lo deduco dal deserto di risposte! cmq anche io userò un albero e mi sbatto ricorsivamente a cercare i cammini, alla fine forse è mejo...

domanda: vi sbattete tutti a fare gli RB? perchè se si riuscisse a mettere bene le chiavi in un albero binario secondo me può venire lo stesso bilanciato e quindi rimanere O(lgn)... cmq la domanda vera è come disporreste le chiavi? in base all'ordinata e in caso di parità in base all'ascissa o a caso e si spera nel bilanciamento?

Siccome il nodo NIL mi sembra OK come soluzione mi chiedo che valori potrei dare alle variabili di tipo int X e Y.. per esempio..

io ho seri problemi con ste' chiavi... sto usando RB... io cerco di inserire a nel sottoalbero a sx se l'ascissa è minore e nel sottoalbero dx se è maggiore, se l'ascissa è uguale allora vado a sx se l'ordinata è minore e a dx se è maggiore...
così però non mi va!!! help...please...

Originally posted by drakend
Non è vero che è essenziale usare queste sentinelle. Infatti il libro dice, a pagina 255, che:

"Per semplificare nel codice sorgente la gestione dei casi limite si usa la sentinella invece del valore NIL."

La sentinella semplifica la gestione dei casi limite nella funzione di cancellazione, perché fa scomparire alcune condizioni dai vari if, tutto qua. Infatti io ho preso l'implementazione degli alberi RB dal algoteam e l'ho adattata togliendo le sentinelle e usando il valore NULL perché mi risulta più semplice la comprensione.

PS Ovviamente genero alberi RB rispettosi delle quattro proprietà...

Qualcuno si esprimerebbe su questo?:
Visto che per la determinazione dei cammini devo comunque usare una lista di adiacenza ho pensato di usare direttamente una lista(ogni elemento è un vertice del grafo)con connesse delle altre liste di adiacenza.In questo modo avrei un'unica struttura per contenere i dati(piuttosto che un albero o altro) e per interrogarli..certo che la complessità è n,ed è un pò tanto....ma sto progetto è un casino.Thanks

cristiano: ciao anche io volevo usare un grafo, ma quando mi sono trovato di fronte alla necessità di usare liste per memorizzare i vertici da cui partono le adiacenze ho desistito... cmq la complessità è n per l'uso di liste, ma se poi ci applichi algoritmi efficienti magari sono migliori di quelli che cercano punto per punto i fiori per eseguire i cammini ricorsivamente su strutture più efficienti della tua...
io cmq uso un RB ormai... non so, mi torna voglia di grafoooo!

Quindi pensi di usare un RB per la complessità lg n contro quella n della lista?Oppure perchè la rappresentazione di grafi è un casino?(infatti sto cercando in rete del codice da personalizzare perchè da solo è un macello).
Mi pare che l'unico vantaggio che ne avrei sarebbe la quantità minore di mem. poichè uso la lista di aiacenza sia per contenere i dati che per costruire cammini.Con un'altra struttura dovrei cercare e inserire lì ma devo cmq creare una lista di adiacenza.....confusione alla n!!!
Cmq grazie.

si anche io mi sono "rassegnato" agli alberi... perchè un grafo lo sceglievo perchè mi dava la topologia del piano ed era facile trovare i cammini... ma che sbattimento implementarlo senza array...

Se qualcuno ha un'idea per i campi... la posti please... io per adesso sto cercando di vedere se posso calcolarli mettendo un campo apposito in ogni fiore che ne da l'appartenenza ad un determinato campo, assegnando il valore da un contatore di campi che viene incrementato. Il problema di questo approccio è quando inserisco un prato che UNISCE DUE CAMPI DISTINTI (come appunto capita per i primi tre prati dell'esempio di input del testo!!)

sarebbe un problema di connettività, quindi potrebbe essere risolto con un algoritmo union-find.... adesso spulcio il Cormen

Ho l'impressione che l'algoritmo per la ricerca dei cammini minimi da una singola sorgente di Dijkstra sia perfettamente adattabile al nostro scopo con poche piccole modifiche..

__________________
"What the Caterpillar calls the end of the World,
the Master calls a Butterfly"
(Il manuale del messia, Illusioni, Richard Bach)

cmq Per i grafi sto usando delle liste,non array.riguardo il problema dell'appartenenza ad un campo ho letto qualcosa cap. 22 del cormen,dove un elemento dell'insieme è "eletto" rappresentante e si fa riferimento a quello...per l'implementazione per ora BHO!.

Shimoda quindi tu hai usato un grafo??

Originally posted by eskimo
Shimoda quindi tu hai usato un grafo??

__________________
"What the Caterpillar calls the end of the World,
the Master calls a Butterfly"
(Il manuale del messia, Illusioni, Richard Bach)