.dsy:it. - [Progetto] L'ape bottinatrice

Pages (2): [1] 2 »
Show 150 posts per page

.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Progetto] L'ape bottinatrice (http://www.dsy.it/forum/showthread.php?threadid=21329)

Posted by Frigging on 15-09-2005 09:13:

[Progetto: L'ape bottinatrice]

E' online ... speriamo bene ...

Posted by maynard80 on 15-09-2005 10:42:

mhmmm non sembra facile...

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by Frigging on 15-09-2005 11:09:

Confidiamo nel Gran Visir Indice del Cormen ... qualche idea verra'

eheheh ridiamo per non piangere...

Pero' il lato positivo e' che l'ho finito di leggere ...

Posted by Ziotony.f4f on 15-09-2005 11:12:

ma no

Non non è poi così difficile, è sulla stessa scia dei progetti Oleodotti, ma mooooooolto più semplice, quindi mi sa che si ancdrà a pescare da lì...

Posted by Frigging on 15-09-2005 11:15:

Non l'ho guardato oleodotti per cui... ma si dai mo ci si pensa un attimo ... il problema e' sempre l'impatto

Posted by eskimo on 15-09-2005 13:58:

anche a me non sembra difficile, considerato che si deve implementare solo Viaggio, quindi l'algoritmo ha solo l'obiettivo di trovare un cammino massimo fra i fiori... vediamo e speriamo in bene, in bocca al lupo a tutti guagliò!!!
P.

Posted by Frigging on 15-09-2005 14:02:

Ma insomma .. secondo me e' determinare i campi in modo ottimizzato...

Tutte le volte che considero un prato devo controllare nel caso peggiore l'intersezione con tutti gli altri... purtroppo non mi viene in mente nulla di piu' intelligente...

altra cosa che non ho capito dal testo, cosa vuol dire che solo due prati possono sovrapporsi?

Tre prati perche' non possono?

cioe' e' permessa la sequenza di inserimento:

ret1-ret2-ret3

ma non e' permessa la sovrapposizione ret1 ret3 perche' se inserisco poi ret2 interseca 2 prati?

Boh...

piu' che altro il testo dice

Due prati possono sovrapporsi, anche solo parzialmente. Se un punto appartiene A DUE O PIU' prati, il valore....

E' qui che non capisco... Se sono due all'inizio e poi dopo due o piu'...

Posted by vlaste on 15-09-2005 16:01:

Io ho capito che infiniti prati possono sovrapporsi..... però li consideri a due a due, forse in quel senso dice "Due prati possono sovrapporsi"...
Effettivamente non è chiaro...

Posted by maynard80 on 15-09-2005 16:10:

dunque, per quanto riguarda la struttura dei prati non so ancora cosa utilizzare, è chiaro che sovraposti o meno no ci interessa molto (quando inserisci un prato se nessuno dei fiori gia esiste non è sovrapposto a nessuno e incremento la variabile globale di 1, se è sovrapposto qualche fiore il numero di campi non aumenta e il peso di quel fiore è sommato a quello gia esistente in quel punto)

il cammino è sempre lungo come la differenza Y1-Y0, da ogni fiore ci si sposta al + in tre altri fiori ui verticale, questo mi induce a pensare che tutti i cammini possibili siano un albero ternario e quello migliore sia quello con la foglia + pesante.

voi che dite?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by desrob on 15-09-2005 20:43:

2padri ???

si ma se usi un albero kon 3 rami, un fiore può essere ripetuto in + nodi , giusto ? kome fai a inserire un fiore ke è raggiungibile da 2 fiori, ke ha cioè 2 padri ? ...kosì dicendo diventerebbe un grafo !! o mi sbaglio ???

Posted by desrob on 15-09-2005 20:51:

ma visto ke è simile al progetto OLEODOTTI, xkè nessuno dall'animo gentile non lo posta nell'area filez ??

Posted by desrob on 15-09-2005 21:05:

ma visto ke è simile al progetto OLEODOTTI, xkè nessuno dall'animo gentile non lo posta nell'area filez ??

Posted by desrob on 15-09-2005 22:07:

ma voi a ke strutture avete pensato ??? io ho pensato di usare delle liste per ogni campo in cui ci inserisco i fiori kon i valori aggiornati se 2 prati si sovrappongono!
dei prati me ne frego visto ke nn m servono da nessuna parte ?? voi ke dite ???

Posted by maynard80 on 15-09-2005 22:08:

Originally posted by desrob
ma voi a ke strutture avete pensato ??? io ho pensato di usare delle liste per ogni campo in cui ci inserisco i fiori kon i valori aggiornati se 2 prati si sovrappongono!
dei prati me ne frego visto ke nn m servono da nessuna parte ?? voi ke dite ???

delle liste di liste?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by maynard80 on 15-09-2005 22:09:

o delle tabelle hash? l'RB Albero perchè non ti convince?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by desrob on 15-09-2005 22:26:

ma xkè liste di liste quando si può fare solo una semplice lista koncatenata! le tabelle hash e gli alberi RB li eliminio a priori visto ke sono troppo incasinati , se vuoi avete altre idee potete postarle visto ke le mie scarseggiano !! tnx

Posted by maynard80 on 15-09-2005 22:31:

più che altro come ordini la lista e soprattutto poi la devi sempre scorrere tutta.... a livello di ottimizzazione fa un po pena.... certo anche io sono abbastanza imbranato, ma se ci riesco a fare qualcosa di buono meglio. Meglio non scartare a priori una soluzione perchè "incasinata", è vero che è + dura da implementare, ma è sicuramente + efficiente

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by desrob on 15-09-2005 22:36:

l'importante è ke il programma funzioni, poi se funziona bene è meglio ! ma scegliere gli alberi RB è un suicidio, fattelo dire ..poi puoi fare quello ke vuoi !!!!

Posted by Frigging on 16-09-2005 00:16:

Un Inserimento in O(1) per una lista e' minore di un inserimento in un RB O(lgn), ma una ricerca in un RB O(lgn) e' minore che in una lista O(n^2)... di conseguenza dipende da cosa ci si deve fare...

Gli RB alberi implementati (senza accessori ) vengono sulle 500 righe di codice (commenti abbondanti inclusi).
Senza operazione di JoinRB.

Io escluderei cmq le tabelle hash, tries & company.

Rimangono in gioco:
- LISTE
- ALBERI

Cmq sono dell'idea che l'implementazione piu' difficile da ottimizzare e' quella della determinazione dei campi. Troppo dispendiosa... Secondo me si puo' fare di meglio di O(n^2).

Voi cosa avete pensato per determinare i campi?

Posted by Jaco on 16-09-2005 00:31:

A questo giro ci sono anch'io.Anch'io avevo pensato a delle liste di puntatori oppure tabelle hash,ma dagli altri progetti tutti hanno sempre usato liste o alberi e questo non mi sembra troppo diverso.

Posted by Frigging on 16-09-2005 00:50:

ma perche' avevate pensato alle tabelle hash?

Posted by livio_82 on 16-09-2005 03:14:

Ok, dopo aver letto tutti i vostri commenti, ora mi posso concedere la lettura del testo
Spero che la notte fonda mi aiuti nella comprensione.

Alea iacta est!

__________________
Livio

** Pone seram, cohibe, sed quis custodiet ipsos custodes? Cauta est et ab illis incipit uxor. **

www

Posted by drakend on 16-09-2005 05:42:

Con un albero RB come pensate di calcolare il cammino massimo?

Posted by Frigging on 16-09-2005 07:36:

Per cosa vorresti calcolare il cammino massimo? Quello di peso massimo?

Anch'io son daccordo che l'rb per quello non ve bene.

Posted by maynard80 on 16-09-2005 07:36:

Originally posted by drakend
Con un albero RB come pensate di calcolare il cammino massimo?

è proprio questo che non so fare, inizialmente avevo pensato ad un albero RB come struttura del piano, ma ora che devo pensare al calcolo del cammino massimo non saprei cosa utilizzare...

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by Paolo74GRS on 16-09-2005 11:23:

Ma secondo voi, per quanto riguarda la funzione di inserimento nuovo piano (function "i"), va fatto il controllo sul fatto che il piano che sto inserendo ed il file che vado ad utilizzare considerano lo stesso numero di punti=fiori?
..oppure considero non possibile il caso errato?

Posted by maynard80 on 16-09-2005 12:50:

Originally posted by Frigging
Per cosa vorresti calcolare il cammino massimo? Quello di peso massimo?

Anch'io son daccordo che l'rb per quello non ve bene.

beh invece dovrebbe essere possibile applicare un algoritmo di calcolo del cammino PESATO indipendentemente dalla struttura dati utilizzata, per questo la lista è una cacchiata con la sua complessità n^2 contro l'albero con complessità log(n).

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by Frigging on 16-09-2005 12:58:

Originally posted by maynard80
beh invece dovrebbe essere possibile applicare un algoritmo di calcolo del cammino PESATO indipendentemente dalla struttura dati utilizzata, per questo la lista è una cacchiata con la sua complessità n^2 contro l'albero con complessità log(n).

Se usi un albero rb come fai a mantenere la proprieta' di connessione tra un pto(x0,y0)e un punto(x1,y0) ad esempio?

Se usi l'rb che criterio di ordinamento di key vai a usare? E soprattutto si puo' muovere in 3 direzioni e non solo due .. di conseguenza l'albero binario non lo vedo giusto...

che ne pensi?

Meglio un albero normale...

Per quello chiedevo a cosa serviva l'rb se e' per il peso allora non va bene secondo me...

Mah adesso cmq ci penso un po su... se si puo' usare anche per la determinazione del cammino di peso massimo.

Posted by maynard80 on 16-09-2005 13:59:

Originally posted by Frigging
Se usi un albero rb come fai a mantenere la proprieta' di connessione tra un pto(x0,y0)e un punto(x1,y0) ad esempio?

Se usi l'rb che criterio di ordinamento di key vai a usare? E soprattutto si puo' muovere in 3 direzioni e non solo due .. di conseguenza l'albero binario non lo vedo giusto...

che ne pensi?

Meglio un albero normale...

Per quello chiedevo a cosa serviva l'rb se e' per il peso allora non va bene secondo me...

Mah adesso cmq ci penso un po su... se si puo' usare anche per la determinazione del cammino di peso massimo.

non capisco, la struttura dati è indipendente da queste cose, i nodi sono ordinati in base alla chiave (x,y) se un nodo non esiste non esiste il rispettivo fiore.
quando scorri l'albero per trovare il cammino sarà li e solo li che tra i parametri del cammino dici che sono permessi alcuni spostamenti (3 spostamenti) e memorizzi il percorso in una struttura di supporto dove andrà a finire solo il cammino prescelto.

ogni ricerca sarà sempre + veloce che in una lista ed esaminerà ricorsivamente i percorsi possibili restituendo quello migliore.

non deve in alcun modo interessare che il grafo sia costruito in base ai percorsi possibili, ma che sia efficiente.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by Frigging on 16-09-2005 14:08:

Originally posted by maynard80
non capisco, la struttura dati è indipendente da queste cose, i nodi sono ordinati in base alla chiave (x,y) se un nodo non esiste non esiste il rispettivo fiore.
quando scorri l'albero per trovare il cammino sarà li e solo li che tra i parametri del cammino dici che sono permessi alcuni spostamenti (3 spostamenti) e memorizzi il percorso in una struttura di supporto dove andrà a finire solo il cammino prescelto.

ogni ricerca sarà sempre + veloce che in una lista ed esaminerà ricorsivamente i percorsi possibili restituendo quello migliore.

non deve in alcun modo interessare che il grafo sia costruito in base ai percorsi possibili, ma che sia efficiente.

Avevo capito che la struttura la usavi in modo diverso. Sorry!

Posted by Jaco on 16-09-2005 16:24:

premetto che non ho ancora avuto molto tempo da dedicarci ma ora,d'accordo con maynard, proverò con un semplice albero.Non so se può essere superfluo ribadirlo(per alcuni posts) ma il piano esiste in funzione delle strutture dati che contengono i fiori e i campi,di per sè non è un problema implementare il piano in sè.

Posted by maynard80 on 16-09-2005 16:37:

Originally posted by Jaco
premetto che non ho ancora avuto molto tempo da dedicarci ma ora,d'accordo con maynard, proverò con un semplice albero.Non so se può essere superfluo ribadirlo(per alcuni posts) ma il piano esiste in funzione delle strutture dati che contengono i fiori e i campi,di per sè non è un problema implementare il piano in sè.

Alberi RB non semplici alberi

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by drakend on 16-09-2005 17:21:

Originally posted by maynard80
non capisco, la struttura dati è indipendente da queste cose, i nodi sono ordinati in base alla chiave (x,y) se un nodo non esiste non esiste il rispettivo fiore.
quando scorri l'albero per trovare il cammino sarà li e solo li che tra i parametri del cammino dici che sono permessi alcuni spostamenti (3 spostamenti) e memorizzi il percorso in una struttura di supporto dove andrà a finire solo il cammino prescelto.

Cioè tu vuoi far una specie di "albero di adiacenza"? Cioè un albero, rb o meno che sia, in cui in ogni nodo memorizzi una lista di puntatori agli elementi raggiungibili a partire da quel nodo?
Se è così ci avevo pensato pure io, però tieni conto di alcune cose:
1) devi farti un albero per ogni campo, a meno di stratagemmi particolari, e mettertelo in una lista.
2) gli algoritmi che calcolano i cammini massimi necessitano comunque di liste di adiacenza come input, per cui devi calcolarti le liste di adiacenza dalla struttura che usi ogni volta...

Posted by Frigging on 16-09-2005 17:49:

... Rieditato il post... avevo dimenticato i che si poteva solo muovere in alto

Posted by maynard80 on 16-09-2005 17:59:

Originally posted by drakend
Cioè tu vuoi far una specie di "albero di adiacenza"? Cioè un albero, rb o meno che sia, in cui in ogni nodo memorizzi una lista di puntatori agli elementi raggiungibili a partire da quel nodo?
Se è così ci avevo pensato pure io, però tieni conto di alcune cose:
1) devi farti un albero per ogni campo, a meno di stratagemmi particolari, e mettertelo in una lista.
2) gli algoritmi che calcolano i cammini massimi necessitano comunque di liste di adiacenza come input, per cui devi calcolarti le liste di adiacenza dalla struttura che usi ogni volta...

no no, semplicemente una struttura che memorizzi i pesi dei nodi dei fiori che esistono (l'ordinamento non ha importanza) ma essendo un rb albero il costo di ricerca sarà sempre log(n).
che me ne frega di sapere nel grafo come sono collegati, una volta che ho le coordinate xy come chiave so dove sono senza dover per forza mantenere nel grafo stesso la forma del prato.

una volta che so che in (1,1) c'è un nodo e voglio andare in (2,3) l'algoritmo (opportunemente definiti limiti di muovimento in X e Y che vanno controllati ricorsivamente) sa che può passare solo per (1,1)(1,2)(2,3) oppure (1,1)(2,2)(2,3), se queste strade esistono entrambe (sono presenti i nodi con le rispettive chiavi) sceglie quello con il peso maggiore (calcolato durante il viaggio stesso), diversamente non esiste un viaggio possibile.

in + tale algoritmo deve tenere traccia dei cammini esistenti per utilizzarli eventualmente in altri viaggi dove sono compresi, ma questa è un'aggiuta

l'albero RB mi serve solo per memorizzare i nodi esistenti e accedervi in maniera efficiente.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by drakend on 16-09-2005 19:25:

Originally posted by Frigging
Non possiamo usare, secondo me, gli algoritmi noti per il calcolo del cammino di peso massimo, in quanto prendendo in considerazione di utilizzare l'algoritmo di Floyd-Warshall che e' l'unico che prende in considerazione pesi negativi, non e' assicurata cmq la corettezza dell'algoritmo nel caso in cui esistano circuiti negativi.

Cmq secondo me questo progetto non e' poi cosi' facile implementarlo con una decente complessita'.

Capitolo 25.4 DAG-Shortest-Path, dal momento che il grafo formato dai vari fiori è orientato ed aciclico (si sale sempre verso l'alto). Alla fine del paragrafo c'è peraltro indicato il modo di calcolare i cammini critici: ah ovviamente supporta i pesi negativi, dal momento che sono presenti nel relativo esempio.

Posted by Frigging on 16-09-2005 21:26:

Originally posted by drakend
Capitolo 25.4 DAG-Shortest-Path, dal momento che il grafo formato dai vari fiori è orientato ed aciclico (si sale sempre verso l'alto). Alla fine del paragrafo c'è peraltro indicato il modo di calcolare i cammini critici: ah ovviamente supporta i pesi negativi, dal momento che sono presenti nel relativo esempio.

Scusa ... hai pienamente ragione ... e' che sono fuso mi ero completamente dimenticato che si poteva solo salire... ho buttato tre ore per nulla oggi pome uff!!!

Grazie mille

Posted by Shimoda on 17-09-2005 02:21:

A prescindere dall'applicazione e quindi dal contesto dell'attuale progetto..
Che differenza c'è a livello pratico tra una lista ordinata e un RBAlbero?
E' solo una questione di efficienza. Se la lista è ordinata sia l'inserimento sia la ricerca nel caso peggiore hanno complessità O(n) mentre per l'RBAlbero è O(lg n).
E su input grandi non è poco.. la ricerca tra 10^9 elementi in un RBAlbero avviene nel caso peggiore in 30 passaggi contro i 10^9 della lista...
Tralaltro l'albero può essere (visto) usato allo stesso modo di una lista tramite le funzioni successivo() e precedente().

A chi ha scritto come ordinare i punti con due coordinate direi che si può fare in base all'ascissa, e a parità di ascissa in base all'ordinata.

__________________
"What the Caterpillar calls the end of the World,
the Master calls a Butterfly"
(Il manuale del messia, Illusioni, Richard Bach)

Posted by drakend on 17-09-2005 07:39:

Originally posted by Shimoda
A chi ha scritto come ordinare i punti con due coordinate direi che si può fare in base all'ascissa, e a parità di ascissa in base all'ordinata.

Perché in base all'ascissa? Dovrebbe essere in base all'ordinata e, a parità di ordinata, in base all'ascissa.

Posted by Shimoda on 17-09-2005 16:24:

Originally posted by Shimoda
A prescindere dall'applicazione e quindi dal contesto dell'attuale progetto..

Era solo un esempio su come gestire le 2 coordinate

__________________
"What the Caterpillar calls the end of the World,
the Master calls a Butterfly"
(Il manuale del messia, Illusioni, Richard Bach)

Posted by drakend on 17-09-2005 17:43:

Originally posted by Shimoda
Era solo un esempio su come gestire le 2 coordinate

Sì hai ragione, sono io che mi sono confuso: nell'albero tu puoi stabilire l'ordine che ti pare per i punti, che non necessariamente rifletta quello del piano cartesiano.
Ad ogni modo:

Qualcuno conosce un programma per disegnare RB alberi?!? Mi spiego: gli do in input la struttura dei nodi dell'albero (anche con una stringa in formato specifico, non è un problema) e lui me lo disegna, con i pallini e gli archi di collegamento, magari se ci si può specificare un etichetta è meglio!

Posted by maynard80 on 17-09-2005 19:29:

a rigor di logica gli alberi binari sono efficaci come gli RB Alberi ed efficienti uguali, gli alberi RB sono bilanciati, ma i B Alberi sono molto + facili da implementare.

(questo me lo ha fatto notare Shimoda)

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by drakend on 17-09-2005 20:59:

Originally posted by maynard80
a rigor di logica gli alberi binari sono efficaci come gli RB Alberi ed efficienti uguali, gli alberi RB sono bilanciati, ma i B Alberi sono molto + facili da implementare.

(questo me lo ha fatto notare Shimoda)

Beh sai ci sono gli algoritmi già pronti di AlgoTeam: puoi benissimo basarti su quelli e personalizzare.

Posted by maynard80 on 17-09-2005 21:16:

Originally posted by drakend
Beh sai ci sono gli algoritmi già pronti di AlgoTeam: puoi benissimo basarti su quelli e personalizzare.

beh bisogna conoscere bene il codice che si presenta,e poi per trovare errori ed anomalie...

cmq sia io degli alberi RB non ho mai capito come si gestiscono le rotazioni ed i cambi di colore....

in + ancora non riesco a racapezzarmi su quale sia la procedura per trovare il cammino migliore.... trovare semplicemente uno per uno i cammini e poi vedere quello con il peso maggiore mi pare una ca@@ata

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by Jaco on 18-09-2005 18:10:

Dopo aver creato la struttura fiore e un'altra tipo lista che lo contenga sto cercando di implementare una tabella hash tipo a matrice con due array,cioè con una funzione hash che mi detetermini la locazione in base a x e y.in caso di collisione inserisco in testa nella lista.
..qualcuno mi dice che ne pensa?thx

Posted by Jaco on 18-09-2005 18:17:

visto che la struttura dati è indipendente dalla creazione successiva della lista di adiacenza ho pensato ad una struttura che non rifletta necessariamente l'ordinamento dei prati e veloce per la ricerca e l'inserimento...

Posted by Paolo74GRS on 19-09-2005 08:58:

Ragazzi... AiutooO!! Qualcuno mi puo' dare una dritta?? ..ci sto davvero impazzendo! Non riesco a trovare l'idea giusta per la gestione di questo progetto, il problema principale è proprio sulla gestione dei punti (fiori). Come faccio a gestire le sovrapposizioni? ..ragiono sui piani? ..ragiono sui campi? Oppure tengo sempre solo conto dei singoli punti? Un fiore lo distingo per la sua coordinata cartesiana e per la sua appartenenza ad un prato oppure ad un campo? Trovo troppe variabili nei casi che si possono presentare...
Se qualcuno mi gira la dritta che puo' sbloccare questo dilemma gli saro' sempre grato!! ;oP

Posted by Shimoda on 19-09-2005 12:53:

Originally posted by drakend
Qualcuno conosce un programma per disegnare RB alberi?!?

Questo è l'unico che conosca.. è molto carino per vedere come funzionano gli rb-alberi

__________________
"What the Caterpillar calls the end of the World,
the Master calls a Butterfly"
(Il manuale del messia, Illusioni, Richard Bach)

Posted by mitnik on 19-09-2005 13:38:

ciao a tutti come procedono i lavori? io ora stao cercando di capire come calcolare i campi presenti nel piano! Non ho molte idee anche perchè non mi sembra semplicissimo considerato il fatto che poi nella funzione elimina si dovra cancellare dal piano il campocompleto contenente il fiore dato in input!

Voi come fate?

Posted by maynard80 on 19-09-2005 19:02:

Originally posted by mitnik
ciao a tutti come procedono i lavori? io ora stao cercando di capire come calcolare i campi presenti nel piano! Non ho molte idee anche perchè non mi sembra semplicissimo considerato il fatto che poi nella funzione elimina si dovra cancellare dal piano il campocompleto contenente il fiore dato in input!

Voi come fate?

beh il numero dei campi secondo me va calcolato in inserimento e incrementato quando si forma un nuovo campo (nel caso in cui tutti i fiori inseriti non si sovrappongono a nessuno)

cancellare tutto un campo significa ricorsivamente cancellare tutti i fiori attorno a quello dato fino a che non ci sono + fiori a cui si può arrivare (è simile all'algoritmo dei cammini)

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by Paolo74GRS on 19-09-2005 21:52:

..un viaggio della nostra cara Ape è possibile se eseguito tra i due fiori (X0, Y0 ed X1, Y1) i quali dovrebbero essere dello stesso campo, giusto? Ma potrebbero essere validi anche viaggi su campi diversi?

Posted by Paolo74GRS on 19-09-2005 22:02:

MMmmhh...
Direi che il viaggio è possibile anche se esistono entrambi i punti..
Certo.. Certo! ;oP

Posted by maynard80 on 20-09-2005 07:38:

Originally posted by Paolo74GRS
MMmmhh...
Direi che il viaggio è possibile anche se esistono entrambi i punti..
Certo.. Certo! ;oP

invece no perchè la nostra ape si può muovere solo di un passo alla volta, e per saltare da un campo ad un altro dovrebbe superare questa limitazione ---> i viaggi sono validi solo nello stesso campo di (X0,Y0)

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by Frigging on 20-09-2005 07:42:

Io non condivido invece che il viaggio deve essere fatto solo nello stesso campo. Puo' essere che due prati siano adiacenti, e quindi non si sovrappongono. L'ape puo' saltare quindi su campi diversi a patto che siano adiacenti, ovvero che l'equazione delle coordinate del progetto siano ancora verificata.

Almeno io ho capito cosi'...

Posted by drakend on 20-09-2005 07:52:

Originally posted by Frigging
Io non condivido invece che il viaggio deve essere fatto solo nello stesso campo. Puo' essere che due prati siano adiacenti, e quindi non si sovrappongono. L'ape puo' saltare quindi su campi diversi a patto che siano adiacenti, ovvero che l'equazione delle coordinate del progetto siano ancora verificata.

Almeno io ho capito cosi'...

Idem, non c'è scritto da nessuna parte nel testo del progetto che un ape non si può muovere da un campo all'altro. Per questo anche i campi sono abbastanza inutili: bisogna tenerne traccia solo perché bisogna evidenziarne il numero, se no si potrebbe mettere direttamente i fiori nel piano e basta.

Posted by mitnik on 20-09-2005 08:48:

ma un campo è formato da uno o più prati se questi hanno in comune almeno un punto! Quindi per formare un campo non è necessario che due prati si sovrappongano ma possono anche essere adiacenti; si conseguenza viaggi da un prato all'altro sono possibile perchè appartenenti allo stesso campo; per contro invece viaggi tra campi diversi non sono possibili!

Per quanto riguarda la formazione dei campi sono giunto alla conclusione (forse sbagliata) che ad ogni insderimento di un nuovo prato devo ricalcolare e "riformare" la struttura contenente i campi! Giusto secondo voi?

Posted by Frigging on 20-09-2005 09:06:

Originally posted by mitnik
ma un campo è formato da uno o più prati se questi hanno in comune almeno un punto! Quindi per formare un campo non è necessario che due prati si sovrappongano ma possono anche essere adiacenti; si conseguenza viaggi da un prato all'altro sono possibile perchè appartenenti allo stesso campo; per contro invece viaggi tra campi diversi non sono possibili!

Per quanto riguarda la formazione dei campi sono giunto alla conclusione (forse sbagliata) che ad ogni insderimento di un nuovo prato devo ricalcolare e "riformare" la struttura contenente i campi! Giusto secondo voi?

Due prati adiacenti non formano un campo. Un campo e' formato solamente da due o piu' prati che si sovrappongono.

Leggo nel testo:

Due prati A e B sono connessi se esiste una sequenza P1 , . . . , Pn di prati tale che A = P1 , B = Pn e per
ogni i ∈ {1, . . . , n − 1}, Pi ∩ Pi+1 != 0

Posted by mitnik on 20-09-2005 09:35:

Originally posted by Frigging
Due prati adiacenti non formano un campo. Un campo e' formato solamente da due o piu' prati che si sovrappongono.

Leggo nel testo:

Due prati A e B sono connessi se esiste una sequenza P1 , . . . , Pn di prati tale che A = P1 , B = Pn e per
ogni i ∈ {1, . . . , n − 1}, Pi ∩ Pi+1 = 0

nel testo dice .........Pi (int) Pi+1 =/(diverso) 0.

Infatti nell'esempio illustrato si hanno i prati 5,4,7,6 6,6,8,8 5,8,6,9. In questo caso il secondo e il terzo prato hanno in comune solo un vertice eppure fanno parte dello stesso campo

Posted by drakend on 20-09-2005 09:46:

Originally posted by Frigging
Due prati adiacenti non formano un campo. Un campo e' formato solamente da due o piu' prati che si sovrappongono.

Leggo nel testo:

Due prati A e B sono connessi se esiste una sequenza P1 , . . . , Pn di prati tale che A = P1 , B = Pn e per
ogni i ∈ {1, . . . , n − 1}, Pi ∩ Pi+1 = 0

Non è un = 0 sai? Nel file pdf c'è scritto che pi intersecato a pi+1 deve essere diverso dall'insieme vuoto, non che deve essere uguale...

Posted by mitnik on 20-09-2005 09:56:

Originally posted by drakend
Non è un = 0 sai? Nel file pdf c'è scritto che pi intersecato a pi+1 deve essere diverso dall'insieme vuoto, non che deve essere uguale...

Si lo so che non è uno zero.

Ma scusa appunto perchè dice che deve essere diverso dall'insieme vuoto anche solo un punto in comune può andare bene! A me sembra chiaro che se sue prati hanno almeno un punto in comune (quindi l'intersezione è diversa dall'insieme vuto) appartengono allo stesso campo!

Posted by mitnik on 20-09-2005 10:31:

che funzioni usate per dare il file in input alla funzione inserisci?

Posted by Frigging on 20-09-2005 10:36:

Originally posted by drakend
Non è un = 0 sai? Nel file pdf c'è scritto che pi intersecato a pi+1 deve essere diverso dall'insieme vuoto, non che deve essere uguale...

Non e' venuto giusto cut and paste sorry

Posted by Frigging on 20-09-2005 10:40:

Ma se ho R(0,0,5,5) R2(6,0,7,5) non sono un campo ma cmq l'ape puo' fare un viaggio. No?

Sbaglio qualcosa?

Posted by eskimo on 20-09-2005 11:02:

Io ho chiesto a fiorentini qualche giorno fa riguardo al problema fra viaggi tra due campi diversi... ed è possibile! non capisco cosa insista mitnik...
due prati sono connessi se hanno almeno un punto in comune (o sono connessi attraverso un altro prato ma con la stessa regola del punto in comune)... se quindi due prati sono adiacenti non sono connessi (e formano due campi) ma io posso lo stesso fare un viaggio! basta che le coordinate me lo consentano!!

io sono ancora in alto mare nel pensare come farlo: invece di un albero pensavo al grafo su cui posso usare un algoritmo che trova cammini minimi (noi troviamo il max)-il problema è la rappresentazione del grafo!!!- infatti bisogna mappare le coordinate come vertici in array! adesso cercherò una soluzione a questo ma come procedimento mi sembra il migliore, perchè mantengo i nodi del grafo collegati in base alla vera connettività, cioè se c'è il link c'è anche la possibilità di un viaggio secondo le specifiche...
voi che ne pensate? c'è qualcuno che usa i grafi???

Paolo

Posted by mitnik on 20-09-2005 13:14:

Io volevo solo avere chiare le idee su quando si ha un campo e se utilizzate una struttura apposta per i campi che aggiornate o meglio deve essere rifatta ad ogni inserimento di un prato perche per esempio io inserisco il prato 0 0 2 2 poi il prato 2 3 4 5 ho due campi nel piano. Poi inserisco il prato 2 2 3 3 e tutti vanno accorpati in un unico campo!

Posted by maynard80 on 20-09-2005 13:51:

ok allora
- se 2 fiori sono dello stesso campo viaggio --> ok
- se 2 fiori sono di 2 campi adiacenti viaggio --> ok
- se 2 fiori appartengono a 2 campi non adiacenti viaggio --> no

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by allxxx on 20-09-2005 14:04:

qui c'è il codice degli alberiRB, vorrei modificarlo per avere la possibilità di gestirlo con una coppia di chiavi (ascissa e ordinata) e non una sola

la struttura principale per capirci è

code:
typedef int key;

typedef enum { red, black } color;

struct rbnode {
	key v;
	color c;
	struct rbnode *left, *right, *up;
}; 

typedef struct rbnode rbnode;

typedef struct {
	rbnode *root, *nil;
} rbtree;

(tra l'altro non so come inserire il valore del dato, qui vedo solo la chiave ed il colore)

qualche anima pia che guarda il file in allegato e mi dice dove effettuare le modifiche

__________________
IL MIGLIOR TELEFILM TRA I MIGLIORI.... VOTA!!

Posted by eskimo on 20-09-2005 14:30:

Io sono ancora indeciso su che fare.... a quanto pare tutti usano strutture più o meno efficienti per memorizzare tutto e velocizzare ricerca e inserimento, ma poi è un casino tirare fuori tutti i cammini e valutare il più pesante...
io avrei fatto un grafo che permetteva di trovare facilmente i cammini (semplicemente perchè gli algoritmi ci sono già) ma per implementarlo è un casino! principlamente non riesco a mappare le coordinate dei fiori negli indici degli array per trovare i vertici!!! help please!
P.

Posted by mitnik on 20-09-2005 16:04:

una domanda! se un prato si sovrappone per qualche punto ad un altro i valori dei fiori cambiano prendendo quelli del prato inserito per ultimo?

Posted by Frigging on 20-09-2005 16:12:

Originally posted by mitnik
una domanda! se un prato si sovrappone per qualche punto ad un altro i valori dei fiori cambiano prendendo quelli del prato inserito per ultimo?

Si sommano

Posted by mitnik on 20-09-2005 16:20:

ah è vero non ci avevo pensato! grazie

Posted by Frigging on 20-09-2005 17:22:

C'e' un errata corrige del progetto. Semplicemente un valore errato nei file txt.

Posted by drakend on 20-09-2005 17:53:

Originally posted by maynard80
ok allora
- se 2 fiori sono dello stesso campo viaggio --> ok
- se 2 fiori sono di 2 campi adiacenti viaggio --> ok
- se 2 fiori appartengono a 2 campi non adiacenti viaggio --> no

Sì ma tanto l'astrazione dei campi non serve a niente nel calcolo del viaggio. Ti fai un cammino possibile seguendo le solite tre regole di movimento, quindi ti basi sulle coordinate del punto successivo, ignorando tranquillamente i campi.

Posted by Paolo74GRS on 21-09-2005 00:36:

Quali valori si potrebbero assegnare a dei campi di tipo int per un nodo sentinella(NIL) ???
..non mi viene in mente nulla, anche perchè il piano cartesiano già prevede le coordinate di tipo int negativo, oppure no ??? :wall:

Posted by drakend on 21-09-2005 06:20:

Originally posted by Paolo74GRS
Quali valori si potrebbero assegnare a dei campi di tipo int per un nodo sentinella(NIL) ???
..non mi viene in mente nulla, anche perchè il piano cartesiano già prevede le coordinate di tipo int negativo, oppure no ???

Ma perché devi usare la sentinella?

Usa NULL e basta...
Le coordinate possono essere anche negative ovviamente, infatti nelle specifiche dice che x ed y appartengono a Z, cioè l'insieme dei numeri interi relativi.

Posted by Paolo74GRS on 21-09-2005 13:19:

..la necessità di utilizzare la sentinella è per la gestione degli alberi RB, ho scelto quella come struttura, mi sbaglio? :eek:

Posted by Frigging on 21-09-2005 14:04:

Se usi l'RB e' necessaria la sentinella in quanto devi rappresentare le foglie NIL come nere, altrimenti non rispetteresti una delle proprieta' del red-black tree.

Posted by drakend on 21-09-2005 14:12:

Originally posted by Frigging
Se usi l'RB e' necessaria la sentinella in quanto devi rappresentare le foglie NIL come nere, altrimenti non rispetteresti una delle proprieta' del red-black tree.

Non è vero che è essenziale usare queste sentinelle. Infatti il libro dice, a pagina 255, che:

"Per semplificare nel codice sorgente la gestione dei casi limite si usa la sentinella invece del valore NIL."

La sentinella semplifica la gestione dei casi limite nella funzione di cancellazione, perché fa scomparire alcune condizioni dai vari if, tutto qua. Infatti io ho preso l'implementazione degli alberi RB dal algoteam e l'ho adattata togliendo le sentinelle e usando il valore NULL perché mi risulta più semplice la comprensione.

PS Ovviamente genero alberi RB rispettosi delle quattro proprietà...

Posted by eskimo on 21-09-2005 14:41:

quindi nessuno ha fatto come me... lo deduco dal deserto di risposte! cmq anche io userò un albero e mi sbatto ricorsivamente a cercare i cammini, alla fine forse è mejo...

domanda: vi sbattete tutti a fare gli RB? perchè se si riuscisse a mettere bene le chiavi in un albero binario secondo me può venire lo stesso bilanciato e quindi rimanere O(lgn)... cmq la domanda vera è come disporreste le chiavi? in base all'ordinata e in caso di parità in base all'ascissa o a caso e si spera nel bilanciamento?

Posted by Paolo74GRS on 21-09-2005 15:41:

Siccome il nodo NIL mi sembra OK come soluzione mi chiedo che valori potrei dare alle variabili di tipo int X e Y.. per esempio..

Posted by eskimo on 21-09-2005 17:27:

io ho seri problemi con ste' chiavi... sto usando RB... io cerco di inserire a nel sottoalbero a sx se l'ascissa è minore e nel sottoalbero dx se è maggiore, se l'ascissa è uguale allora vado a sx se l'ordinata è minore e a dx se è maggiore...
così però non mi va!!! help...please... :wall:

Posted by Frigging on 21-09-2005 22:14:

Originally posted by drakend
Non è vero che è essenziale usare queste sentinelle. Infatti il libro dice, a pagina 255, che:

"Per semplificare nel codice sorgente la gestione dei casi limite si usa la sentinella invece del valore NIL."

La sentinella semplifica la gestione dei casi limite nella funzione di cancellazione, perché fa scomparire alcune condizioni dai vari if, tutto qua. Infatti io ho preso l'implementazione degli alberi RB dal algoteam e l'ho adattata togliendo le sentinelle e usando il valore NULL perché mi risulta più semplice la comprensione.

PS Ovviamente genero alberi RB rispettosi delle quattro proprietà...

Non sara' essenziale ma secondo il mio modesto parere semplifica di molto la stesura e la comprensione del codice. Poi per sentinella io rappresento semplicemente un puntatore al valore NIL da me definito che rappresenta una foglia nera. Nulla di piu'.

Se poi la sentinella, la sotitituisci con NULL o con altro l'importante e' avere sempre un riferimento per i nodi che non puntano a nulla.

Non voglio togliere nulla al codice che tu hai preso da algoteam e modificato secondo le tue necessita'.

Grazie per aver cercato anche il numero di pagina

Posted by cristiano on 22-09-2005 13:10:

Qualcuno si esprimerebbe su questo?:
Visto che per la determinazione dei cammini devo comunque usare una lista di adiacenza ho pensato di usare direttamente una lista(ogni elemento è un vertice del grafo)con connesse delle altre liste di adiacenza.In questo modo avrei un'unica struttura per contenere i dati(piuttosto che un albero o altro) e per interrogarli..certo che la complessità è n,ed è un pò tanto....ma sto progetto è un casino.Thanks

Posted by eskimo on 22-09-2005 13:25:

cristiano: ciao anche io volevo usare un grafo, ma quando mi sono trovato di fronte alla necessità di usare liste per memorizzare i vertici da cui partono le adiacenze ho desistito... cmq la complessità è n per l'uso di liste, ma se poi ci applichi algoritmi efficienti magari sono migliori di quelli che cercano punto per punto i fiori per eseguire i cammini ricorsivamente su strutture più efficienti della tua...
io cmq uso un RB ormai... non so, mi torna voglia di grafoooo!

Posted by cristiano on 22-09-2005 14:05:

Quindi pensi di usare un RB per la complessità lg n contro quella n della lista?Oppure perchè la rappresentazione di grafi è un casino?(infatti sto cercando in rete del codice da personalizzare perchè da solo è un macello).
Mi pare che l'unico vantaggio che ne avrei sarebbe la quantità minore di mem. poichè uso la lista di aiacenza sia per contenere i dati che per costruire cammini.Con un'altra struttura dovrei cercare e inserire lì ma devo cmq creare una lista di adiacenza.....confusione alla n!!!
Cmq grazie.

Posted by eskimo on 22-09-2005 14:44:

si anche io mi sono "rassegnato" agli alberi... perchè un grafo lo sceglievo perchè mi dava la topologia del piano ed era facile trovare i cammini... ma che sbattimento implementarlo senza array...

Se qualcuno ha un'idea per i campi... la posti please... io per adesso sto cercando di vedere se posso calcolarli mettendo un campo apposito in ogni fiore che ne da l'appartenenza ad un determinato campo, assegnando il valore da un contatore di campi che viene incrementato. Il problema di questo approccio è quando inserisco un prato che UNISCE DUE CAMPI DISTINTI (come appunto capita per i primi tre prati dell'esempio di input del testo!!)

sarebbe un problema di connettività, quindi potrebbe essere risolto con un algoritmo union-find.... adesso spulcio il Cormen

Posted by Shimoda on 22-09-2005 22:34:

Ho l'impressione che l'algoritmo per la ricerca dei cammini minimi da una singola sorgente di Dijkstra sia perfettamente adattabile al nostro scopo con poche piccole modifiche..

__________________
"What the Caterpillar calls the end of the World,
the Master calls a Butterfly"
(Il manuale del messia, Illusioni, Richard Bach)

Posted by cristiano on 22-09-2005 23:41:

cmq Per i grafi sto usando delle liste,non array.riguardo il problema dell'appartenenza ad un campo ho letto qualcosa cap. 22 del cormen,dove un elemento dell'insieme è "eletto" rappresentante e si fa riferimento a quello...per l'implementazione per ora BHO!.

Posted by eskimo on 23-09-2005 10:43:

Shimoda quindi tu hai usato un grafo??

Posted by Shimoda on 23-09-2005 12:31:

Originally posted by eskimo
Shimoda quindi tu hai usato un grafo??

no, un rb-albero per tutti i fiori del piano.. poi userò qualche altra struttura, probabilmente altri rb-alberi per tener traccia dei prati e dei campi..
l'intenzione è di creare, quando è richiesto di calcolare un viaggio, una lista di adiacenza contenente solo i fiori che possono essere attraversati in quel determinato viaggio, e applicarvi l'algoritmo di Dijkstra modificato

__________________
"What the Caterpillar calls the end of the World,
the Master calls a Butterfly"
(Il manuale del messia, Illusioni, Richard Bach)

Posted by nocIvo on 23-09-2005 15:57:

io per i campi ho pensato ad un controllo sul perimetro del prato, mi spiego meglio...controllo se ogni punto del piano su ogni lato adiacente al prato contiene un fiore, se nn ho fiori adiacenti x nessun lato incremento la variabile campo,se ce li ho su un lato non la incremento, se ce li ho su 2 la decremento(caso che si presenta nell'esempio del prof)in quanto 2 lati occupati vul dire avere unito 2 campi "distanti" tra loro, si può contemplere infine un caso limite di tutti i lati occupati che vuol dire prati sovrapposti dove come nel caso di un lato occupato la variabile campo rimane
invariata...io l'ho buttata giù così...può andar bene?si accettano consigli e ovviamente critiche

Posted by Ziotony.f4f on 23-09-2005 17:30:

Io non ho partecipato alle varie discussioni sul forum, ma per implementare le strutture ho usato alberi binari, ogni nodo è un punto con le sue belle coordinate e indicatore di campo, quindi per le varie intersezioni e adiacenze controllo semplicemente la presenza dei punti, i PRATI non li considero perchè non mi servono a nulla. Ho testato il prog. con gli input e funzia tutto, ma qualcuno ha altri input e output per testare?

Posted by Ziotony.f4f on 23-09-2005 17:32:

Ah dimenticavo, vi sonsiglio vivamente di testare il vostro progetto con GCC sotto Linux , una versione recente , tipo la fedora 4 (che usa Fiorentini), eviterete spiacevoli sorprese !!!!

Posted by drakend on 23-09-2005 19:12:

Originally posted by Ziotony.f4f
Ah dimenticavo, vi sonsiglio vivamente di testare il vostro progetto con GCC sotto Linux , una versione recente , tipo la fedora 4 (che usa Fiorentini), eviterete spiacevoli sorprese !!!!

Quali sorprese scusa? L'ho giusto testato sotto Fedora 4 e non mi dà nessun problema.

Posted by Ziotony.f4f on 24-09-2005 10:38:

Si, certo, io infatti mi rivolgevo alle persone che hanno usato compilatori sotto windows, visto che puo´ essere che in uno dei tanti processi non venga assegnato un valore NULL a un puntatore, sotto WIN , a questo verra´ automaticamente assegnato il valore NULL, mentre sotto LINUX, NOO. quindi c´é un seg. fault . Se il programma gira sotto WIN non e´ detto che vada con LINUX, ma e´ vero l´ inverso !! Questo almeno e´ cio´ che mi e´ capitato col progetto di Luglio !!

Posted by drakend on 24-09-2005 10:46:

Originally posted by Ziotony.f4f
Si, certo, io infatti mi rivolgevo alle persone che hanno usato compilatori sotto windows, visto che puo´ essere che in uno dei tanti processi non venga assegnato un valore NULL a un puntatore, sotto WIN , a questo verra´ automaticamente assegnato il valore NULL, mentre sotto LINUX, NOO. quindi c´é un seg. fault . Se il programma gira sotto WIN non e´ detto che vada con LINUX, ma e´ vero l´ inverso !! Questo almeno e´ cio´ che mi e´ capitato col progetto di Luglio !!

Scusa ma se tu il puntatore lo inizializzi a NULL come fa a non assumere quel valore?

Posted by Paolo74GRS on 24-09-2005 16:04:

..qualcuno mi sa dare una dritta su come gestire linput del "filename.txt" ???
Sto perdendo un sacco di tempo per gestire questa stringa in input come una sequanza di char, etc.. etc...

Mi sapete dare una dritta per uscire da questo loop? :bubble:

Posted by Ziotony.f4f on 24-09-2005 17:16:

DAI UN OCCHIO ALL'AREA FILEZ , SPERO DI ESSERE STATO UTILE A TUTTI QUELLI CHE HANNO QUESTO PROBLEMA !!!
..ah dimenticavo per l'input del nome io ho usato %s , un' array di caratteri di lunghezza 20, spero basti !!!!

Posted by Paolo74GRS on 25-09-2005 12:07:

Ok.. proverò a dare un'occhiata nella sezione FileZ.. Grazie 1000!
Quindi con il %s di scanf() riesci a caricare direttamente la stringa in un array?

Posted by raffi83 on 25-09-2005 16:53:

Ziotony scusami non ho capito molto come fai a non considerare i prati...
Dici che basta aggiungere ad ogni fiore un puntatore al suo campo ? E i campi come li memorizzi ? Grazie mille !

Posted by Paolo74GRS on 26-09-2005 08:53:

Una questione relativa all'input..
..quando vado ad inserire il nuovo piano devo effettuare dei controlli per quanto riguarda il match tra numero elementi numerici nel file ed il numero di punti/fiori del piano da inserire?

Secondo quello che interpreto dal testo dovrei ritenere l'input valido, ma non so se questo caso va considerato..
Inoltre mi domando se i 2 punti in ingresso per definire il piano sono sempre nell'ordine angolo basso sx, angolo alto dx, oppure devo gestire l'input? :help:

Grazie in anticipo a tutti! :smokin:

Grazie Ziotony.. Ottimo post sull'arg[v] file..
Many Thanks! :lode:

Posted by Frigging on 26-09-2005 09:30:

Originally posted by Paolo74GRS
Una questione relativa all'input..
..quando vado ad inserire il nuovo piano devo effettuare dei controlli per quanto riguarda il match tra numero elementi numerici nel file ed il numero di punti/fiori del piano da inserire?

Secondo quello che interpreto dal testo dovrei ritenere l'input valido, ma non so se questo caso va considerato..
Inoltre mi domando se i 2 punti in ingresso per definire il piano sono sempre nell'ordine angolo basso sx, angolo alto dx, oppure devo gestire l'input?

Grazie in anticipo a tutti!

Grazie Ziotony.. Ottimo post sull'arg[v] file..
Many Thanks!

Io ho capito cosi dal testo quando dice che x e' compresa tra x0 e x1 e y tra y0 e y1.
Di consegunza angolo basso - angolo alto per farla semplice.

Qualcuno ha voglia di fare qualche test di modo da controllare se il prog funzica?

Posted by Ziotony.f4f on 26-09-2005 09:56:

Per testare il prog. ho scritto una mail a Fiorentini per chiedergli se mi manda degli INPUT-OUTPUT, altrimenti dovremmo ingegnarci da soli, io ho provato con i test dei 2 esempi del testo, cioe' quello gia' fatto alla fine e quello del disegno. Spero risponda...

P.S. Per la questione dei prati, secondo me non serve a nulla mantenere i dati che individuano il prato stesso, tanto poi devo lavorare solo sui campi, vedi comandi elimina e campi . Io considero i miei campi come punti , messi tutti insieme in un albero, per distinguere campi diversi, ha aggiunto il campo CAMPO al nodo dell' albero.

Posted by Frigging on 26-09-2005 10:01:

ZioTony proviamo a fare degli esempi noi, e confrontare poi il nostro output.

che dici?

Posted by Ziotony.f4f on 26-09-2005 10:07:

Va benone, hai gia' qualche input preparato, con i relativi files di testo?? Io preparo qualcosa e poi posto i miei nell'area filez... anche con i relativi miei OUTPUT

Posted by Frigging on 26-09-2005 10:39:

Ora come ora sto ordinando il codice... perche' ho cambiato carattere del testo ed ha sballato le tabulazioni ... uff che sbatti... appena finisco questo lavoraccio posto i files.

Piu che altro sono su percorsi molto grandi che non posso controllare a mano.
Tipo
i -1000 -1000 1000 1000
v 500 -1000 500 1000

cose del genere.

Cmq finisco di ordinare il codice e vedo di postarli.

Posted by cristiano on 26-09-2005 11:53:

Riguardo la corretteza dell'input...quando abbiamo delle coordinate negative queste sono sempre tutte negative o dobbiamo aspettarci qualcosa tipo (-4,0,2,8,nomefile)?se e' così sarebbe un caso in più ed è un casino.Thankz.

Posted by cristiano on 26-09-2005 11:55:

...e poi..giusto per mal comune mezzo gaudio:ma qualcuno è già arrivato all'algoritmo per det. i cammini?io sono ancora sulla costruzione dei prati da input...non mi passsa più!

Posted by zac111 on 26-09-2005 12:47:

dubbio:quando inserisco il prato con il file di testo, quindi calcolo
il viaggio,il programma deve uscire dall'esecuzione oppure mi deve
permettere di continuare l'inserimento nella stessa esecuzione???
la pazzia oramai....

Posted by Frigging on 26-09-2005 14:39:

Ho scritto questo programmino stupidissimo per generare casualmente il valore dei fiori in base alle coordinate del prato.

Magari a qualcuno puo' interessare.

code:#include <stdio.h>
#include <stdlib.h>

/*
        Passare come parametri le coordinate del prato  x0 y0 x1 y1 
        e un numero che fara' da resto per restringere il range
        dei numeri generati casualmente.
*/

int main(int argc, char *argv[])
{
        int i;
        int x0, y0, x1, y1, mod, n;

        if(argc == 6)
        {
                srandomdev();
                srand48(random());

                x0 = atoi(argv[1]);
                y0 = atoi(argv[2]);
                x1 = atoi(argv[3]);
                y1 = atoi(argv[4]);
                mod = atoi(argv[5]);

                n = (x1 - x0 + 1) * (y1 - y0 + 1);

                for (i = 1; i <= n; i++)
                        printf(" %d", (mrand48())%(mod)); 
        }
        else
                printf("Syntax is: x0 y0 x1 y1 mod");

        printf("\n");
        return 0;
}

Posted by eskimo on 26-09-2005 14:41:

Ciao come trattate i valori negativi? ok che gli interi li prevedono ma a me capita che la funzione fgetc() mi restituisca prima il - come carattere e poi il numero.... io li metto tutti in un array e quando vado a stampare il contenuto dell'array mi stampa prima il - e poi il numero!!!
dove sbaglio?

Posted by Frigging on 26-09-2005 14:47:

Non funziona perche' prende un carattere.
Usa:

code:
int
fscanf(FILE * restrict stream, const char * restrict format, ...);

Posted by eskimo on 26-09-2005 15:14:

ah ok... devo usare la fscanf e digli di usare %d come formato!!!
thx...

un'altra cosa: chi di voi ha pensato di fare la funzione VIAGGIO in mod o che operi ricorsivamente? perchè ho dei problemi... come andate avanti nella ricorsione? incrementando il punto di partenza fino alla fine o il punto finale fino alla fine? (spero di essermi spiegato, punto di partenza o punto finale sono i due parametri di viaggio(xstart,ystart,xend,yend))

Posted by Frigging on 26-09-2005 15:35:

Se qualcuno vuole fare dei test mi faccia sapere che ci si organizza....

Posted by drakend on 26-09-2005 17:42:

Originally posted by Frigging
Ho scritto questo programmino stupidissimo per generare casualmente il valore dei fiori in base alle coordinate del prato.

Magari a qualcuno puo' interessare.

Ciao grazie per il programmino, è molto interessante ma mi dà questi errori qua:

code:
cc8Gbaaa.o(.text+0x6a):generatore.c: undefined reference to `srandomdev'

cc8Gbaaa.o(.text+0x6f):generatore.c: undefined reference to `random'

cc8Gbaaa.o(.text+0x77):generatore.c: undefined reference to 'srand48'

cc8Gbaaa.o(.text+0x106):generatore.c: undefined reference to ìmrand48'

Da che può dipendere?

Posted by Frigging on 26-09-2005 18:30:

Hai incluso stdlib.h, le definizioni di quelle funzioni sono li.

Io compilato sotto unix, uso mac per la precisione.

Posted by eskimo on 26-09-2005 20:36:

nessuno che ha usato un metodo ricorsivo per i cammini?

Posted by Frigging on 27-09-2005 08:37:

Dubbio: ma una volta che si costruisce un viaggio di qualita' massimo non e' richiesto di cambiare il contenuto dei fiori? Vero?

Cioe' io ho pensato: se l'ape esegue il viaggio se lo mangia ilnettare e il fiore ne rimane senza di conseguenza si azzera il suo valore....

Ho riletto il testo e non specifica nulla... sara' solo una paranoia... ma preferisco una vostra conferma

Posted by Ziotony.f4f on 27-09-2005 09:13:

Originally posted by Frigging
Dubbio: ma una volta che si costruisce un viaggio di qualita' massimo non e' richiesto di cambiare il contenuto dei fiori? Vero?

Cioe' io ho pensato: se l'ape esegue il viaggio se lo mangia ilnettare e il fiore ne rimane senza di conseguenza si azzera il suo valore....

Ho riletto il testo e non specifica nulla... sara' solo una paranoia... ma preferisco una vostra conferma

SIAMO ALLA FOLLIA ORMAI !!!! Tutto cio' che hai detto e' totalmente parto delle tue mente, offuscata da questo progetto...

Posted by mitnik on 27-09-2005 09:37:

Qualcuno ha dei test da fare? oppure indicare qualche caso particolare per testare il progetto?

Posted by eskimo on 27-09-2005 09:46:

Scusate insisto di nuovo: qualcuno ha qualche dritta per l'algoritmo che calcola i cammini? se fatto in modo ricorsivo meglio, altrimenti altre idee??
thx P.

Posted by Frigging on 27-09-2005 10:13:

ahahah oramai sono bruciato!!!
Si io ho dei testa da fare te li allego.

Posted by zac111 on 27-09-2005 10:26:

scusatem ma avete ottimizzato al massimo? o anche un algoritmo
non superottimizzato potrebbe andare bene?

Posted by Frigging on 27-09-2005 17:19:

qualche commento sui test?

Posted by maynard80 on 27-09-2005 18:30:

ragazzi non capisco un paio di cose:

code:
nel progetto dice:"valore intero v(x; y) (eventualmente negativo) che 
rappresenta la
qualitò del nettare del fiore stesso estraibile dall'ape (un valore 
negativo denota nettare di scarsa qualità e quindi tendenzialmente 
trascurabile)."

vuol dire che un valore negativo nei cammini non deve essere preso in considerazione e quindi contato come 0? (se fosse così l'algoritmo per il cammino pesato sarebbe uno di quelli proposti nel corso)

code:Un campo C e un insieme C massimale di prati connessi, vale a 
dire:
 Per ogni coppia di prati A;B 2 C, A e connesso con B.
 Per ogni A 2 C e ogni prato P del piano tale che P 62 C, A non connesso con P.

vuol dire che se 2 prati sono adiacenti ma nessuno dei fiori è in comune non formano un campo ma sono di campi distinti (es prato1= {(0,0)(2,2)} prato2={3,0)(5,2)} sono adiacenti ma non formano un campo perchè non hanno nessun fiore in comune, e quindi non sono contigui)

in + per mantenere le informazioni sui campi voi avete inserito una variabile campo in ogni fiore (semplice ma come ottimizzazione schifoso in quanto devo scorrere tutta la struttura per fare modifiche)

oppure avete una struttura di supporto che memorizza i prati ed i campi di appartenenza??

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by eskimo on 27-09-2005 18:54:

io ho tenuto nel fiore l'informazione prato, e poi ragionavo su delle liste di campi, che a loro volta avevano attaccate liste di prati. Gli oggetti delle liste sono molto semplici, hanno solo numeri per identificare il prato o il campo.
Praticamente ragiono su quelle strutture poi con algoritmi union-find, che scattano ad ogni fiore inserito se questo coincide con un altro fiore.

Posted by maynard80 on 27-09-2005 20:05:

Originally posted by maynard80
ragazzi non capisco un paio di cose:
code:
nel progetto dice:"valore intero v(x; y) (eventualmente negativo) che 
rappresenta la
qualitò del nettare del fiore stesso estraibile dall'ape (un valore 
negativo denota nettare di scarsa qualità e quindi tendenzialmente 
trascurabile)."
vuol dire che un valore negativo nei cammini non deve essere preso in considerazione e quindi contato come 0? (se fosse così l'algoritmo per il cammino pesato sarebbe uno di quelli proposti nel corso)

code:
Un campo C e un insieme C massimale di prati connessi, vale a dire: Per ogni coppia di prati A;B 2 C, A e connesso con B. Per ogni A 2 C e ogni prato P del piano tale che P 62 C, A non connesso con P.

vuol dire che se 2 prati sono adiacenti ma nessuno dei fiori è in comune non formano un campo ma sono di campi distinti (es prato1= {(0,0)(2,2)} prato2={3,0)(5,2)} sono adiacenti ma non formano un campo perchè non hanno nessun fiore in comune, e quindi non sono contigui)

questi 2 quesiti?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by Frigging on 27-09-2005 20:18:

Per quanto riguarda il primo quesito la risposta e' che il peso va memorizzato anche se negativo, da nessuna parte c'e' scritto di considerarlo 0.

Mentre se due prati sono adiacenti non appartengono allo stesso campo ma possono essere considerati cmq per un viaggio.

Rileggendo mi fa ridere il non determinismo della frase "tendenzialmente trascurabile".

Posted by maynard80 on 27-09-2005 20:42:

quel "tendenzialmente trascurabile" potrebbe aprire la strada ad altre interpretazioni è troppo ambiguo.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by Shimoda on 28-09-2005 05:51:

Originally posted by maynard80
quel "tendenzialmente trascurabile" potrebbe aprire la strada ad altre interpretazioni è troppo ambiguo.

Intende dire che probabilmente è trascurabile proprio perché negativo.. ma dipende dal percorso su cui si trova.. se tutti gli altri fiori del percorso hanno un'alta qualità allora il percorso è comunque preferibile..
se ignori i valori negativi ottieni risultati diversi, è chiaro anche dagli esempi.

__________________
"What the Caterpillar calls the end of the World,
the Master calls a Butterfly"
(Il manuale del messia, Illusioni, Richard Bach)

Posted by zac111 on 28-09-2005 07:36:

come lo usi il test? e che valori dovrebbe dare?

Posted by Frigging on 28-09-2005 08:04:

Io ho allegato un file tar ad uno dei miei post precedenti, che contiene i file dei prati un file di input e il mio file di output in modo tale che poi possiamo confrontarlo.

esempio:
cat input | ./nome_programma > tuo_output

Potrebbe volerci un po per l'elaborazione in quanto sono presenti file molto grossi in quanto c'e' ad esempio un rettangolo di -1000 -1000 1000 1000

Posted by mitnik on 28-09-2005 09:05:

si ma io non riesco ad aprire il tuo file di test!

Posted by mitnik on 28-09-2005 09:15:

o meglio apro il file .tar ma non contiene nulla. Potresti rimetterlo?

Posted by Frigging on 28-09-2005 09:18:

provo a cambiare formato.

Posted by mitnik on 28-09-2005 09:18:

grazie

Posted by mitnik on 28-09-2005 09:20:

ok adesso vedo i file! ora provo i test e poi ti faccio sapere

Posted by Ziotony.f4f on 28-09-2005 09:21:

Originally posted by Frigging
ahahah oramai sono bruciato!!!
Si io ho dei testa da fare te li allego.

Ho provato a testare questi dati, ma il file di testo "quattro" è grande 12 MB !!!!!!! non riesco nemmeno ad aprirlo, si impalla tutto, sei sicuro che sia solo testo?

Posted by Frigging on 28-09-2005 09:38:

Si sono sicuro, e funziona. Infatti il file da 12 mb fa test per vedere se il prog funzica con dimensioni cosi' grandi.

Dovrebbe essere il prato -1000 -1000 1000 1000

Posted by Frigging on 28-09-2005 09:40:

Cmq se l'algoritmo per il cammino o per la costruzione del grafo, ora non so come li hai fatti, e' lento ci vuole un po priam che termini.

Un conto e' bloccarsi e crashare un conto e' essere lento.

Al massimo commenta la riga di quel prato e provalo, poi dopo lo aggiungi e vai in pausa pranzo

Posted by Ziotony.f4f on 28-09-2005 09:42:

Originally posted by Frigging
Io ho allegato un file tar ad uno dei miei post precedenti, che contiene i file dei prati un file di input e il mio file di output in modo tale che poi possiamo confrontarlo.

esempio:
cat input | ./nome_programma > tuo_output

Potrebbe volerci un po per l'elaborazione in quanto sono presenti file molto grossi in quanto c'e' ad esempio un rettangolo di -1000 -1000 1000 1000

un po' quanto?!?! Per curiosità, con che processore?

Posted by Frigging on 28-09-2005 09:58:

Ma io ho un piccolo piccolo I-book... 1.2ghz

quanto dipende dall'algo... se esponenziale neanche tra decenni... se e' lineare tempo di lanciare l'eseguibile

Posted by Paolo74GRS on 28-09-2005 11:32:

:help:

..qualcuno saprebbe indicarmi dove posso trovare il codice per cancellare un intero albero RB? ..intendo fare il free di tutti i nodi dell'albero, non riesco a farlo con una semplice visita ricorsiva, è possibile?

:wall:

Posted by Ziotony.f4f on 28-09-2005 12:01:

Originally posted by Frigging
Ma io ho un piccolo piccolo I-book... 1.2ghz

quanto dipende dall'algo... se esponenziale neanche tra decenni... se e' lineare tempo di lanciare l'eseguibile

Io intendevo il tuo tempo di esecuzione !!!!

Posted by lucaderossi on 28-09-2005 12:07:

ma mi spiegate a cosa cavolo servono gli alberi RB in questo progetto?

Posted by Frigging on 28-09-2005 12:15:

Io a calcolare tutto con quel file di input impiego sul minuto.

Posted by Paolo74GRS on 28-09-2005 12:15:

Personalmente uso gli RB alberi come struttura che momorizza i punti la quale ha una buona efficienza in fase di ricerca..

Posted by zac111 on 28-09-2005 15:15:

compilo normalmente e quando eseguo inserisco per
esempio: "i 2 3 4 5 (tuo file)" e calcolo viaggio?

Posted by mitnik on 28-09-2005 15:34:

Originally posted by Frigging
Io a calcolare tutto con quel file di input impiego sul minuto.

Io ottengo i tuoi stessi output solo che a calcolare il viaggio potente impiego un sacco di tempo! dici che potrebbe essere un problema e che il prof per testare utilizzi un input cosi grande?

Posted by Frigging on 28-09-2005 16:01:

Mah, non penso che utilizzi file cosi' grandi. L'importante e' che funzioni e non crashi.
Bhe dai se abbiamo gli stessi output son proprio contento.

Quando ci mette il tuo per calcolare?

---
Risposta al post precedente:
puoi passare l'input cosi'

cat input | ./nome_tuo_prog > output

---

Se sei da windows, chi va di mano va sano e va lontano

cmq si devi fare i x0 y0 x1 y1 nomefile

All times are GMT. The time now is 09:39.

Pages (2): [1] 2 »
Show all 262 posts from this thread on one page