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

Operazione impianto (alfa):
sembrerebbe essere un problema di ottimizzazione, quindi probabilmente Programmazione dinamica o Algoritmi golosi.
Se la soluzione fosse la seconda di che Stanze sarebbe goloso l'algoritmo?

ho dei piccoli dubbi sull'eliminazione di un stanza

voi come l'avete interpretata?

io l'ho interpretata così:
se devo eliminare una stanza che non sia quella di ingresso, devo prendere tutti i suoi figli e farli diventare figli del padre della stanza da eliminare, giusto?

Allego immagini della mia interpretazione

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

se lo rappresenti con un albero credo che la cancellazione si faccia sempre in quel modo

Sinceramente ne sono usciti di molto piu' difficili(questo e' anche carino come "storia"), io personalmete credo di essere a buon punto, a parte qualche piccola questione di puntatori facilmente risolvibile.
Come struttura dati ho usato un AVL-Tree, nel caso peggiore il tempo e' di O(log n), e cmq la percorrenza media e' O(h), ottimo sopratutto se l'albero diventa molto grande (cosa molto prevedibile).

ma scusa...l'albero del progetto non è binario! L'albero avl non permette di bilanciare un albero binario?

ciao a tutti
effettivamente credo sia impossibile usare gli alberi binari visto che, ogni stanza ha dei collegamenti (corridoi) con k stanze, come nell' esempio, ho pensato anche io agli alberi, ma a quelli k-ari, anche se non c'è molto su libro, come implementazione.
Solo che in mente c'è sempre la stessa frase, mi sembra troppo facile che il prof. abbia disegnato un albero a pag 2 per dirci di usare gli alberi, quella sembra l'idea più intuitiva ma è chiaro che per capire se una stanza è sorvegliata in qualche modo ci vuole un altra struttura, boo, ancora non ho capito come "sorvegliare" le stanze.

buon lavoro

ciao

Qualcuno ha capito quale potrebbe essere la struttura migliore per sorvegliare le stanze?

ma voi come pensate di implementare la funzione Impianto?!
Io non riesco a trovare nemmeno un modo per calcolarla a mano!!!!

ankio sono in crisi con la struttura, visto che gli alberi k-ari non ho idea di come rappresentarli, visto che in questo caso non si puo' fare una struttura nodo con puntatori fissi a padre e due figli.. qualche suggerimento??
secondo me in apparenza è più facile, ma nella realtà è complicato come gli altri..
per quanto riguarda l'impianto, ankio ho pensato a programmazione dinamica o allgoritmi golosi ma non sono ancora arrivata al dunque..
lfn

__________________
an arrow from the sun

gli alberi k-ari pg 203 del libro, un puntatore per il padre un puntatore per in primo figlio, e un puntatore per il fratello quindi su ogni livello c'è una lista concatenata.
C'è anche il problema della ricerca del nome della stanza

Originally posted by black_mamba

C'è anche il problema della ricerca del nome della stanza

La ricerca è un'operazione frequente, mi chiedevo se sarebbe meglio farla in tempo lineare, o mantenere una struttura dati ordinata e farla in tempo logaritmico.


Partendo dall'idea di grafo, e considerando le stanze come l'insieme dei vertici e i corridoi come insieme dei lati...secondo voi quest'idea può portare da qualche parte?

Secondo me sono buone sia l'dea dell' albero k-ario che quella di grafo... alla fine voi cosa state utilizzando?

L'impianto come lo avete pensato?

Ciao ragazzi, ho appena avuto una specie di illuminazione! per caso sfogliando il libro (molto a caso direi) sono giunta alle foreste di alberi radicati, vi chiederete cosa centrano, io ci ho fatto caso solo ora: nell'input del prof. alle prime due righe c'è,
d frutta e d mobili. questi sono due depositi diversi! quindi due alberi diversi.
L'idea di usare un grafo non so se è possibile perchè 1) dobbiamo avere un solo ingresso, 2)ogni stanza deve avere un cammino unico e credo che solo gli alberi permettano un' implementazione del genere (poi non so, sui grafi non sono il massimo).
Da qualche parte nei lucidi, avevo visto qualche progetto fa, un modo che dato un nodo (il nome di una stanza) risaliva alla sua radice e quindi al deposito di appartenenza.

che ne dite? secondo voi è un possibile inizio?

mi dici dove l'hai trovato gentilmente?