Paolo74GRS

.primate.

User info:

Registered: Mar 2003
Posts: 71 (0.01 al dì)
Location: Bergamo
Corso: Informatica
Anno: > 3
Time Online: 2 Days, 11:55:02: [...]
Status: Offline

Post actions:

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

Frigging

.primate.

User info:

Registered: Mar 2005
Posts: 69 (0.01 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 8:27:03: [...]
Status: Offline

Post actions:

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.

drakend

.grande:maestro.

User info:

Registered: Oct 2002
Posts: 1857 (0.22 al dì)
Location:
Corso:
Anno:
Time Online: 11 Days, 16:15:18 [...]
Status: Offline

Post actions:

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.

eskimo

.illuminato.

User info:

Registered: Jul 2003
Posts: 156 (0.02 al dì)
Location: Milano
Corso: informatica
Anno: 3datroppotempoormai
Time Online: 1 Day, 22:23:46 [...]
Status: Offline

Post actions:

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?

Paolo74GRS

.primate.

User info:

Registered: Mar 2003
Posts: 71 (0.01 al dì)
Location: Bergamo
Corso: Informatica
Anno: > 3
Time Online: 2 Days, 11:55:02: [...]
Status: Offline

Post actions:

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

eskimo

.illuminato.

User info:

Registered: Jul 2003
Posts: 156 (0.02 al dì)
Location: Milano
Corso: informatica
Anno: 3datroppotempoormai
Time Online: 1 Day, 22:23:46 [...]
Status: Offline

Post actions:

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

Frigging

.primate.

User info:

Registered: Mar 2005
Posts: 69 (0.01 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 8:27:03: [...]
Status: Offline

Post actions:

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

Non sara' essenziale ma secondo il mio modesto parere semplifica di molto la stesura e la comprensione del codice. Poi per sentinella io rappresento semplicemente un puntatore al valore NIL da me definito che rappresenta una foglia nera. Nulla di piu'.

Se poi la sentinella, la sotitituisci con NULL o con altro l'importante e' avere sempre un riferimento per i nodi che non puntano a nulla.

Non voglio togliere nulla al codice che tu hai preso da algoteam e modificato secondo le tue necessita'.

Grazie per aver cercato anche il numero di pagina

cristiano

User info:

Registered: Nov 2003
Posts: 37 (0.00 al dì)
Location: Milano
Corso: informatica
Anno: segùndo
Time Online: 8:16:27 [...]
Status: Offline

Post actions:

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

eskimo

.illuminato.

User info:

Registered: Jul 2003
Posts: 156 (0.02 al dì)
Location: Milano
Corso: informatica
Anno: 3datroppotempoormai
Time Online: 1 Day, 22:23:46 [...]
Status: Offline

Post actions:

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!

cristiano

User info:

Registered: Nov 2003
Posts: 37 (0.00 al dì)
Location: Milano
Corso: informatica
Anno: segùndo
Time Online: 8:16:27 [...]
Status: Offline

Post actions:

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.

eskimo

.illuminato.

User info:

Registered: Jul 2003
Posts: 156 (0.02 al dì)
Location: Milano
Corso: informatica
Anno: 3datroppotempoormai
Time Online: 1 Day, 22:23:46 [...]
Status: Offline

Post actions:

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

Last edited by eskimo on 22-09-2005 at 15:00

Shimoda

.consigliere.

User info:

Registered: Feb 2003
Posts: 118 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno: 3
Time Online: 1 Day, 12:30:16 [...]
Status: Offline

Post actions:

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)

cristiano

User info:

Registered: Nov 2003
Posts: 37 (0.00 al dì)
Location: Milano
Corso: informatica
Anno: segùndo
Time Online: 8:16:27 [...]
Status: Offline

Post actions:

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

eskimo

.illuminato.

User info:

Registered: Jul 2003
Posts: 156 (0.02 al dì)
Location: Milano
Corso: informatica
Anno: 3datroppotempoormai
Time Online: 1 Day, 22:23:46 [...]
Status: Offline

Post actions:

Shimoda quindi tu hai usato un grafo??

Shimoda

.consigliere.

User info:

Registered: Feb 2003
Posts: 118 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno: 3
Time Online: 1 Day, 12:30:16 [...]
Status: Offline

Post actions:

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

no, un rb-albero per tutti i fiori del piano.. poi userò qualche altra struttura, probabilmente altri rb-alberi per tener traccia dei prati e dei campi..
l'intenzione è di creare, quando è richiesto di calcolare un viaggio, una lista di adiacenza contenente solo i fiori che possono essere attraversati in quel determinato viaggio, e applicarvi l'algoritmo di Dijkstra modificato

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