.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Algoritmi - Torelli] Progetto "OLEODOTTI" (http://www.dsy.it/forum/showthread.php?threadid=19840)

[Algoritmi - Torelli] Progetto "Oleodotti"

Uscito il testo http://homes.dsi.unimi.it/~fiorenti...4/oleodotti.pdf

Consegna entro domenica 19 giugno.

Non sembra facilissimo ma neppure impossibile (almeno il testo è abbastanza chiaro, una volta tanto )

Spero di non dovermi rimangiare queste parole...

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

Progetto "oleodotti"

bene ragazzi è uscito il nuovo progetto se qualcuno ha ad esempio pezzi di codice che possano andare bene per l'implementazione di qualche metodo la posti, cosi' ci confrontiamo e vediamo di fare un bel esame. buona fortuna a tutti!

strutture dati

Ciao
volevo avere le vostre prime impressioni sulle strutture dati da utilizzare?
Io direi lista per oleodotti e albero binario per i pozzi ...

__________________
La mente che si apre ad una nuova idea non torna mai alla dimensione precedente (A. Einstein)

Originally posted by queen
bene ragazzi è uscito il nuovo progetto se qualcuno ha ad esempio pezzi di codice che possano andare bene per l'implementazione di qualche metodo la posti, cosi' ci confrontiamo e vediamo di fare un bel esame. buona fortuna a tutti!

Intervento del moderatore:
Ricordo a tutti che è vietato postare codice di elaborati in corso.

Sono invece concessi i messaggi con suggerimenti implementativi "non implementati"

__________________
"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 :::

perchè albero binario per i pozzi? secondo quale ordinamento?

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

Originally posted by Jacoposki
perchè albero binario per i pozzi? secondo quale ordinamento?

__________________
La mente che si apre ad una nuova idea non torna mai alla dimensione precedente (A. Einstein)

ciao ragazzi, secondo voi questo progetto puo essere uguale al progetto richiami????

e metterli in un grafo, invece? così poi si facilita anche la ricerca dei cammini, no?
ma lo spazio cartesiano, che dice ovviamente di non rappresentare come una matrice, come lo rappresentate?

aiuto...sono una capra in algoritmi

__________________
more and more there is this animal
looking out thorugh my eyes
capitalism is the devil's wet dream
the big plan is just to keep spinning, 'cause the big bang is always just beginnin'

in un grafo? 0_o Scusa ma l'idea del grafo non mi pare molto sensata... tu NON SAI come i pozzi verranno collegati dai tubi, quindi non hai modo di sapere come un pozzo è in relazione con gli altri ---> niente grafo, a meno di non fare un grafo per ogni oleodotto ma mi pare quantomeno incasinato ^^

Lo spazio cartesiano, di fatto, non lo rappresenti... usando coppie di valori per i punti stai già rappresentando il piano, non devi usare una struttura di dati apposita.

E sì, ho anche l'impressione che abbia più di una cosa in comune con il progetto richiami. Pessima notizia per me che di quel progetto non avevo capito un'ostia.

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

Progetto oleodotti

...è uscito il nuovo progetto di algoritmi...non sembra tanto semplice qualcuno saprebbe darmi un'idea??

Sto facendo la più banale delle strutture a liste concatenate per tenere dentro tutto... una lista di giacimenti, una di zone e una di pozzi. Non sono ancora sicuro se abbia o meno senso fare una struct "tubo" e poi rappresentare l'oleodotto come una lista di tubi.

Ben lontano anche solo dal cominciare a pensare all'algoritmo per trovare l'oleodotto migliore.

Voi?

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

Io pensavo di gestire i pozzi con una struttura ad albero.
In questo modo, è possibile scartare velocemente tutti quelli che non devono essere considerati nella costruzione di un oleodotto, riducendo così i tempi di esecuzione.

Per giacimenti e zone anche io partirò con una lista, perchè al momento non mi viene in mente niente di più furbo.

Per quanto riguarda l'algoritmo cruciale... non ci ho ancora pensato a dir la verità, ma ho qualche piccola idea di base.

Speriamo bene

Originally posted by Novalis
Io pensavo di gestire i pozzi con una struttura ad albero.
In questo modo, è possibile scartare velocemente tutti quelli che non devono essere considerati nella costruzione di un oleodotto, riducendo così i tempi di esecuzione.

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

Ciao a tutti secondo me i problema del progetto è:
come fa l'oleodotto a scegliere il percorso migliore?
la prima cosa che ho pensato è stato un grafo ma poi mi sono accorto che nn serve a niente.
Forse dovremmo usare un algoritmo che ad ogni nuovo pezzo di oleodotto confronti se il valore ottenuto è migliore di quello del passo precedente; e poi c'e anche da tenere presente che nuovi oleodotti nn possono incrociare quelli gia esistenti.
Il progetto nn mi sembra tanto facile se avete qualche idea anche stupida nn fate i timidi fatevi sentire, al limite ci facciamo 2 risate.
saluto tutti.

L'idea è quella di ordinare i pozzi in base a una delle loro coordinate (ad esempio l'ordinata): in tal modo, dovendo costruire un oleodotto in direzione nord tra (2.2) e (6,8), possiamo limitare la nostra attenzione soltanto agli elementi dell'albero che hanno chiave compresa tra 3 e 7.

Ovviamente si rende necessario memorizzare anche un albero contenente l'ordinamento per ascissa: si spreca un pò di memoria, ma almeno non si è costretti a scorrere ogni volta tutta la lista (in tempo n) per identificare tutti i punti coinvolti nella ricerca del percorso, con qualche beneficio nel tempo di esecuzione.

Tra le altre cose, l'utilizzo di un albero potrebbe facilitare le cose quando sarà necessario... magari con un algoritmo ricorsivo che "esaurisce" tutte le possibili combinazioni tra i vari nodi, e alla fine sputa fuori il percorso migliore.