.dsy:it. - [Algoritmi] Progetto "RICHIAMI"

Pages (33): « First ... « 15 16 17 18 [19] 20 21 22 23 » ... Last »
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)
-- [Algoritmi] Progetto "RICHIAMI" (http://www.dsy.it/forum/showthread.php?threadid=17192)

Posted by LjL on 21-02-2005 01:28:

Nell'area file potete trovare un programmino che ho scritto per generare input validi per il progetto.

Spero vi sia utile.

E, sì, adesso il mio progetto è quasi completamente funzionante e domani invece di litigare con wingzero proverò e confronterò gli input che sono stati postati qui

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 21-02-2005 02:15:

Re: PROVIAMO L'OUTPUT

Originally posted by mattcobain
[snip]

io ho provato a dare in input questa sequenza:

[snip]

ho provato anche a fare le prove su carta e mi tornava tutto...se qualcuno può cmq provarlo e postare eventuali incongruenze, oppure postare altre sequenze non sarebbe una brutta cosa!

Il mio risultato è quasi uguale al tuo, con la differenza che il mio, come output del comando 'p', cita alcune volte l'automa "000" che il tuo output non cita mai.

Il diff tra il mio e il tuo output è

90d89
< 000: 1, 3
109d107
< 000: 1, 3
114d111
< 000: 1, 3
123d119
< 000: 1, 3

A me sembra che sia giusta la mia versione, dato che un automa "000" viene effettivamente creato e c'è almeno un comando 'p' che chiama gli automi con prefisso "0".

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by p2p on 21-02-2005 09:20:

Originally posted by Skilotto83
ho finito....!!!!!!
solo mi rimane un problema su un output.....
dopo il segnale...l'automa 01 a me nn si muove in 2,7...invece sekondo il prof si muove e giunge a destinazione...nessuno ha lo stesso problema???
+E poi...ma l'output vuole che si veda tutto in una volta come esempio..o dopo ogni singola istruzione che stampa???
Perchè a me printa dopo ogni comando di "posizione", "esiste percorso" e "tortuosità"...va bene no??

anch io ho lo stesso problema, lo 01 resta in 8 -4 e non si sposta... questo problema io l ho anche con 10 e 11 non so, potrebbe essere calcolato male la distanza,cioe' il modulo x-x0 + y-y0 forse...
a te che distanze vengono?io ho usato questa istruzione:
(abs(xsorg - xautoma)) + (abs(ysorg - yautoma));

è giusta?

Posted by elpampero on 21-02-2005 09:30:

A me viene come ha detto il prof..controllate bene anche l'input

Posted by elpampero on 21-02-2005 09:37:

S' 2p2 la funzione scritta così è corretta

Posted by mattcobain on 21-02-2005 12:16:

Re: Re: PROVIAMO L'OUTPUT

Originally posted by LjL
Il mio risultato è quasi uguale al tuo, con la differenza che il mio, come output del comando 'p', cita alcune volte l'automa "000" che il tuo output non cita mai.

Il diff tra il mio e il tuo output è

90d89
< 000: 1, 3
109d107
< 000: 1, 3
114d111
< 000: 1, 3
123d119
< 000: 1, 3

A me sembra che sia giusta la mia versione, dato che un automa "000" viene effettivamente creato e c'è almeno un comando 'p' che chiama gli automi con prefisso "0".

davvero sicuro che la tua versione sia giusta?
se guardi bene nell'input l'automa 000 che creo tento di metterlo in posizione (1,3) dove in realtò c'è il primo ostacolo che era stato inserito col comando " o 1 3 4 6" (in particolare, nel punto (1,3) c'è lo spigolo in basso a destra dell'ostacolo considerato)
se un automa va a posizionarsi su un punto appartenente ad un ostacolo, il testo del progetto dice che la funzione automa() non fa niente e quindi non inserisce l'automa....a questo punto penso che la versione giusta sia la mia....che dici?

Posted by Mosco on 21-02-2005 12:27:

Ciao a tutti qualcuno di voi sarebbe così gentile da spiegarmi per quale motivo l'automa 00 e l'automa 1 non possono raggingere il segnale dato che il prof Fiorentini non mi da una risposta? Io mi sono fatto una tabella con excel e ho inserito gli ostacoli e i relativi automi ma da questa mi risulta che solo l'automa 0 non può raggingere il segnale...e ciò mi compare anche dall'algoritmo che ho sviluppato...qualcuno può dirmi cosa non va del mio ragionamento?..o magari è l'output sbagliato?
grazie

Posted by LjL on 21-02-2005 12:52:

Re: Re: Re: PROVIAMO L'OUTPUT

Originally posted by mattcobain
davvero sicuro che la tua versione sia giusta?
se guardi bene nell'input l'automa 000 che creo tento di metterlo in posizione (1,3) dove in realtò c'è il primo ostacolo che era stato inserito col comando " o 1 3 4 6" (in particolare, nel punto (1,3) c'è lo spigolo in basso a destra dell'ostacolo considerato)
se un automa va a posizionarsi su un punto appartenente ad un ostacolo, il testo del progetto dice che la funzione automa() non fa niente e quindi non inserisce l'automa....a questo punto penso che la versione giusta sia la mia....che dici?

Si', hai ragione tu. In effetti sapevo che il mio programma non considera ancora questi casi, ma mi era proprio scappato di mente... (erano anche le 3 di notte

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 21-02-2005 13:05:

Originally posted by p2p
anch io ho lo stesso problema, lo 01 resta in 8 -4 e non si sposta... questo problema io l ho anche con 10 e 11 non so, potrebbe essere calcolato male la distanza,cioe' il modulo x-x0 + y-y0 forse...
a te che distanze vengono?io ho usato questa istruzione:
(abs(xsorg - xautoma)) + (abs(ysorg - yautoma));

è giusta?

E' giusta.
Piu' che questo, controllate se avete fatto i test nell'ordine giusto e e calcolate nella maniera corretta il minimo tra le distanze.

Se io ho capito bene, si determina quali automi devono muoversi in questo modo:
1) tra tutti gli automi, scegliere queli che corrispondono al prefisso indicato
2) tra questi, scegliere quelli per cui esiste un percorso libero da ostacoli
3) tra questi, scegliere quelli che si trovano a distanza minima dal richiamo
4) quelli che rimangono si muovono verso il richiamo

In particolare vi faccio notare che il punto 2 viene *prima* del punto 3. In realta' nel codice possono essere combinati per risparmiare qualche ciclo, ma se li combinate, state veramente attenti a farlo nel modo corretto.

L'altra questione e' il calcolo della distanza minima: se non usate metodi particolarmente arcani, suppongo che avrete una variabile "distanza minima" che aggiornate ogni volta che trovate un automa che la diminuisce... ecco, con che valore inizializzate questa variabile? E' facile che il problema stia li'.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by elpampero on 21-02-2005 13:08:

Per mosco. Non raggiunge il segnale perchè la distanza tra l'automa 1 e il segnale non è quella minima che hanno invece gli altri due automi!

Posted by Mosco on 21-02-2005 13:22:

è proprio quello che non riesco a capire..perchè a me l'automa 00 e l'automa 1 ragginge il segnale con un percorso di distanza minima..e rispettivamente l'automa 1 in 18 passi e l'automa 00 in 22...sbaglio a calcolare la distanza minima?
ho usato D = abs(x1-x2) + abs(y1-y2);

Posted by LjL on 21-02-2005 13:41:

Originally posted by Mosco
è proprio quello che non riesco a capire..perchè a me l'automa 00 e l'automa 1 ragginge il segnale con un percorso di distanza minima..e rispettivamente l'automa 1 in 18 passi e l'automa 00 in 22...sbaglio a calcolare la distanza minima?
ho usato D = abs(x1-x2) + abs(y1-y2);

Esempio: 00 può raggiungere il richiamo in 22 passi, ma 0 può raggiungerlo in 15, quindi 00 non si muove.
Se leggi anche la mia risposta a p2p dovresti capire qual è la questione.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by Mosco on 21-02-2005 13:47:

Grazie LjL tutto chiarito...mi era sfuggita sta cosa...il che significa riguardare tutta la funzione....consegnarlo entro giovedì è la mia impresa epica..

Posted by LjL on 21-02-2005 14:13:

Tirando le somme...

Adesso che il mio progetto è completo e (salvo alcuni casi particolari e segmentation fault vari che dovrò sistemare) sembra funzionare, posso indicarvi dei livelli di efficienza che sicuramente si possono raggiungere -- poi nessuno vieta che ne ne possano raggiungere anche di migliori, ovviamente.

- Detto 'n' il numero degli ostacoli e degli automi presenti, il piano può essere rappresentato con una struttura di dimensioni O(n²) che permette inserimento e ricerca in tempo O(n) per chiavi di tipo (x,y), senza privilegiare la x o la y.

- La ricerca degli automi che rispondono a un determinato prefisso di lunghezza k può, nel caso migliore, essere portata a termine in tempo @(k+m), dove m è il numero degli automi il cui come ha il prefisso cercato. In realtà sono abbastanza convinto che si possa raggiungere @(k+m) anche nel caso peggiore.

- Il calcolo della tortuosità per un automa può essere portato a termine in tempo O(n²), utilizzando una quantità di spazio O(n²), e volendo anche molto meno, direi O(n) ma non ne sono sicuro. Non sono in grado di dire quale sia la complessità in tempo del mio algoritmo nel caso medio (probabilmente sempre @(n²)), ma sono quasi sicuro che possa essere diminuita: infatti il mio algoritmo risolve in molti casi dei sottoproblemi che apparentemente si potrebbe evitare di considerare. Probabilmente il caso medio può arrivare fino a @(a*n), dove 'a' a occhio e croce sta tra una costante e un logaritmo.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 21-02-2005 14:15:

Re: Tirando le somme...

(deleted - scusate di nuovo, continuo a schiacciare Quote invece che Edit)

All times are GMT. The time now is 22:54.

Pages (33): « First ... « 15 16 17 18 [19] 20 21 22 23 » ... Last »
Show all 482 posts from this thread on one page