.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [ALGORITMI LAB] Progetto "Oledotti 2" (http://www.dsy.it/forum/showthread.php?threadid=20512)

[ALGORITMI LAB] Progetto "Oledotti 2"

É uscito il nuovo progetto di algoritmi...
Data di consegna 17 luglio (compreso).

Oleodotti 2

...ma sul sito del laboratorio di Fiorentini nn c'è nulla...come è possibile?

...da dove lo hai preso il testo del progetto?

ciao

Originally posted by Decs
...ma sul sito del laboratorio di Fiorentini nn c'è nulla...come è possibile?

...da dove lo hai preso il testo del progetto?

ciao

..ma alla fine, visto che il sorgente dell'altro é stato rimosso dalla sezione files (grazie , vorrei chiedere a chi ha giá fatto il primo (o comunque ci stava giá lavorando, e un'idea se l'é fatta) che strutture dati vi sembrano piú adatte.
le mie considerazioni (preliminari) sono queste:

piú o meno dovrebbero servire:

- una struttura per memorizzare le zone difficoltose [una lista sarebbe semplice, considerando che magari non saranno migliaia ma una decina, un albero sarebbe piú efficiente, ma in base a cosa si ordina? ordinata del primo punto della zone? ecc]

- una struttura per memorizzare pozzi / oleodotti

...e qui si comincia...mando dei dubbi in ordine sparso

- il primo (sará giá emerso...) riguarda i punti di partenza e arrivo di un oleodotto: non sono pozzi, ma andranno mantenuti nella stessa struttura che memorizza i pozzi (come, magari, 'pozzi nulli')

- ritenete necessario memorizzare gli oleodotti e i pozzi in due strutture separate? magari un bialbero per pozzi e punti, e un grafo (o meglio una foresta) per l'insieme degli oleodotti?
questo permetterebbe di eseguire ricerche topografiche in modo abbastanza efficiente, ma complicherebbe un poco la gestione dell'insieme...

- il problema del calcolo della collisione di un segmento nuovo con uno esistente: come lo state approcciando? al di lá della formuletta banale per calcolare la collisione, penso che il metodo di ricerca (diciamo 'preliminare') dipenda fortemente dalla struttura o dalle strutture che si é scelto di utilizzare.

scusate l'esposizione caotica, ciao

Ciao anche io userei un approccio come il tuo, cioè con strutture così semplici, soprattutto userei due liste: 1pozzi e 1"tubi" che mi danno i pozzi, i collegamenti(con anche il verso!) e usandole insieme anche l'insieme degli oleodotti (e qui viene il bello, questo tubo di che oleodotto è??? 1 problema)
Poi calcolerei gli oleodotti senza considerare le permutazioni di tutti i possibili percorsi ammessi (come leggevo nei thread del progetto precedente, anche perchè non sarei capace) ma considerei da ogni punto (punto di partenza o pozzo intermedio che sia) il pozzo più vicino in direzione D e lo inserirei nell'oleodotto solo se Val(P)>C(T)+Z && "non_incrocia_nessun_tubo", se la condizione non è valida scarto il pozzo e considero il secondo più vicino.... e così via. Dovrebbe funzionare, non riscontro evidenti problemi, ma vorrei conferma! forse un problema che mi viene in mente è che una zona difficoltosa deve essere considerata sull'insieme, visto che forse passando per una Z che mi fa raggiungere un pozzo "sconveniente" magari arrivo ad un altro pozzo con un valore altissimo che mi fa recuperare!!

spero di essere stato chiaro...
P.

Originally posted by eskimo
Ciao anche io userei un approccio come il tuo, cioè con strutture così semplici, soprattutto userei due liste: 1pozzi e 1"tubi" che mi danno i pozzi, i collegamenti(con anche il verso!) e usandole insieme anche l'insieme degli oleodotti (e qui viene il bello, questo tubo di che oleodotto è??? 1 problema)
Poi calcolerei gli oleodotti senza considerare le permutazioni di tutti i possibili percorsi ammessi (come leggevo nei thread del progetto precedente, anche perchè non sarei capace) ma considerei da ogni punto (punto di partenza o pozzo intermedio che sia) il pozzo più vicino in direzione D e lo inserirei nell'oleodotto solo se Val(P)>C(T)+Z && "non_incrocia_nessun_tubo", se la condizione non è valida scarto il pozzo e considero il secondo più vicino.... e così via. Dovrebbe funzionare, non riscontro evidenti problemi, ma vorrei conferma! forse un problema che mi viene in mente è che una zona difficoltosa deve essere considerata sull'insieme, visto che forse passando per una Z che mi fa raggiungere un pozzo "sconveniente" magari arrivo ad un altro pozzo con un valore altissimo che mi fa recuperare!!

spero di essere stato chiaro...
P.

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

Come faccio a sapere quando due tubi (quindi due segmenti) si intersecano?? Grazie

Ciao a tutti! anche io sono orientato all'uso di liste. Una per memorizzare i pozzi, una per le zone difficoltose ed una per i tubi inseriti nel piano.

Poi, per i calcoli dell'oleodotto ho bisogno di almeno un'altra lista di supporto che "svuoterò" al termine del calcolo e di una lista nella quale memorizerò temporaneamente ed ordinatamente i pozzi che possono eventualmente fare parte dell'oleodotto che dovrò creare in una data direzione! In poche parole, se devo creare un oleodotto in direzione sud con partenza da (5,4) è in utile considereare e quindi memorizzare nella lista il pozzo (5.9).

Secondo me un qualcosa per gli oleodotti ci vuole... per forza! anche se voglio mantenere la lista di tubi, per vedere quando costruisco un oleodotto se posso riutilizzare un collegamento esistente, non mi serve per stampare la lista dei tubi di un oleodotto! ho bisogno di una struttura che tenga traccia di quale oleodotto fa parte un determinato tubo... immaginate un reticolo esagerato di tubi, da un pozzo ne possono uscire più di uno, quindi devo sapere COME è fatto un oleodotto... e qui mi incarto!

non ho letto il testo, ma se è come nel progetto di giugno gli oleodotti li devi solo stampare... aggiungi alla lista globale di tubi i tubi che compongono l'oleodotto che stampi, e sei a posto... o no?

__________________
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

si ma il problema è che la lista di tubi ha TUTTI i collegamenti fra i pozzi. Visto che mi chiede uno specifico oleodotto, io gli devo tirare fuori l'elenco dei pozzi (x, y) che compongono l'oleodotto, elencatri secondo la direzione.... io come faccio a sapere quale pozzo e quale tubo fanno parte dell'oleodotto?
ho appena finito di scrivere sto pezzo e mi sono accorto che devo stampare solo quando mi chiede di costruirlo (l'unica funzione che fa tutto è oleodotto(xyxyD)) quindi, mentre lo faccio posso stamparlo e poi me ne lavo le mani... o no?? qualcuno mi può rassicurare su questo? cioè se devo pensare ad una struttura per memorizzare l'oleodotto per intero??
thx P.

Originally posted by Jacoposki
non ho letto il testo, ma se è come nel progetto di giugno gli oleodotti li devi solo stampare... aggiungi alla lista globale di tubi i tubi che compongono l'oleodotto che stampi, e sei a posto... o no?

senai: no in teoria se il tubo c'è già non faccio niente... l'oleodotto usa un collegamento preesistente e basta... tanto se lo si stampa mentre lo fai non devi mantenere nessuna informazione specifica sull'oleodotto , usi le info locali mentre costruisci.

Ma è qui il problema! a me proprio non viene quel fottuto oleodotto; io pensavo di poter usare una tecnica greedy (a dir la verità mi sembra più idiota che greedy cmq...) cioè scelgo sempre il pozzo migliore localmente... cioè il più vicino, non solo come distanza ma anche rispetto alla D, che non passi zone difficoltose di un livello più alto del valore del pozzo e che non intersechi....
in questo modo l'oleodotto viene fuori ma ci sono troppe probabilità che ci siano anche cammini più "strani" che sono migliori (cioè che prevedono l'uso di un pozzo molto lontano ma che poi ad esempio è vicino ad altri pozzi esagerati che bisognerebbe usare...).
In pratica bisogna considerare TUTTI i cammini per intero e poi scegliere il migliore!

ho letto i commenti di quelli che hanno fatto il progetto oleodotti di giugno e sembra che abbiano fatto così... costruendo il grafo e poi calcolando il percorso più "pesante" (valore max)... il guaio è che innanzitutto non ho i capitoli del libro di algo dove c'è lo shortest path di un DAG (E' FUORI DAL PROGRAMMA!!!!! E IL MIO LIBRO FOTOCOPIATO NON CE L'HA!!!!)

non c'è nessuno che ha qualche idea???? a luglio sono già tutti in vacanza e siamo rimasti in 4 gatti?

sigh sigh sooooob

non penso sia necessario scomodare Dijkstra e compagnia cantante...

dobbiamo analizzare TUTTI i possibili percorsi, quindi dobbiamo valutare TUTTE le combinazioni disponibili...

Salve ragazzi, non so a che punto siete, io avevo fatto il progetto del mese scorso,ma l'ho finito un po' di giorni in ritardo, quindi per fare questo, preaticamente ho solo fatto un paio di modifiche al vecchio codice, però ho notato una cosa strana negli output, se qualcuno si è fatto un disegno del grafico degli input e output forniti in esempio, avrà notato che l'ultimo output NON è in migliore, mi spiego meglio, o 6 0 6 12 N in output dà (70 6,0 -8,2 -2,8 -4,10 6,12)
. Per me invece il percorso migliore sarebbe (220 6,0 6,6 -2,8 -4,10 6,12).
Qualcuno la pensa come me?