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

Originally posted by CirAnto

Non so perchè ma riducendo l'insieme dei pozzi ad una coppia di grafi ordinati (uno da Nord a Sud e uno da Est a Ovest) si potrebbe vedere la scelta dell'oleodotto come la scelta di un cammino minimo tra due punti in un grafo ordinato aciclico (in quanto, data una direzione E-S-O-N, non è possibile tornare indietro).
A questo punto l'algoritmo DAG-Shortest-Path mi sembra il più semplice e ottimale tra tutti gli algoritmi NON svolti durante il corso...

Il DAG-Shortest-Path non considera il cammino più corto ma il cammino costituito dai pesi minori.

Detto ciò preferisco creare due semplici liste per contenere i nodi da includere come possibili punti del mio oleodotto.

In pratica ponendo il caso che debba creare un oleodotto da Est a Ovest e che ho una lista (ordinata in base alle ASCISSE) costituita dai punti:

(2) - (4) - (3) - (8) - (5) - (12) - (10)

e devo partire da un punto A (2 < A < 4) e devo arrivare in un punto B ( 12 < B < 10) posso limitare la costruzione del mio grafo aciclico ai nodi 4, 3, 8, 5, 12 e su questo grafo ordinato topologicamente eseguo il DAG-Shortest-Path.

Il bello è che avendo una lista a doppia concatenazione mi basta invertire i puntatori all'elemento precedente con il puntatore all'elemento successivo posso costruire il grafo in entrambe i sensi ed eseguire l'algoritmo DAG-Shortest-Path in maniera equivalente.
Ovviamente durante la costruzione del grafo dovrò avere cura di non considerare gli archi irrealizzabili (perchè intersecanti con altri archi) e di effettuare la differenza:

ValorePozzo - CostoZonaDifficoltosaAttraversata

Questo valore sarà il peso effettivo del mio arco.

Idem dicasi nel caso si vada da Nord a Sud o viceversa.
Ovviamente prima devo aver costruito una seconda lista ordinata in base alle ORDINATE.

Spero possa aiutare.

Ciao

stavo pensando a qualcosa del genere, mi devo rivedere il DAG-S.-P., evidentemente...

Io pensavo di costruirmi localmente al metodo oleodotto() una lista di pozzi possibili (ovvero quelli che non escono dai limiti dei punti dati, la lista che per te è 4-3-8-5-12) e ordinare questa lista in base a ascissa o ordinata, crescente o decrescente, in base alla direzione passata. Dopodichè associare ad ogni pozzo nella lista locale il massimo valore di tutti i *cammini* che ci entrano, venendo da A. Procedendo a partire da A, questi valori dovrebbero aggiornarsi senza troppi problemi... 4 avrà associato il valore di A-4. 3 avrà associato il più alto valore tra (valore di 4 + valore del tubo 4-3) e A-3. E via dicendo, quindi i confronti andranno fatti sulla sottolista costituita dai tubi che precedono l'attuale.

Non so se sto descrivendo il DAG-Shortest-Path con altre parole, sinceramente, ma mi pare che potrebbe funzionare. Ora devo solo scriverlo

__________________
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
stavo pensando a qualcosa del genere, mi devo rivedere il DAG-S.-P., evidentemente...

Io pensavo di costruirmi localmente al metodo oleodotto() una lista di pozzi possibili (ovvero quelli che non escono dai limiti dei punti dati, la lista che per te è 4-3-8-5-12) e ordinare questa lista in base a ascissa o ordinata, crescente o decrescente, in base alla direzione passata. Dopodichè associare ad ogni pozzo nella lista locale il massimo valore di tutti i *cammini* che ci entrano, venendo da A. Procedendo a partire da A, questi valori dovrebbero aggiornarsi senza troppi problemi... 4 avrà associato il valore di A-4. 3 avrà associato il più alto valore tra (valore di 4 + valore del tubo 4-3) e A-3. E via dicendo, quindi i confronti andranno fatti sulla sottolista costituita dai tubi che precedono l'attuale.

Non so se sto descrivendo il DAG-Shortest-Path con altre parole, sinceramente, ma mi pare che potrebbe funzionare. Ora devo solo scriverlo

ragazzi ma perchè questi giorni non ci riuniamo nel tentativo di fare questo benedetto progetto?

Io e Jacoposki ci troviamo questa mattina in silab verso le 10 chiunque voglia unirsi a noi è ok.

Io ora (8.45) sono gia qui, sui computer vecchi in fondo vicino alla vetrata con le due porte. L'ultimo computer della tavolata e alle mie spalle ci sono i pc nuovi, quelli con lo schermo LCD.

io mi sono svegliato mezz'ora fa... aspetto che passi il caffè e arrivo... gh, ho sonno...

__________________
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 sono reduce dal compito di analisi e mi sono svegliato un pò dopo

se passo verso le 13-14 vi trovo ancora?

Passa dal Silab che qualcuno trovi!!

Ciao

allora in un'oretta son lì... rimanete sempre in quel pc mi raccomando, altrimenti non vi trovo

sono rimasto solo io, sempre sul suddetto PC... se non mi trovi vuol dire che sono stato assalito da crisi di fame e sono andato a procacciarmi del cibo... eventualmente aspettami che torno ^^

__________________
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

Domani per chi volesse discutere di questo orrido progetto saremo in silab appena esco dalla prova di laboratorio di sisop. Suppongo sarà un orario tipo 10.30 - 11, per me.

__________________
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

Se vuoi io ne posso discutere....ma io arrivo in silab per le 15...ti va bene?

__________________
Spaghetti!!!

domani non ci sono... sabato forse, ma non so ancora.

__________________
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

Volevo segnalarvi un problema che ho riscontrato intersecando due tubi.

I due tubi sono:

(3,3,6,5) e (1,1,6,5)

Il problema è che il coefficente angolare del primo è periodico, è 0,66666667, mentre il coefficiente angolare del secondo è discreto, è 0,8.

Quando uso i coefficienti angolari per trovare l'intersezione, ovviamente trovo che essa è situata nel punto (6 - 5).

Però il programma secondo me vede questo punto come(5,999999 - 4,99999999) o una cosa di questo genere, perchè secondo lui i due tubi si intersecano prima della loro fine...

Non penso di aver sbagliato la funzione, perchè questo è l'unico caso che mi si è presentato, e ho molti altri tubi che si intersecano proprio alla fine, ma li posso inserire tranquillamente

Avete suggerimenti? Vi è capitato anche a voi?