.dsy:it. - [PROGETTO] "Mappe 2"

Pages (17): « First ... « 3 4 5 6 [7] 8 9 10 11 » ... 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)
-- [PROGETTO] "Mappe 2" (http://www.dsy.it/forum/showthread.php?threadid=23982)

Posted by YoMo on 10-02-2006 19:52:

Secondo me dei cicli te ne fotti (se no il nostro progetto include anche quello di gennaio?!?!?), data una mappa e la relativa specifica devi ricavare due cose: origine e destinazione. Questo è ciò che ti basta per calcolarti la riduzione.
Per quanto riguarda i grafi, tra src e dst si potrebbe costruire un grafo e poi utilizzare un algoritmo per trovare i cammini minimi, ma a questo punto sorge un problema: nel progetto sono i PUNTI che hanno un valore, non gli ARCHI. Soluzione: ad es. valore[arco(u,v)] = valore[punto(v)]. Altro problema: ATTENZIONE, l'algoritmo di Dijkstra non è utilizzabile in quanto calcola il cammino minimo in un grafo nel caso in cui tutti i pesi degli archi siano positivi. Nel progetto (secondo la notazione di prima) un arco può avere valori negativi. Soluzione: sul Cormen due pagine dopo Dijkstra c'è l'algoritmo di Bellman-Ford che fa al caso nostro, ma cavolo, tra pseudocodice e C ci passa un mare!!!!
Cmq se volete qualche implementazione dei grafi guardatevi l'ultima lezione di Aguzzoli, proprio le ultime slide, altrimenti provate su http://www.algoteam.dsi.unimi.it/

Originally posted by maynard80
dunque allora sono contento che la nota 3 sia ormai chiara (il file contiene semplicemente nxm dati utilizzati per riempire il piano), i punti del piano esistono chiaramente solo nella nostra testa e si concreatizzano solo se fanno parte di una (o più) mappe, se poi cambiamo valore ad un punto agiamo manualmente sul dato che esplica il valore del punto che precedentemente era stato calcolato automaticamente tramite la formulina della nota 3.

ora ci troviamo quindi con delle mappe che hanno un nome, un punto di partenza e un percorso definito dalla specifica, le mappe sono selezionate tramite il nome quindi definire una struttura unica per contenere tutti i punti è una cacchiata, meglio una struttura come insieme di mappe, e ogni mappa una struttura contenente tutti i punti della specifica.. ora è meglio creare tutti i punti di ogni mappa oppure mantenere semplicemente il punto di partenza e lavorare con le specifiche? in teoria ogni mappa è un grafo che può contenere cicli e dove ogni punto può prendere 4 direzioni, ottimizzarlo vuol dire prima di tutto eliminare i cicli, quindi quale struttura può fare al caso nostro?

Posted by lfn on 10-02-2006 20:39:

niente lasciate stare ho risolto, non fate caso a quello che ho scritto T_T sono proprio fusa
lfn :cool:

__________________
an arrow from the sun

Posted by ornati on 11-02-2006 12:54:

Originally posted by YoMo
[B]Secondo me dei cicli te ne fotti (se no il nostro progetto include anche quello di gennaio?!?!?), data una mappa e la relativa specifica devi ricavare due cose: origine e destinazione. Questo è ciò che ti basta per calcolarti la riduzione.
Per quanto riguarda i grafi, tra src e dst si potrebbe costruire un grafo e poi utilizzare un algoritmo per trovare i cammini minimi, ma a questo punto sorge un problema: nel progetto sono i PUNTI che hanno un valore, non gli ARCHI. Soluzione: ad es. valore[arco(u,v)] = valore[punto(v)].

Non credo che ci sia bisogno di scomodare i grafi.

Per la riduzione, usando la programmazione dinamica, si può fare in tempo O(dx * dy). Dove dx = |src.x - dst.x| e dy = |src.y - dst.y|.

Non penso che si possa fare di meglio... nel caso generico. Poi magari si può velocizzare nel caso medio con qualche euristica, boh!

Posted by Nosferatu on 12-02-2006 09:31:

Sarà una stupidata ma io non riesco proprio a permettere la lettura sulla stessa linea di interi e di stringhe, come ad esempio nel comando m qualcuno può aiutarmi?

Posted by Diuzza on 12-02-2006 10:55:

Chissà come mai oggi ho riprovato a leggere il file s funzia.... mah

Posted by Diuzza on 12-02-2006 10:58:

prima fai un getchat e leggi il carattere che identificherebbe l'istruzione. Poi usi uno switch per riconoscere l'istruzione ed eseguire le relative operazioni. Dopodichè (in caso di c), gai un fscanf per leggere i valori o quel che sono.
E' questo che intendevi? o ho capito male?

Originally posted by Nosferatu
Sarà una stupidata ma io non riesco proprio a permettere la lettura sulla stessa linea di interi e di stringhe, come ad esempio nel comando m qualcuno può aiutarmi?

Posted by Nosferatu on 12-02-2006 11:01:

I miei problemi sono nel caso del comando m, quando devi permettere prima di inserire una stringa di lunghezza arbitraria, poi 2 interi e poi ancora una stringa

Posted by Polsy on 12-02-2006 11:55:

Originally posted by Nosferatu
I miei problemi sono nel caso del comando m, quando devi permettere prima di inserire una stringa di lunghezza arbitraria, poi 2 interi e poi ancora una stringa

scaricati qualche progetto vecchio dall'area filez, in tutti a un certo punto hai un comando misto tra interi e stringhe

Posted by maynard80 on 12-02-2006 13:52:

allora io ho 2 quesiti:
1)Per il discorso dei valori alla fine come calcoliamo il modulo? nel senso che 7mod2 fa 1 e su questo non ci sono problemi, ma -7mod2 dovrebbe fare -7 ma nel nostro caso a quanto pare non possiamo avere risultati della funzione modulo negativi (chiaro visto che il risultato stesso è l'indice per trovare il valore nel file), ecco voi coe operate??

2)stavo pensando che alla fine ogni mappa potrebbe essere una piccola lista di adiacenze, e ad essa applicare gli algoritmi per gli shortest path, no? unica cosa come si fa a modificare Dijkstra per il caso dei pesi negativi?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by ornati on 12-02-2006 16:28:

Originally posted by maynard80
allora io ho 2 quesiti:
1)Per il discorso dei valori alla fine come calcoliamo il modulo? nel senso che 7mod2 fa 1 e su questo non ci sono problemi, ma -7mod2 dovrebbe fare -7 ma nel nostro caso a quanto pare non possiamo avere risultati della funzione modulo negativi (chiaro visto che il risultato stesso è l'indice per trovare il valore nel file), ecco voi coe operate??

-7 mod 2 = 1
http://www.google.it/search?hl=it&q=-7+mod+2

E dalla pagina 2 di questo thread:
http://en.wikipedia.org/wiki/Modulo_operation

code:
int modulo(int a, int b)
{
	int x;

	if (a < 0) {
		x = -a + b - 1;
		a += x - x % b;
		return a;
	}
	return a % b;
}

Posted by Polsy on 12-02-2006 16:46:

Originally posted by maynard80

2)stavo pensando che alla fine ogni mappa potrebbe essere una piccola lista di adiacenze, e ad essa applicare gli algoritmi per gli shortest path, no? unica cosa come si fa a modificare Dijkstra per il caso dei pesi negativi?

io mi terrei come riferimento una matrice dei punti compresi tra l'origine e la destinazione della mappa coi valori per ogni punto
poi farei una seconda matrice in cui ogni cella (i,j) è una struct che tiene le coordinate del punto appena precedente a (i,j) nel cammino (quale scegliere te lo calcoli con dijkstra, ovviamente modificato x cercare il cammino di peso massimo) e il valore totale del cammino fino a quel punto
il cammino te lo trovi riguardando a ritroso i punti della seconda matrice, tempo di calcolo O(n*m) considerando una matrice nxm

non ti preoccupare dei pesi negativi, di solito dijkstra si incasina perchè cerca il cammino di peso minimo e coi valori negativi rischia di andare in loop, qui non hai di questi problemi perchè 1) cerchi il cammino di peso massimo e 2) visto che devi trovare il cammino di lunghezza minima imponi movimenti solo nelle 2 direzioni che ti fanno avvicinare al punto di destinazione => niente cicli

Posted by tyzer on 12-02-2006 16:47:

Non credo che ci sia bisogno di scomodare i grafi.

Per la riduzione, usando la programmazione dinamica, si può fare in tempo O(dx * dy). Dove dx = |src.x - dst.x| e dy = |src.y - dst.y|.

Non penso che si possa fare di meglio... nel caso generico. Poi magari si può velocizzare nel caso medio con qualche euristica, boh!

Spero proprio che non ci sia da scomodare i grafi, e concordo col tempo che hai detto, ma l mia domanda è come si può implementare questo algoritmo? Come fai con la programmazione dinamica? Col backtracking? io ho riguardato il problema del cavallo (quello sulla scacchiera che devi andare su tutte le caselle eccetera..) però li non c'era da tenere conto dei pesi dei punti come qui...se qualcuno ha idee...

Posted by Simeon on 12-02-2006 18:02:

Avanzo un problema che magari per voi sarà scemo ma mi sta mandando in confusione.

Voi QUANDO invocate la funzione che calcola il valore totale di una mappa?

Nell'esempio del prof lui inizia con

c 4 4 primo.txt
m mappa1 4 3 blablabla
s mappa1
...

E stampando mappa1 viene visualizzato:

...
mappa1 4 7 1 EEESSSEENWWWWWWWSSEENNNWSSSSSWW
...

Il valore di mappa1 con quella specifica e' "1", quindi in quelle 3 istruzioni la in alto è gia stato calcolato.

Allora ho pensato :"bene, invoco la funzione di calcolo del valore della mappa quando la inserisco con m mappa1 etc...".

Poi sono andato avanti a leggere l'esempio e ho trovato sto passaggio:

...
s alfa
v -3 3 100
s alfa
...

Che in output produce

...
alfa -6 3 11 NEEEN
alfa -6 3 94 EEENN
...

E questo mi manda in crisi. Quello che facciamo noi tra le due stampe è soltanto inserire un nuovo valore. Com'è possibile che la seconda stampa abbia gia a disposizione il valore nuovo della mappa alfa? E la specifica "NEEEN" cambia in "EEENN"... ma perchè?!?!

Boh se qualcuno riesce a capire qualcosa del mio problema e mi da una risposta lo ringrazio tantissimo, può darsi che mi sfugga qualcosa di molto molto importante.

:help:

p.s Polsy ma la rappresentazione con la matrice non è inefficiente? Almeno a quanto dice il progetto si...

Posted by YoMo on 12-02-2006 18:13:

Originally posted by Simeon

...

Poi sono andato avanti a leggere l'esempio e ho trovato sto passaggio:

...
s alfa
v -3 3 100
s alfa
...

Che in output produce

...
alfa -6 3 11 NEEEN
alfa -6 3 94 EEENN
...

E questo mi manda in crisi. Quello che facciamo noi tra le due stampe è soltanto inserire un nuovo valore. Com'è possibile che la seconda stampa abbia gia a disposizione il valore nuovo della mappa alfa? E la specifica "NEEEN" cambia in "EEENN"... ma perchè?!?!

...

Se l'esempio dice che

r alfa
s alfa
v -3 3 100
s alfa

sputa fuori

alfa -6 3 11 NEEEN
alfa -6 3 94 EEENN

può significare solo una cosa: se riduco una mappa VOGLIO che quella mappa sia SEMPRE ridotta, qualsiasi cosa succeda (es. modifico il valore di un punto).
Ciò mi fa venire i brividi....

Posted by Simeon on 12-02-2006 18:17:

Originally posted by YoMo
Se l'esempio dice che

r alfa
s alfa
v -3 3 100
s alfa

sputa fuori

alfa -6 3 11 NEEEN
alfa -6 3 94 EEENN

può significare solo una cosa: se riduco una mappa VOGLIO che quella mappa sia SEMPRE ridotta, qualsiasi cosa succeda (es. modifico il valore di un punto).
Ciò mi fa venire i brividi....

Oddio, sentiamo che dicono gli altri...

E che mi dici della prima parte invece? La funzione valore la calcoli quando fai "m mappa1 etc" oppure quando... la stampi?

p.s : ho mandato una mail al prof per chiarire un altro dubbio: "i valori che noi settiamo esplicitamente (tramite valore(x,y,n) valgono per un solo piano o per tutti quelli che creiamo?"

Se qualcuno avesse lo stesso dilemma domani dovrei ricevere la risposta, saluti

All times are GMT. The time now is 10:04.

Pages (17): « First ... « 3 4 5 6 [7] 8 9 10 11 » ... Last »
Show all 246 posts from this thread on one page