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

è possibile che una zona si sovrappone ad un pozzo oppure che un pozzo viene posizionato all'interno di una zona pericolosa?

Non so , in effetti non è specificato, però negli esempi non è contemplato nessun caso del genere, domani devo andare a parlare con Fiorentini e gli chiedo anche questo !!

grazie mille!

...Dubbio...

Ho parlato col Dott. Fiorentini e...
PANICO!!!

Gli ho parlato del mio algoritmo che, pedestremente, analizza tutti i percorsi possibili e lui, in tutta tranquillità, ma ha detto che il mio algoritmo avrebbe dovuto utilizzare una strategia di tipo "dinamico", ovvero riutilizzare le soluzioni per i sotto cammini già trovate.

Bene.
Fare ciò, per me, a 4 giorni dalla consegna e a 7 giorni dall'orale risulta vagamente deleterio (vorrebbe dire riformulare l'algoritmo)...
Qualcuno sà se consegnare un progetto funzionante ma che non rispetta il vincolo della programmazione dinamica possa compromettere l'esito dell'esame?

Ciao.

a proposito, via mail ho saputo dal prof che un pozzo può essere inserito dentro una zona difficoltosa.
e dato che niente lo vieta, una zona può contenere più pozzi.

Originally posted by Novalis
a proposito, via mail ho saputo dal prof che un pozzo può essere inserito dentro una zona difficoltosa.
e dato che niente lo vieta, una zona può contenere più pozzi.

Ciao, vi consiglio di dare un occhio al sito di Fiorentini, perchè ci sono un paio di errori stampati sull' output del programma da correggere.
Anche io ho calcolato le permutazioni sui percorsi, non sono riuscito a calcolare un altro modo per migliorare l'efficenza. Qualcuno lo ha fatto in un modo particolare ?? Comunque l'esame orale si puo' sostenere lo stesso, anche se l'algoritmo non è super efficente, naturalmene il voto non sara' alto...

una cosa! considerato che il costo per la posa di un tubo può influenzare il percorso dell'oleodotto, quando calcolate tale costo e come fate a sapere quali pozzi considerare?

Originally posted by mitnik
una cosa! considerato che il costo per la posa di un tubo può influenzare il percorso dell'oleodotto, quando calcolate tale costo e come fate a sapere quali pozzi considerare?

io ho un problema con una funzione che ho creato per farmi dare i nuovi pozzi da controllare: io le do i due punti dell'ultimo pozzo inserito (partendo dal fondo però) e i due punti di arrivo (quello di partenza quindi) con la direzione (contraria a quella richiesta), lei mi restituisce un pozzo da controllare e vedere se e dove mi conviene attaccarlo per fare l'oleodotto.
Il problema è il criterio con cui sceglierlo! distanza minore, direzione minore (cioè considero la distanza solo su una coordinata.... spero si capisca) oppure considerare anche il valore del pozzo?
l'algoritmo funzica più o meno, ma ho dei problemi perchè fa dei percorsi un po suoi.... cazzarola....
P.

Un paio di domande veloci veloci....
La consegna è da fare entro domenica (inclusa). Ma come faccio a consegnare la copia cartacea di domenica? La cassetta postale in via comelico è accessibile anche quando l'uni è chiusa?

Poi mi chiedevo se per passare l'esame è strettamente necessario che il programma dia lo stesso output dei prof. Il mio individua gli stessi pozzi che costituiscono un'oleodotto ma sbaglia a calcolare il valore.... speriamo bene

domenica consegna in email, lunedì consegna cartacea. c'è sul progetto.

domenica consegna in email, lunedì consegna cartacea. c'è sul progetto.

Originally posted by x-Fede
domenica consegna in email, lunedì consegna cartacea. c'è sul progetto.

ops

Originally posted by faxmaister
Poi mi chiedevo se per passare l'esame è strettamente necessario che il programma dia lo stesso output dei prof. Il mio individua gli stessi pozzi che costituiscono un'oleodotto ma sbaglia a calcolare il valore.... speriamo bene

ciao che algoritmo avete usato? o meglio: c'è qualcuno che come me è partito dal fondo considerando il pozzo più vicino, se era il primo lo immetteva, poi il secondo più vicino e calcolava il valore, se era maggiore bene, se era minore provava a vedere come sarebbe stato il valore collegandolo con il punto precedente e così via??? ho un grosso problema e me ne sono accorto oraaa!!!
Paolo

p.s. ma perchè cazzo gli ultimi due giorni del progetto sono sempre ridotto malissimoooo??!?!?!

non è che qualcuno ha dei file di input di test e relativo output del programma (oltre a quello indicato dal prof) così da confrontare i valori che otteniamo?

ciao. una domanda dell'ultim'ora.
testando l'input del prof ottengo risultati collimanti (percorso e valori) per tutti gli oleodotti ECCETTO (..cazz...) che per questo

o 6 12 -2 -6 S

che mi da come risultato

(1100
6,12
14,8
16,4
10,-2
-4,-4
-2,-6
)

a me questo risultato sembra giusto (e' un oleodotto legittimo, e il valore e' maggiore di quello fornito sulle specifiche), ma a quest'ora la paranoia e' massima...
potete confermarmi o smentirmi questa cosa per favore (mentre io mi rileggo tutto il codice per la ventesima volta...)?
se risultasse (come irrazionalmente temo...) che ho cannato qualcosa, mi spiegate perche' l'oleodotto che ho trovato io non va bene? forse non ho capito qualcosa delle specifiche (!!!).
se risultasse corretto posso postare un po' di input di test con relativo output, se serve.
ciao

a me quello viene giusto, non mi trovo invece sull'ultimo!

Pongo U=20, quindi devo moltoplicare per venti il valore che calcolo per la posa giusto?

bene! essendo c* (|x2 - x1| + |y2 - y1|) avrò:

6 0 -8 2 ---> 20(|-8 - 6| + |2 - 0|= 20*(14+2)= 320
-8 2 -2 8 --->....240
-2 8 -4 10 ---->...80
-4 10 6 12 ---> ...240

quindi Val(O)= 50+40+200+100 - (320+240+80+240)= -490

invece se passasi da 6 0-->6 4 --> 6 12 otterrei un valore di 60
quindi

(60
6 0
6 4
6 12
]

ditemi dove sbaglio!!

..HOUSTON, abbiamo un problema!!!
se consideriamo buona la soluzione del prof per l'oleodotto oleodotto 6 12 -2 -6 S (e sto ancora aspettando qualcuno che me lo confermi o smentisca...qualcuno mi spiega perché?) allora avremo tra i tubi giá postati sul piano

(6,12) -> (-4,10) [in direzione S W]
(-4,10) -> (-2,8) [in direzione S E]
(-2,8) -> (-8,2) [in direzione S W]
(-8,2) -> (-4,-4) [in direzione S E]

la soluzione del prof

(70
6,0
-8,2
-2,8
-4,10
6,12
)

e' corretta - *se consideri gli ultimi tre tubi come gia' posati*!!!
...il che contrasta con le specifiche...
siete d'accordo? ci sono altre letture possibili?
...che si fa? (mail al prof?)
ciao

...forse sono stato poco chiaro: contrasta con le specifiche perché considera giá posato un tubo posato nella direzione inversa.
...o sono io ad aver capito male??

...ok, errata corrige.
se consideri la soluzione di "o -8 2 6 12 N" che e'

(362
-8,2
-2,8
-4,10
6,12
)

noterai che gli ultimi tre tubi sono gia' posati nell'ordine giusto, qundi non pesano nel calcolo dell'handicap.
quindi l'ultima soluzione a cui alludi e' giusta nel testo.
....qualcuno ha capito perché la 'mia' non va bene? (se non va bene...)

Penso che la tua soluzione violi delle specifiche del testo , ovvero tutti gli estremi dei tubi , tranne il primo e l´ultimo punto dell´OLEODOTTO, devono essere dei POZZI, quindi la tua soluzione non va bene , perché´ usi il punto 10, -2 , che non e´ un POZZO !!! SEMPLICE .

CIAOZ

hai ragione! questo me l'ero perso...
....vediamo di fissarlo al volo...
ciao e grazie

...infatti ora é tutto uguale.
Grazie ancora per la dritta.

se vi serve per i vostri test

[input]

p -1 0 300
p 2 2 100
z -1 1 2 0 1000
p 0 -4 700
p 4 -3 200
p 0 1 900
p 5 1 50
o -1 -6 1 4 N
h 0 1
p 0 1 1500
o -1 -6 1 4 N
o -3 -7 7 2 E
o 3 5 -3 -7 S
f

[output]

(1030
-1,-6
0,-4
4,-3
5,1
2,2
1,4
)

(1388
-1,-6
0,-4
4,-3
0,1
1,4
)

(941
-3,-7
0,-4
4,-3
5,1
7,2
)

(1474
3,5
2,2
0,1
4,-3
0,-4
-3,-7
)

0. occhio che non hai messo crea()

1. 1030 per il primo oleodotto viene anche a me.

2. per il secondo dovresti avere stesso percorso e valore di 1050 (non paghi nessun tubo).

Il punto (0,1) appartiene alla zona difficoltosa (è sul confine, ma ne fa parte), quindi avresti due tubi "penalizzati", cioè quello che arriva da (4,-3) e quello che va verso (1,4).

3. 941 corretto

4. sempre per la storia dei pozzi che stanno sul confine delle zone difficoltose, l'ultimo oleodotto dovrebbe venire

(1026
3,5
2,2
5,1
4,-3
0,-4
-3,-7)

e non quello indicato da te.


fatemi sapere se siete d'accordo

ok, ora provo ad inserire la modifica sul calcolo dell'appartenenza alle zone e ti faccio sapere.
ma, in conseguenza del fatto che i confini delle zone sono inclusivi e non esclusivi, il tentativo di inserire queste due zone

z 0 0 3 3 1000
z 3 3 5 5 2000

dovrebbe fallire nel secondo caso, perché le zone si sovrappongono, no?
...
....le zone non si possono sovrapporre, vero?!?!?....
TERRORE!!!

deve fallire perchè le zone non possono sovrapporsi

Io sottoscrivo tutte le osservazioni e gli oUTPUT di Novalis, l´unica cosa che non mi va e´ lnput per la zona da inserire, controllate il formato, perche´ non e´ corretto. Bisogna inserire il punto in basso a sinistra e poi quello in alto a destra, come i due estremi.

Ciaoz

nelle specifiche non ci sono vincoli sull'ordine in cui devono essere inserite le coordinate.

anche a me la cosa ha creato un pò di problemi, ma ho aggiunto un pò di controlli (sostanzialmente bisogna capire se la zona è stata inserita in direzione S->N e O->E o negli altri tre modi) e la cosa si sta pian piano risolvendo

PREMESSA: ...spero che il progetto funzioni bene...aspetto nitizie dal prof...

Detto questo...ora arriva un altro problema...l'orale...

In questi pochi giorni devo bombardare di input il mio cervello...

...a tal proposito c'è qualcuno interessato a una bella studiata di algoritmi?

...tenendo presente di svolgere l'orale il 22, ovvero venerdì...

...fate sapere così ci si organizza subito...

Saluti

sapete se i risultati li mette in rete o manda una mail?

dovrebbe contattarci via mail

grazie!!!!

il dubbio era,almeno a sentire i pareri della gente,che non
veniva comunicato nulla sino al giorno dell'orale e solo allora
sapevi l'esito,un po' strano credo...

http://www.dsy.it/forum/showthread....40&pagenumber=4

se guardi qua, qualcuno ha avuto addirittura la risposa il lunedì successivo alla scadenza.

speriamo bene

discussione progetto

ciao a tutti,

qualcuno mi saprebbe dire quand'è la discussione del progetto Oleodotti 2 con il prof. Aguzzoli?

Io so che l'esame orale è il 25...

grazie

aaaaaaaaaaaaaaaaaargh ragazzi sono troppo sfigato
ho fatto il mio bel progetto di oleodotti 2.. lavorando su un Mac con Mac OS X ed XCode sotto Tiger.... usando gcc 4.0.0 ...
funziona tutto bene..compila e va alla grande.

Consegno.. oggi passo dal prof per lasciare la copia cartacea e mi dice che non funziona nulla! Seg fault e valori di output sbagliati.

torno a casa.. riprovo..e su gcc 4 funziona tutto mentre quando compilo su linux con gcc 3.2 sbaglia clamorosamente.

ad occhio e croce penso sia per qualche puntatore che magari il gcc 4 piazza a null automaticamente, mentre il gcc 3.2 no.. ma è un bordello e mi vien da piangere a cercare il bug.. anche perchè ho ambiente di sviluppo (debugger & co.) tutto su gcc 4

sigh me tapino.

Il prof è stato molto gentile e mi ha detto di inviargli la versione fixata.. ma non ne vengo a capo, è un bordello.

Re: discussione progetto

Ciao ragazzi, come vi è andato il giudizio di Fiorentini ?
A me ha detto che l'algoritmo è inefficente (calcolo tutti i percorsi) e che quindi non lo accetta.

Mi ha mandato anche l' input con cui ha testato il programma, è lungo 273 righe, sfido io che ci mette tanto !! Però mi sa che non sono l'unico da quello che ho capito !!! Fatemi sapere se a qualcuno di voi che ha usato questo metodo è andata diversamente.

...ho una domanda...

...ma dove cavolo è il calendario degli orali?

...sul sito di laboratorio non c'è nulla...

...come è andato il giudizio di Fiorentini?

Ciao

il calendario degli orali è disponibile sulla home del laboratorio.

mi ha messo il 21 (ma nella mail ho chiesto di andare il 26) e mi è venuto un colpo.

fortunatamente sono qua in dipartimento e sono passato subito in ufficio... tutto a posto

http://homes.dsi.unimi.it/~fiorenti/labalg04/orali.txt

...certo che il 26 luglio...saremo solo noi in dipartimento?

...vabbè dai, faremo quest'ultimo sforzo....

...comunque la mia "offerta" per un ripasso insieme rimane sempre aperta....

Ciao

...allora ragazzi come procede lo studio?

Re: discussione progetto

Originally posted by wlf3d_it
ciao a tutti,

qualcuno mi saprebbe dire quand'è la discussione del progetto Oleodotti 2 con il prof. Aguzzoli?

Io so che l'esame orale è il 25...

grazie