.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [PROGETTO] Videosorveglianza (http://www.dsy.it/forum/showthread.php?threadid=26992)

Originally posted by ale82info
l'avete tutti finito o ci avete rinunciato? [/B]

__________________
__________________________
FORZA INTER ALE'
NON MOLLARE PERCHE'
C'E' LA NORD CHE CANTA PER TE!
__________________________

no dai...provaci ancora!

MA QUALCUNO HA CAPITO COME FARE IMPIANTI E BUI!?!?!

io procedo con un algoritmo gredy
per ogni nodo, partendo dal livello più alto, calcolo la migliore combinazione di figli con telecamera o senza telecamera
la calcolo due volte per ogni nodo, una volta pensando che in quel dato nodo ci sia la telecamera, una volta pensando che non ci sia
poi vado ai ndi padre, rifaccio tutto e così via
arrivato alla radice ho sempre la soluzione migliore


questo è il succo dell'algoritmo che uso io

per il buio, calcolato l'impianto ottimale, controllo le stanze non direttamente controllate, se ce ne sono due vicine, significa che tra loril corridoio è buio

__________________
Heal The World
Just Because You Read It In A Magazine Or You See It On A Tv Scren Don't Make It Factual

ma supponiamo che io abbia una creato la struttura di figura 1 sul testo del progetto....

Se ora faccio D S9 20, lui trova la stanza, quindi cancella tutto il deposito....

Ma poi deve anche ricreare un nuovo deposito con ingresso S9 ????

Originally posted by ale82info
ma supponiamo che io abbia una creato la struttura di figura 1 sul testo del progetto....

Se ora faccio D S9 20, lui trova la stanza, quindi cancella tutto il deposito....

Ma poi deve anche ricreare un nuovo deposito con ingresso S9 ????

__________________
Heal The World
Just Because You Read It In A Magazine Or You See It On A Tv Scren Don't Make It Factual

Qualcuno ha una minima idea di come rendere l'albero k-ario efficiente con la ricerca per nome?
Cioe se ogni volta x aggiungere una stanza devo scorrere tutto l'albero in cerca dell'altra stanza a cui collegarla la cosa non risulta molto efficiente...

io tengo due "alberi"
un reale albero rb lessicografico con all'interno tutti i nodi di tutti i depositi (ricordatevi che possono coesistere due o più depositi in contemporanea) dove faccio tutte le ricerce se esistono i nodi e quindi ricavo il relativo indirizzo (la ricerca su esistenza va fatta ad ogni inserimento stanza, creazione deposito, cancellazione stanza)

i nodi veri e propri li memorizzo in un... albero k-pario... in termini di implementazione una lista di "adiacenze", dove per adiacenze intendo la lista dei figli... quindi avrà tutti i nodi (il cui indirizzo è memorizzato nell'albero k-ario) con all'interno la lista dei figli

poi a dir la verità io ho un'altra lista di adiacenze a livelli, mi serve per l'algoritmo
sto iniziando ora a implementare l'algoritmo... credo sia molto efficiente, al più n alla seconda (ma in verità credo di meno, è qualcosa come n*m dove m è il numero medio dei figli... per un albero binario impiega tempo 0n) ma è piuttosto laborioso per l'aggiunta e eliminazione di stanze

__________________
Heal The World
Just Because You Read It In A Magazine Or You See It On A Tv Scren Don't Make It Factual

io avevo pensato ad una tabella hash con concatenazione

scusate io ho implementato un semplice albero k-ario con il metodo del figlioSx, fratelloDx... non sarà ottimizzatissimo ma a me basta uno schifoso 18... voglio sperare che non rompa le palle perchè meglio di così non so fare...

__________________
lol

Sicuramente lo accetterà lo stesso ma con un voto inferiore. Il fatto è che ogni volta che inserisci una nuova stanza ad un deposito devi cercare in tutto l'albero dove si trova l'altra stanza a cui devi collegarlo. Se si inserisce una stanza n volte scorrendo in media n/2 volte l'albero nel caso peggiore si potrebbe arrivare ad un efficienza dell'ordine di n^2.
Credo che usare un albero lessicografico che tenga i riferimenti alle stanze sia il metodo migliore, alla fine è quasi come l'albero che usi per i depositi.
Se vuoi fare le cose al meglio dovresti usare un albero RB per mantenere l'albero bilanciato altrimenti se vengono ipoteticamente inserite le stanze in ordine alfabetico non otterresti nessun vantaggio dall'utilizzo di 2 alberi.

Ciao a tutti, ho una struttura nodo di questo tipo in modo da avere un albero con radice che punta al primo figlio con sx e con il primo figlio che punta ai fratelli con dx e così via.
Ho un problema con la visita dell’albero.
Il fatto è che per un certo numero di figli sembra che funzioni ma dopo aver cominciato a implementare impianti e via dicendo mi sono accorto che non è così.
Sicuramente c’è un problema nella ricorsione, qualcuno per caso sa dirmi dove sbaglio.


struct nodo {...}

P.S. Se qualcuno giovedì mattina è al Silab ci si può beccare e per scambiarsi qualche suggerimento.

Originally posted by fema82
struct nodo {...}

Intervento del moderatore:
E' stato tolto il codice dei programmi, dato che è un progetto valido per l'esame.

Ricordo che è vietato (anche perchè può portare all'annullamento dei voti) inserire codice di elaborati in corso; sono invece liberissimi - ovviamente - utili suggerimenti implementativi e quant'altro non fornisca codice preconfezionato

__________________
"Voi che tingete i mari del colore dello zinco, che tramutate i boschi in gialli deserti, i venti in fumi di polveri da sparo e che bruciate i cieli. Voi che volete ripetere i malvagi atti della sconsiderata Lilith, che fu la prima moglie di Adamo e poi la sposa del Diavolo. Voi che volete ripetere la ribellione scatenata da Lucifero, del mondo celeste il più splendente. Voi! Ascoltate l'afflizione della sottospecie alata che vola alta nel cielo." [Angel Sanctuary]
::: mail: yoruno@dsy.it ::: ::: My Site ::: ::: Dsy Photo Gallery ::: ::: DeviantART Gallery :::

pensavo che per una minuscola parte di codice fosse consentito...
errore mio.

Originally posted by fema82
Se qualcuno giovedì mattina è al Silab ci si può beccare e per scambiarsi qualche suggerimento.

__________________
lol

Posso associarmi e chiedere un po' di chiarimenti se non sono di peso? Come posso risconoscerVi? Grazie