Novalis

Dvce della Rete

User info:

Registered: Feb 2003
Posts: 244 (0.03 al dì)
Location: Milano - Nuoro
Corso: TICOM
Anno: 2
Time Online: 2 Days, 18:20:28 [...]
Status: Offline

Post actions:

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

CirAnto

User info:

Registered: Jul 2003
Posts: 25 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 10:30:29 [...]
Status: Offline

Post actions:

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

Jacoposki

.arcimaestro.

User info:

Registered: Sep 2004
Posts: 498 (0.06 al dì)
Location: Milano
Corso: Informatica
Anno: in tesi-sa dio per quanto
Time Online: 4 Days, 0:36:57 [...]
Status: Offline

Post actions:

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

CirAnto

User info:

Registered: Jul 2003
Posts: 25 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 10:30:29 [...]
Status: Offline

Post actions:

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

Beh concettualmente siamo sulla stessissima idea, il problema è solo realizzare l'algoritmo che calcola tutti i cammini possibili per raggiungere il punto di arrivo...
Detto sinceramente io ho preso il DAG-S-P perchè è una versione semplificata del Bellman-Ford...
Il codice del Bellman-Ford lo si trova qui:
http://www.algoteam.dsi.unimi.it/im...codici/ford.txt

La pagina è redatta dallo stesso Fiorentini quindi immagino che si possa prelevare e modificare il codice in base alle proprie necessità.
Ovviamente bisogna modificare l'input che nell'implementazione presentata viene presa da un file formattato in un certo modo.

Novalis

Dvce della Rete

User info:

Registered: Feb 2003
Posts: 244 (0.03 al dì)
Location: Milano - Nuoro
Corso: TICOM
Anno: 2
Time Online: 2 Days, 18:20:28 [...]
Status: Offline

Post actions:

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

mitnik

User info:

Registered: Jun 2002
Posts: 235 (0.03 al dì)
Location:
Corso:
Anno:
Time Online: 3 Days, 4:25:25 [...]
Status: Offline

Post actions:

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.

Jacoposki

.arcimaestro.

User info:

Registered: Sep 2004
Posts: 498 (0.06 al dì)
Location: Milano
Corso: Informatica
Anno: in tesi-sa dio per quanto
Time Online: 4 Days, 0:36:57 [...]
Status: Offline

Post actions:

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

Novalis

Dvce della Rete

User info:

Registered: Feb 2003
Posts: 244 (0.03 al dì)
Location: Milano - Nuoro
Corso: TICOM
Anno: 2
Time Online: 2 Days, 18:20:28 [...]
Status: Offline

Post actions:

io sono reduce dal compito di analisi e mi sono svegliato un pò dopo

se passo verso le 13-14 vi trovo ancora?

mitnik

User info:

Registered: Jun 2002
Posts: 235 (0.03 al dì)
Location:
Corso:
Anno:
Time Online: 3 Days, 4:25:25 [...]
Status: Offline

Post actions:

Passa dal Silab che qualcuno trovi!!

Ciao

Novalis

Dvce della Rete

User info:

Registered: Feb 2003
Posts: 244 (0.03 al dì)
Location: Milano - Nuoro
Corso: TICOM
Anno: 2
Time Online: 2 Days, 18:20:28 [...]
Status: Offline

Post actions:

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

Jacoposki

.arcimaestro.

User info:

Registered: Sep 2004
Posts: 498 (0.06 al dì)
Location: Milano
Corso: Informatica
Anno: in tesi-sa dio per quanto
Time Online: 4 Days, 0:36:57 [...]
Status: Offline

Post actions:

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

Jacoposki

.arcimaestro.

User info:

Registered: Sep 2004
Posts: 498 (0.06 al dì)
Location: Milano
Corso: Informatica
Anno: in tesi-sa dio per quanto
Time Online: 4 Days, 0:36:57 [...]
Status: Offline

Post actions:

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

Nonsaprei

.arcimaestro.

User info:

Registered: Oct 2002
Posts: 485 (0.06 al dì)
Location: Sobborghi
Corso: Non rilevato
Anno: Ignoto
Time Online: 7 Days, 11:31:45 [...]
Status: Offline

Post actions:

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

__________________
Spaghetti!!!

Jacoposki

.arcimaestro.

User info:

Registered: Sep 2004
Posts: 498 (0.06 al dì)
Location: Milano
Corso: Informatica
Anno: in tesi-sa dio per quanto
Time Online: 4 Days, 0:36:57 [...]
Status: Offline

Post actions:

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

rox

User info:

Registered: Oct 2002
Posts: 103 (0.01 al dì)
Location:
Corso: Informatica
Anno: 2°
Time Online: 2 Days, 6:27:55 [...]
Status: Offline

Post actions:

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?