 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[PROGETTO] "Mappe 2"
Clicca QUI per vedere il messaggio nel forum |
| Polsy |
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 |
| tyzer |
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... :?:?:?:? |
| Simeon |
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... |
| YoMo |
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.... |
| Simeon |
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....
:eek:
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 :) |
| Polsy |
Originally posted by Simeon
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:
mumble...
i casi sono 2, o il prof ha sbagliato e si è dimenticato una riduzione nel mezzo, o ha ragione yomo e le mappe vanno ridotte automaticamente...in tal caso non fai altro che richiamare riduci quando vuoi stampare una mappa (le riduci solo quando le vuoi stampare, se no sarebbe inefficientissimo) ma mi sembra strano...l'avrebbe scritto nelle specifiche...provate a mandargli una mail
edit: tra le altre cose, se riduci fosse implicita, a che pro richiamare r alfa prima di s alfa?
p.s Polsy ma la rappresentazione con la matrice non è inefficiente? Almeno a quanto dice il progetto si...
la rappresentazione del piano tramite una matrice è di sicuro inefficiente, dato che il piano è infinito ;)
le matrici che dico io riguardano solo la porzione di piano compresa tra l'inizio e la fine della mappa da ridurre |
| Simeon |
Originally posted by Polsy
mumble...
i casi sono 2, o il prof ha sbagliato e si è dimenticato una riduzione nel mezzo, o ha ragione yomo e le mappe vanno ridotte automaticamente...in tal caso non fai altro che richiamare riduci quando vuoi stampare una mappa (le riduci solo quando le vuoi stampare, se no sarebbe inefficientissimo) ma mi sembra strano...l'avrebbe scritto nelle specifiche...provate a mandargli una mail
edit: tra le altre cose, se riduci fosse implicita, a che pro richiamare r alfa prima di s alfa?
Non è per fare lo scarica barili, ma gli ho gia mandato 2 mail in 4 giorni e non vorrei che si alteri :look:, non può pensarci uno di voi?
la rappresentazione del piano tramite una matrice è di sicuro inefficiente, dato che il piano è infinito ;)
le matrici che dico io riguardano solo la porzione di piano compresa tra l'inizio e la fine della mappa da ridurre
No ho capito che non intendevi rappresentare TUTTO il piano, è che mi sa che avevo frainteso la nota del progetto (che parla della minima porzione rettangolare contenente tutti i percorsi specificati da mappe).
Bah intanto mi implemento l'alberello per memorizzare i punti non di default... poi si vedrà.
Non ho ancora la minima idea di come fare riduci(..) e sottopercorso(..) |
| tyzer |
Polsy (cioè Paola vero? :D), ho provato a seguire il tuo suggerimento, per fare la funzione riduci usando Dijkstra modificandolo perchè trovi il valore massimo , il fatto è che non funziona lo stesso...
anche tenendo conto dei soli spostamenti possibili e che cerco il cammino massimo quindi non va in loop su cicli negativi.
Il problema è che se i valori dei punti fossero tutti positivi allora l'algoritmo greedy insegue quelli piu grossi (cioè ogni volta che devo scegliere il prossimo punto scelgo quello piu grosso spostandomi nelle due uniche direzioni possibili per avvicinarmi al punto destinazione) e arrivo a determinare la soluzione ottimale...
Invece essendo presenti valori negativi, l'algoritmo può inseguire lo stesso i valori più grossi, ma magari poi trova dei valori negativi (nei punti successivi...) e la soluzione non è ottima perchè ci potrebbe essere il caso che scegliendo un percorso in cui ci sono punti negativi, poi magarai ce ne sono altri positivi che mi danno un percorso di valore maggiore che se nn avessi inseguito quelli di valore maggiore...
Non so se sono stato chiaro, in pratica credo che la struttura su cui applichiamo questo algoritmo non sia un matroide e quindi gli algoritmi greedy (compreso il caro Dijkstra...) non vanno... |
| Polsy |
Originally posted by tyzer
Polsy (cioè Paola vero? :D), ho provato a seguire il tuo suggerimento, per fare la funzione riduci usando Dijkstra modificandolo perchè trovi il valore massimo , il fatto è che non funziona lo stesso...
anche tenendo conto dei soli spostamenti possibili e che cerco il cammino massimo quindi non va in loop su cicli negativi.
Il problema è che se i valori dei punti fossero tutti positivi allora l'algoritmo greedy insegue quelli piu grossi (cioè ogni volta che devo scegliere il prossimo punto scelgo quello piu grosso spostandomi nelle due uniche direzioni possibili per avvicinarmi al punto destinazione) e arrivo a determinare la soluzione ottimale...
Invece essendo presenti valori negativi, l'algoritmo può inseguire lo stesso i valori più grossi, ma magari poi trova dei valori negativi (nei punti successivi...) e la soluzione non è ottima perchè ci potrebbe essere il caso che scegliendo un percorso in cui ci sono punti negativi, poi magarai ce ne sono altri positivi che mi danno un percorso di valore maggiore che se nn avessi inseguito quelli di valore maggiore...
Non so se sono stato chiaro, in pratica credo che la struttura su cui applichiamo questo algoritmo non sia un matroide e quindi gli algoritmi greedy (compreso il caro Dijkstra...) non vanno...
si, Paola :P ti conosco?
il fatto è che tu calcoli per ogni punto del rettangolo compreso tra la sorgente e la destinazione qual'è il cammino migliore dalla sorgente e in esso memorizzi il valore dell'intero cammino che ti porta fin lì
poniamo di dover andare da SW a NE
alla cella (i,j) ci puoi arrivare solo dalla cella (i-1,j) o da (i,j-1) e scegli quella col cammino parziale di valore massimo (mettiamo sia i-1,j)
nella cella (i,j) memorizzerò come valore $valore_cella(i-1,j) + $valore_punto(i,j)
in questo modo ogni cella ha il valore dell'intero cammino che lo precede, per cui è come se avesse memoria sia dei punti positivi che di quelli negativi
ad esempio se per arrivare alla cella (i,j-1) ho passato punti con valori inizialmente molto alti come 15, 20, 32 e poi valori negativi come -35, -30 avrò come valore della cella 2
mentre se per arrivare alla cella (i-1,j) avevo valori del tipo -1, 0, 0, 3, 4 avrò come valore della cella 6
di conseguenza l'algoritmo sceglie (i-1,j) come cella predecessore e pone il valore della cella i,j (il cui punto corrispondente facciamo che vale 3) a 6+3=9
praticamente l'idea è che per ogni punto intermedio si è calcolato il percorso ottimo per arrivarci, se esclude un percorso è solo perchè ne ha trovato un altro che lo porta nello stesso punto con un guadagno maggiore
come dire, tu non scegli dove ti conviene andare, ma da dove ti conviene arrivare |
| darkAntAreS |
| domanda stupida: e se trovo 2 percorsi ottimali con la riduzione? sulla descrizione del progetto dice che la riduzione di una mappa è la mappa stessa con un percorso ridotto, ma quell' "un" è articolo indeterminativo o effettivamente se ci sono più percorsi ottimali ne scelgo uno a caso??? |
| Polsy |
Originally posted by darkAntAreS
domanda stupida: e se trovo 2 percorsi ottimali con la riduzione? sulla descrizione del progetto dice che la riduzione di una mappa è la mappa stessa con un percorso ridotto, ma quell' "un" è articolo indeterminativo o effettivamente se ci sono più percorsi ottimali ne scelgo uno a caso???
se ne hai più ottimali ne scegli 1 a caso |
| Simeon |
Ok ragazzi, sul sito di laboratorio c'è l'errata corrige del problema di ieri, ci voleva una riduzione prima della seconda stampa :)
Per quanto riguarda i valori settati esplicitamente, il prof ha detto che alla creazione di un nuovo piano devono essere svuotati. |
| miles |
| mi sto accingendo a realizzare il progetto e pensavo alla rappresentazione del piano. se uso un albero binario di ricerca e (x,y) rappresenta la chiave l'albero non è sbilanciato? |
| tyzer |
il fatto è che tu calcoli per ogni punto del rettangolo compreso tra la sorgente e la destinazione qual'è il cammino migliore dalla sorgente e in esso memorizzi il valore dell'intero cammino che ti porta fin lì
Ho capito ciò che dici, ma secondo me ci sono dei problemi:
1) Come fai fare quello che ti ho quotato sopra? Per migliore intendi con peso massimo spero...
2) Anche ammettendo che si riesca a trovare per ogni punto (i,j) nel rettangolo il valore del cammino di peso massimo...potrebbe succedere che poi procedendo a ritroso dalla seconda matrice
il cammino te lo trovi riguardando a ritroso i punti della seconda matrice, tempo di calcolo O(n*m) considerando una matrice nxm
trovi che i punti (i-1,j) ed (i,j-1) hanno come valore del cammino migliore per raggiungerli lo stesso costo ed allora quale dei due scegli? Non puoi sceglierne uno a caso fra i 2 perchè non saprai mai se magari sceglievi quello che decidi scartare quali altri costi incontravi e che non incontrerai scegliendo l'altro punto...
P.S.
Di vista forse mi conosci, ero a fare metodi col Mereghet l'anno scorso...eravamo io e un mio amico tutti e due del primo anno... |
| Polsy |
Originally posted by tyzer
Ho capito ciò che dici, ma secondo me ci sono dei problemi:
1) Come fai fare quello che ti ho quotato sopra? Per migliore intendi con peso massimo spero...
si, peso massimo
alla prima iterazione tu non sai niente di nessuna cella, sai solo che il punto di origine vale $valore_punto_00 e che appartiene sicuramente al cammino, per cui nella matrice associ alla cella (0,0) le coordinate (0,0) (all'origine ci arrivi dall'origine :P) e $valore_cella_00 = $valore_punto_00
alla seconda iterazione analizzi la diagonale successiva, cioè (0,1) e (1,0)
(0,1) -> ci puoi arrivare solo dall'origine, quindi
$coordinate_punto_precedente_a_01 = (0,0)
$valore_cella_01 = $valore_cella_00 + $valore_punto_01
(1,0) -> ci puoi arrivare solo dall'origine, quindi
$coordinate_punto_precedente_a_10 = (0,0)
$valore_cella_10 = $valore_cella_00 + $valore_punto_10
terza iterazione, terza diagonale: (0,2) , (1,1) , (2,0)
(0,2) -> ci puoi arrivare solo da (0,1), quindi
$coordinate_punto_precedente_a_02 = (0,1)
$valore_cella_02 = $valore_cella_01 + $valore_punto_02
(1,1) -> ci puoi arrivare sia da (0,1) che da (1,0)
$coordinate_punto_precedente_a_11 = $punto_associato_alla_cella_con_valore_max
$valore_cella_11 = $valore_cella_con_valore_max + $valore_punto_11
(NOTA: se (0,1) e (1,0) hanno valori uguali è indifferente quale scegliere, vuol dire che entrambi i percorsi ti portano lo stesso guadagno)
(2,0) -> ci puoi arrivare solo da (1,0), quindi
$coordinate_punto_precedente_a_20 = (1,0)
$valore_cella_20 = $valore_cella_10 + $valore_punto_20
2) Anche ammettendo che si riesca a trovare per ogni punto (i,j) nel rettangolo il valore del cammino di peso massimo...potrebbe succedere che poi procedendo a ritroso dalla seconda matrice
trovi che i punti (i-1,j) ed (i,j-1) hanno come valore del cammino migliore per raggiungerli lo stesso costo ed allora quale dei due scegli? Non puoi sceglierne uno a caso fra i 2 perchè non saprai mai se magari sceglievi quello che decidi scartare quali altri costi incontravi e che non incontrerai scegliendo l'altro punto...
quando vai a ritroso per ritrovare il cammino non devi scegliere, hai già scelto prima, il punto precedente ce l'hai nel campo $coordinate_punto_precedente
P.S.
Di vista forse mi conosci, ero a fare metodi col Mereghet l'anno scorso...eravamo io e un mio amico tutti e due del primo anno...
la mia memoria è terribile...:oops: |
| tandrea85 |
ho appena iniziato sto progetto ed ho gia un dubbio..
per associare ad ogni punto val basta seguire la nota 3 e fin qua ci sono.. ma x e y dove li prendo? sono semplicemente fatti scorrere partendo dai parametri m e n?
nel caso di c 4 4 primo.txt abbiamo 16 punti e primo.txt contiene 16 valori.. quindi ogni punto avrà un valore.. io facendo 2 calcoli mi è venuto fuori cosi:
(1,1) -> v5
(1,2) -> v9
(1,3) -> v13
(1,4) -> v1
(2,1) -> v6
(2,2) -> v10
(2,3) -> v14
(2,4) -> v2
(3,1) -> v7
(3,2) -> v11
(3,3) -> v15
(3,4) -> v3
(4,1) -> v4
(4,2) -> v8
(4,3) -> v12
(4,4) -> v0
è corretto? |
| MaurizioL |
Originally posted by miles
mi sto accingendo a realizzare il progetto e pensavo alla rappresentazione del piano. se uso un albero binario di ricerca e (x,y) rappresenta la chiave l'albero non è sbilanciato?
Potenzialmente sì,
si suppone che le coordinate dei punti inseriti con il comando v x y siano casuali, in quel caso l'albero è relativamente bilanciato |
| maynard80 |
Originally posted by tandrea85
ho appena iniziato sto progetto ed ho gia un dubbio..
per associare ad ogni punto val basta seguire la nota 3 e fin qua ci sono.. ma x e y dove li prendo? sono semplicemente fatti scorrere partendo dai parametri m e n?
nel caso di c 4 4 primo.txt abbiamo 16 punti e primo.txt contiene 16 valori.. quindi ogni punto avrà un valore.. io facendo 2 calcoli mi è venuto fuori cosi:
(1,1) -> v5
(1,2) -> v9
(1,3) -> v13
(1,4) -> v1
(2,1) -> v6
(2,2) -> v10
(2,3) -> v14
(2,4) -> v2
(3,1) -> v7
(3,2) -> v11
(3,3) -> v15
(3,4) -> v3
(4,1) -> v4
(4,2) -> v8
(4,3) -> v12
(4,4) -> v0
è corretto?
veramente con C crei il piano ed il piano è immenso e non è altro che un insieme di quadrati costruiti come il tuo... ma ripetuti all'infinito. il fatto che ti dia m ed n non vuol dire che è un piano mxn, infatti poi potrebbe darti una mappa che inizia in 4,7 |
| Simeon |
Originally posted by tandrea85
ho appena iniziato sto progetto ed ho gia un dubbio..
per associare ad ogni punto val basta seguire la nota 3 e fin qua ci sono.. ma x e y dove li prendo? sono semplicemente fatti scorrere partendo dai parametri m e n?
nel caso di c 4 4 primo.txt abbiamo 16 punti e primo.txt contiene 16 valori.. quindi ogni punto avrà un valore.. io facendo 2 calcoli mi è venuto fuori cosi:
(1,1) -> v5
(1,2) -> v9
(1,3) -> v13
(1,4) -> v1
(2,1) -> v6
(2,2) -> v10
(2,3) -> v14
(2,4) -> v2
(3,1) -> v7
(3,2) -> v11
(3,3) -> v15
(3,4) -> v3
(4,1) -> v4
(4,2) -> v8
(4,3) -> v12
(4,4) -> v0
è corretto?
Se ti leggi una delle pagine iniziali di questo thread trovi la spiegazione del prof sulla nota 3 :) |
| tandrea85 |
Originally posted by Simeon
Se ti leggi una delle pagine iniziali di questo thread trovi la spiegazione del prof sulla nota 3 :)
ok grazie.. ho piu o meno capito.. quindi piano infinito, valori dei generci punti del piano ricavati o tramite v0, v1.. dal file, o tramite valore(s,y,n) o 0 altrimenti.
mettiamo ke io voglia scegliere l'albero binario di ricerca per il piano.. ma se è infinito cosa ci salvo dentro? quali punti? |
| maynard80 |
Originally posted by tandrea85
ok grazie.. ho piu o meno capito.. quindi piano infinito, valori dei generci punti del piano ricavati o tramite v0, v1.. dal file, o tramite valore(s,y,n) o 0 altrimenti.
mettiamo ke io voglia scegliere l'albero binario di ricerca per il piano.. ma se è infinito cosa ci salvo dentro? quali punti?
solo i punti che ti interessano
ma quello che io sinceramente non capisco è: se a noi essenzialmente interessano solo le mappe, e ogni mappa ha la sua identità precisa (2 mappe sovrapposte non ci interessano)
non basterebbero semplicemente i grafi per ogni mappa? oppure pensate di mettere come dato nel grafo della singola mappa un puntatore ad una struttura che contiene le info su tutti i punti?
certo sarebbe un problema quando si modifica un valore di un punto andare a modificarlo per ogni mappa è contenuto.
al massimo si potrebbe tenere traccia solo dei punti modificati tramite un albero binario e controllare ogni volta se il punto che ci interessa è contenuto nell'albero, in caso differente ha valore standard (il famoso valore della nota3)
voi che dite? |
| tandrea85 |
Originally posted by maynard80
solo i punti che ti interessano
quelli del percorso? se mi fai un esempietto te ne sarei grato..
piu che altro vorrei capire concettualmente la cosa..
quello che ho capito fin ora è (ed è ben poco):
- ho un piano infinito composto da punti
- ogni punto di questo piano infinito ha un valore calcolato secondo la nota3
- esistone delle mappe (che sono dei percorsi di punti all'interno del piano)
il piano quindi alla fin dei conti è una struttura (albero, hash o altro) vuota, che poi riempirò con i punti del percorso di una mappa.
boh.. ci sono concettualmente? |
| maynard80 |
Originally posted by tandrea85
quelli del percorso? se mi fai un esempietto te ne sarei grato..
piu che altro vorrei capire concettualmente la cosa..
quello che ho capito fin ora è (ed è ben poco):
- ho un piano infinito composto da punti
- ogni punto di questo piano infinito ha un valore calcolato secondo la nota3
- esistone delle mappe (che sono dei percorsi di punti all'interno del piano)
il piano quindi alla fin dei conti è una struttura (albero, hash o altro) vuota, che poi riempirò con i punti del percorso di una mappa.
boh.. ci sono concettualmente?
io la vedo + o - così |
| Simeon |
Originally posted by tandrea85
boh.. ci sono concettualmente?
Credo di si, piu o meno.. Cioe nemmeno io ho ancora le idee chiare al 100%.
Nel mio programma c'e' una struttura che ospita i punti inseriti con valore(x,y,n), un'altra struttura che memorizza le mappe...
Mi mancano riduci() e sottopercorso()... Ho solo una vaga idea di come farli ma ho paura che dovro' modificare qualcosa nella vecchia roba... buaaah. |
| jonnypee |
HELP ME!
Ho il primo progetto "Mappe" non riesco a modificarlo per formare il secondo "Mappe 2", in più sto preparando altri esami...c'è qualcuno che per favore me lo può fareee???
Ci sarà una riconpensa! |
| diocla2 |
Raga qualcuno del primo turno che ha finito il progetto me lo potrebbe dare gentilmente io sono del secondo turno con torelli vi pago cazzooooooo helpme
ciaooooo |
| maynard80 |
quindi la tabellona hash che veniva usata nel progetto mappe N°1 qui non ha senso? allora è come penso io servono solo i grafi delle mappe ed una struttura per i punti modificati.
certo bisogna dire che una struttura che contenga tutti i punti delle mappe non sarebbe male, in questo caso basterebbe un puntatore all'interno di ogni punto della mappa (nel caso si voglia modificare un punto appartenente a + mappe) |
| tandrea85 |
per l'input bisogna semplicemente leggere 1 riga alla volta?
per es. io scrivo:
c 1 1 asd.txt -> premo INVIO
rislutato istruzione
m 4 7 EWNNN -> premo INVIO
risultato istruzione
f -> premo INVIO
fine
oppure
c 1 1 asd.txt
m 4 7 EWNNN
f
-> premo INVIO
tutti i risultati 1 dopo l'altro come nel pdf |
| maynard80 |
si penso di si
allora io ho pensato di prender in esame il rettangolo di punti compresi tra i vertici P e Q per la riduzione della mappa (e quindi la lista di adiacenze di quei punti) mentre per il sottocammino solo i punti compresi nella mappa.
giusto?
per il primo caso bisogna adattare un alg. per shortest path (esempio Dijksta) per il secondo... qualcuno ha idee? |
| Simeon |
Certo che se dovessimo essere in troppi ad utilizzare l'approccio proposto da Polsy... :look:
Voi dite che basta che non ci copiamo il codice e tutto ok? |
| Simeon |
Originally posted by tandrea85
per l'input bisogna semplicemente leggere 1 riga alla volta?
per es. io scrivo:
c 1 1 asd.txt -> premo INVIO
rislutato istruzione
m 4 7 EWNNN -> premo INVIO
risultato istruzione
f -> premo INVIO
fine
oppure
c 1 1 asd.txt
m 4 7 EWNNN
f
-> premo INVIO
tutti i risultati 1 dopo l'altro come nel pdf
Si chiaro 1 riga alla volta. Ovvio che poi se rediRIGI l'input con <input.txt allora ti sputa fuori tutto in una botta sola come nel pdf |
| ornati |
Originally posted by marcomaria
esiste una funzione fmod nella libreria std math.h; non funziona allo stesso modo...?
No, esempio:
paolo@tux ~/tmp $ ./a.out
-7 2
-7 mod 2 = -1.000000 (invece che +1)
inoltre: perchè tirare in ballo i floating point quando puoi farne a meno? |
| maynard80 |
| ragazzi ma Dijkstra coi pesi negativi come fate? in alternativa avete materiale sugli algoritmi DSP? |
| poledrisk85 |
ciao a tutti!volevo sapere da voi se e dove piazzare l'output...è 1 pò difficile da spiegare:
nel progettino c'è una sfilza di righe di input e alla fine dice l'output prodotto deve essere bla bla bla...ma l'ouput lo devo salvare in un file e alla fine dell'esecuzione(cioè quando si premi in input il tasto f) si stampa a video o durante l'esecuzione?grazie a tutti! |
| darkAntAreS |
| per come ho capito io...ogni riga dell'input dev'essere seguita dal relativo output...altrimenti non avrebbe senso memorizzare i comandi per poi eseguirli uno dopo l'altro...o no??? |
| darkAntAreS |
domanda:
ho il mio piano, con una struttura che contiene tutti i punti modificati con il comando valore(x,y,v)...se poi cambio il piano col comando crea(m,n,nome), i punti cambiati precedentemente rimangono tali o devo cancellare la struttura che li conteneva perchè sono stati "rivalutati" dalla creazione del nuovo piano???? |
| YoMo |
Originally posted by maynard80
ragazzi ma Dijkstra coi pesi negativi come fate? in alternativa avete materiale sugli algoritmi DSP?
Svolta due pagine dopo sul cormen... |
| Simeon |
Porco cane credevo di avercela fatta e invece sto avendo dei problemoni. Tutto funziona quando l'origine e' minore della destinazione ed entrambe sono positive...
Se invece ho tipo origine 2 2 e destinazione -4 -5 e' il caos, uff... |
| YoMo |
Originally posted by darkAntAreS
domanda:
ho il mio piano, con una struttura che contiene tutti i punti modificati con il comando valore(x,y,v)...se poi cambio il piano col comando crea(m,n,nome), i punti cambiati precedentemente rimangono tali o devo cancellare la struttura che li conteneva perchè sono stati "rivalutati" dalla creazione del nuovo piano????
Beh direi che con "c m n nome" si azzera tutto, piano, mappe, punti, sistema operativo e bisogna pure riavviare il pc. |
| Simeon |
Originally posted by darkAntAreS
domanda:
ho il mio piano, con una struttura che contiene tutti i punti modificati con il comando valore(x,y,v)...se poi cambio il piano col comando crea(m,n,nome), i punti cambiati precedentemente rimangono tali o devo cancellare la struttura che li conteneva perchè sono stati "rivalutati" dalla creazione del nuovo piano????
Guardati qualche pagina addietr del thread... In un mio post c'è la risposta che cerchi. |
| darkAntAreS |
| visto, grazie ;) |
| maynard80 |
Originally posted by darkAntAreS
domanda:
ho il mio piano, con una struttura che contiene tutti i punti modificati con il comando valore(x,y,v)...se poi cambio il piano col comando crea(m,n,nome), i punti cambiati precedentemente rimangono tali o devo cancellare la struttura che li conteneva perchè sono stati "rivalutati" dalla creazione del nuovo piano????
beh se dice di creare un nuovo piano, è logico che si cancella tutto anche le modifiche |
| doddy |
Ho un piccolo problema cioe' e' proprio piccolissimo...nn ho controllato tutte le pagine dietro e quindi nn so se qualkun'altro ha avuto il mio stesso problemino cmq...il file di ornati nn mi stampa nulla cm output...so che nn me ne dovrebbe sbattere molto visto che i due proge sono differenti pero' volevo almeno vedere un po' mappe e zero nn mi da output...
ciao |
| ornati |
Originally posted by doddy
Ho un piccolo problema cioe' e' proprio piccolissimo...nn ho controllato tutte le pagine dietro e quindi nn so se qualkun'altro ha avuto il mio stesso problemino cmq...il file di ornati nn mi stampa nulla cm output...so che nn me ne dovrebbe sbattere molto visto che i due proge sono differenti pero' volevo almeno vedere un po' mappe e zero nn mi da output...
ciao
Ehh???
Il mio programma funziona benissimo! |
| Polsy |
Originally posted by doddy
Ho un piccolo problema cioe' e' proprio piccolissimo...nn ho controllato tutte le pagine dietro e quindi nn so se qualkun'altro ha avuto il mio stesso problemino cmq...il file di ornati nn mi stampa nulla cm output...so che nn me ne dovrebbe sbattere molto visto che i due proge sono differenti pero' volevo almeno vedere un po' mappe e zero nn mi da output...
ciao
hai provato a dargli input? :asd: |
| YoMo |
Originally posted by doddy
Ho un piccolo problema cioe' e' proprio piccolissimo...nn ho controllato tutte le pagine dietro e quindi nn so se qualkun'altro ha avuto il mio stesso problemino cmq...il file di ornati nn mi stampa nulla cm output...so che nn me ne dovrebbe sbattere molto visto che i due proge sono differenti pero' volevo almeno vedere un po' mappe e zero nn mi da output...
ciao
Magari nn usi un sistema operativo serio.... a parte gli scherzi, secondo me hai sbagliato gli input o li hai passati male. |
| Simeon |
Oooh che bello ho praticamente finito riduci()... madonna santa che fatica.
Qualcuno ha gia implementato sottopercorso() ? Idee ? |
| darkAntAreS |
io ho fatto sottopercorso!!!
un consiglio: NON fare l'errore di calcolarti ogni sottopercorso da ogni punto..ragiona su come è fatto un sottopercorso e da dove deve, per forza di cose, partire per essere tale...
nel caso peggiore a me viene (nlogn)/2, ma bisogna essere proprio sfigati...e nel caso medio viene circa n/2 |
| maynard80 |
Originally posted by darkAntAreS
io ho fatto sottopercorso!!!
un consiglio: NON fare l'errore di calcolarti ogni sottopercorso da ogni punto..ragiona su come è fatto un sottopercorso e da dove deve, per forza di cose, partire per essere tale...
nel caso peggiore a me viene (nlogn)/2, ma bisogna essere proprio sfigati...e nel caso medio viene circa n/2
ci dai maggiori dritte sul ragionamento che hai fatto? io mi scervello ma non arrivo, il sottopercorso è un frammento continuo del percorso della mappa, esso è incluso in P+1.......Q-1 , ma non riesco a capire se non facendo tutti i possibili sottocammini tra 2 punti come fare.... |
| Simeon |
Originally posted by darkAntAreS
io ho fatto sottopercorso!!!
un consiglio: NON fare l'errore di calcolarti ogni sottopercorso da ogni punto..ragiona su come è fatto un sottopercorso e da dove deve, per forza di cose, partire per essere tale...
nel caso peggiore a me viene (nlogn)/2, ma bisogna essere proprio sfigati...e nel caso medio viene circa n/2
Mmm forse ho capito, anche quei tempi li possono essere un'indizio :asd:.
Quindi tu hai finito tutto o devi fare riduci? |
| tandrea85 |
per quelli che hanno gia fatto la struttura base.. potete dirmi se il ragionamento che ho in testa regge e come la vedete voi?
avevo in mente 2 strutture
- un albero binario per i i punti a cui vengono variati i valori tramite la funzione "valore"
- un grafo che memorizza il percorso della mappa in base alla specifica e 1 algoritmo del cammino minimo.
non riesco ancora a capire cosa associare al piano e alla mappa..
mettiamo che faccio una funzione con il prototipo Piano new_piano(int m, int n, char *nome);
cosa deve ritornarmi alla struttura piano? tutti i valori dei punti del piano è da escludere..
l'unica cosa che mi viene in mente è fagli tornare i valori dei punti presi da file e memorizzati in un array e magari la struttura che contiene le varie mappe del piano..
riguardo appunto la struttura che raggruppa tutte la mappe posso benissimo usare o una lista o un array.
e infine la mappa sarà appunto un grafo.
se qualcuno mi illumina la retta via gliene sarei grato! grazie |
| maynard80 |
Originally posted by Simeon
Mmm forse ho capito, anche quei tempi li possono essere un'indizio :asd:.
Quindi tu hai finito tutto o devi fare riduci?
illumina anche chi non ha capito..please |
| Simeon |
Originally posted by maynard80
illumina anche chi non ha capito..please
Ma forse intendeva il fatto che per un percorso pi ... pj i dev'essere i>= j e quindi non devi guardarti tutti i punti... boh! Bluffavo, non lo so ancora perche sto rifinendo riduci() :asd: |
| maynard80 |
Originally posted by Simeon
Ma forse intendeva il fatto che per un percorso pi ... pj i dev'essere i>= j e quindi non devi guardarti tutti i punti... boh! Bluffavo, non lo so ancora perche sto rifinendo riduci() :asd:
e mica è vero, se il punto di indice i e quello di indice j sono 2 punti adiacenti??nonostante magari nel percorso della mappa non c'è un hop che li collega.. |
| Simeon |
Originally posted by maynard80
e mica è vero, se il punto di indice i e quello di indice j sono 2 punti adiacenti??nonostante magari nel percorso della mappa non c'è un hop che li collega..
Mi sa che hai ragione e che su sta funzione ci devo proprio ragionare, ma non oggi va... :)
@tandrea85
L'albero binario per i punti mi sembra ok
Per il resto... il piano non esiste.
Voglio dire, non crei una struttura per rappresentare il piano, ma fai in modo che ogni volta che hai bisogno di trovare il valore di un punto di questo piano o gli associ il valore di default (che trovi tramite la nota3) oppure gli associ un valore deciso da te (ma prima devi settarglielo tramite "valore(x,y,n)".
Per la struttura che memorizza le mappe puoi usare una lista o un albero o quel che ti pare a te...
Infine riguardo al "la mappa sarà un grafo" non ti posso dire se sia giusto o sbagliato, cioè io non ho fatto così ad esempio ma potrei aver adottato un approccio differente. |
| darkAntAreS |
bhe, senza sbilanciarmi troppo ;)
considerate che, se cercate i percorsi a partire da un punto P(i) e P(i-1) è >=0, bhe, in un ciclo precedente avreste potuto controllare i percorsi da P(i-1) che sono sicuramente maggiori di quelli da P(i)...
riduci l'ho fatto, ma ci mette troppo, quindi sto ragionando per velocizzarlo un po'...e per farlo sto pensando ad un albero come appoggio (a sinistra se vai in una direzione, a destra se vai verso l'altra...)
per la struttura di memorizzazione delle mappe l'albero è ottimo, visto che, se lo si ordina sui nomi delle mappe, la ricerca è molto veloce...l'unico problema si incontra con l'eliminazione di un nodo interno, ma basta leggere gli esempi del libro che lo spiegano benissimo |
| Simeon |
Originally posted by darkAntAreS
riduci l'ho fatto, ma ci mette troppo, quindi sto ragionando per velocizzarlo un po'...
Ci mette troppo in che termini? A me l'esecuzione dell'input del prof e' instantanea ad occhio, ma magari ci mette che so 100ms e sono troppi (in fondo l'input del prof è piccolino).
Cosa intendi per troppo scusa?
p.s Grazie per la dritta sui percorsi :) |
| darkAntAreS |
bhe, io non mi sto confrontando coi tempi del mio processore...è ovvio che se piazzo un algoritmo come il mio attuale riduci, a meno che non metto i 2 punti a distanze immani, la differenza di tempo non è apprezzabile...più che altro sto facendo i calcoli della complessità dei tempi degli algoritmi...
quindi il discorso di velocizzare le cose si basa sull'algoritmo, non sull'implementazione...
forse ho trovato il metodo per ridurlo a m*n (con m e n intese come le differenze tra le coordinate dei punti) |
| Simeon |
Originally posted by darkAntAreS
bhe, io non mi sto confrontando coi tempi del mio processore...è ovvio che se piazzo un algoritmo come il mio attuale riduci, a meno che non metto i 2 punti a distanze immani, la differenza di tempo non è apprezzabile...più che altro sto facendo i calcoli della complessità dei tempi degli algoritmi...
quindi il discorso di velocizzare le cose si basa sull'algoritmo, non sull'implementazione...
forse ho trovato il metodo per ridurlo a m*n (con m e n intese come le differenze tra le coordinate dei punti)
Ah capito. Io credo di metterci proprio il tempo che dici tu (m*n) perchè ho usato le matrici... |
| tandrea85 |
domanda stupidissima e veloce:
se uso un albero binario di ricerca e come chiavi uso le coordinate x,y di un punto come faccio a discriminare le chaivi per farle andare o nel sottoalbero sinistro o quello destro? |
| YoMo |
Originally posted by tandrea85
domanda stupidissima e veloce:
se uso un albero binario di ricerca e come chiavi uso le coordinate x,y di un punto come faccio a discriminare le chaivi per farle andare o nel sottoalbero sinistro o quello destro?
Io ho ordinato in base alla coordinata x ed, in caso di uguaglianza, in base alla y. Non sembrano esserci problemi, neanche cn le rotazioni (ho usato un rbtree). |
| tandrea85 |
Originally posted by YoMo
Io ho ordinato in base alla coordinata x ed, in caso di uguaglianza, in base alla y. Non sembrano esserci problemi, neanche cn le rotazioni (ho usato un rbtree).
grazie.. sono un beota non ci avevo pensato |
| Simeon |
Ma se per trovare il sottopercorso migliore io scandisco l'array che contiene il percorso UNA SOLA VOLTA... è tempo lineare vero ?
Se si, e se il mio algoritmo funziona, ho trovato una soluzione in tempo lineare.
Dubito molto fortemente della seconda ipotesi però... |
| darkAntAreS |
| se riesci si, è tempo lineare...ma non riesco a immaginarlo...bhe, se funziona sei un grande ;) |
| Simeon |
Originally posted by darkAntAreS
se riesci si, è tempo lineare...ma non riesco a immaginarlo...bhe, se funziona sei un grande ;)
Guarda è una roba abbastanza contorta, sono sicuro di aver tralasciato qualche particolare e probabilmente non funzionerà nel 50% dei casi... ma coi test a "mano" sull'esempio del prof funziona, e anche su molti altri... Il problema è vedere ora se riesco a realizzare la roba scritta su carta.
EDIT : sono un povero illuso, ho appena fatto fallire un test :|
daaragh non so come ragionarciii, lo faccio nel metodo scrauso che ci mette n^2 :asd:
meglio dormire va :arg: |
| Simeon |
Non :wall: riesco :wall: a :wall: venirne :wall: a :wall: capo :wall:
Quasi quasi lo implemento nella maniera iGNorante...
Trovo metodi che funzionano a meta'... ma aaargh.
Darkantares tu hai detto che se analizzo da P(i) e P(i-1) è >= 0 allora in teoria potrei aver gia trovato i percorsi di p(i-1) che sono maggiori di p(i)... sto riflettendo a lungo su questa ma non riesco a capire come deve funzionare sto algoritmo... maronn
EDIT : sul libro non c'e niente che possa essere d'aiuto ? |
| darkAntAreS |
| sul libro non c'è niente, ma pensa che, in ogni caso, devi scorrere il "vettore" (o struttura analoga) del percorso almeno una volta...e che puoi scegliere i punti utili da cui far partire il sottopercorso ottimale...e dove farlo finire... |
| Simeon |
Originally posted by darkAntAreS
sul libro non c'è niente, ma pensa che, in ogni caso, devi scorrere il "vettore" (o struttura analoga) del percorso almeno una volta...e che puoi scegliere i punti utili da cui far partire il sottopercorso ottimale...e dove farlo finire...
Grazie, ma credo di avercela fatta :pazzo: |
| Simeon |
Ok io avrei finito, però mi sbaglia una riga di output:
code:
19: -3,3; -3,4; -3,5; -3,6; -2,6; -2,5
19: -3,3; -3,4; -3,5; -3,6; -2,6; -2,5
19: -3,3; -3,4; -3,5; -3,6; -2,6; -2,5
Il terzo 19:etcetc dovrebbe essere diverso... sembra che non veda il valore cambiato... però tutto il resto e' identico all'esempio del prof
Non è che ha sbagliato lui? Sono solo io ad avere sto problema?
EDIT:
Mi sbaglia anche questa (mi sa che e' un problema mio a sto punto)
code:
9: 5,3; 6,3; 6,4; 6,5
Che dovrebbe essere
9: 5,3; 6,3; 6,4; 6,5; 5,5; 4,5; 4,4; 4,3; 5,3; 6,3 |
| Simeon |
E' FINITAAAAAA! :mad:
Ce l'ho fatta. |
| poledrisk85 |
| ancora help!qualcuno mi potrebbe aiutare sulla funzione riduci e sul sottoxcorso???ho letto i precedenti post ma...buio totale!!!heeeeeeeeeelpppppp! |
| lfn |
ragazzi il compilatore mi dà il seguente errore quando tento di creare l'albero rb..
C:/cs1300/lib/libmingw32.a(main.o)(.text+0x97):main.c: undefined reference to `WinMain@16'
help me!!
lfn :cool: |
| lfn |
edit.. ho cercato in giro..cioè questo errore è dovuto solamente al fatto ke non ho dichiarato un main? :lol
altro sclero da esame
lfn :cool: |
| YoMo |
Originally posted by lfn
ragazzi il compilatore mi dà il seguente errore quando tento di creare l'albero rb..
C:/cs1300/lib/libmingw32.a(main.o)(.text+0x97):main.c: undefined reference to `WinMain@16'
help me!!
lfn :cool:
Boh!! L'unico consiglio che posso darti è disinstalla il compilatore (cioè cancella la cartella), riavvia la macchina, scaricati di nuovo il compilatore e reinstallalo. |
| YoMo |
Vorrei sottoporre alla vostra attenzione la mia personale esperienza: ho finito il progetto, da qlche gg e tutto funziona a dovere ma.... oggi ho dovuto rivalutare la funzione riduci() perchè con specifiche grandi, o meglio, con punto sorgente e destinazione abbastanza distanti, non funziona più!!! Beh magari funziona anche ma il tempo che ci mette...
Infatti la mia funzione essendo ricorsiva, nel ricercare il percorso ottimo verso un punto abbastanza distante apre talmente tanti record d'attivazione che la rende praticamente inutilizzabile.
Per esempio con una specifica del tipo NENENENENENENENENENENENENENENENENENE dopo 15sec sta ancora lavorando....
Quindi state attenti nel caso la vostra riduci() dia ricorsiva!!
Ora mi tocca riprogettare la funzione...meno male che devo modificare solo una funzione...
Qlcuno ha avuto la stessa esperienza? |
| Simeon |
Originally posted by YoMo
Qlcuno ha avuto la stessa esperienza?
No, ma credo proprio perchè la mia non è ricorsiva...
Ah ragazzi attenzione che il prof ha pubblicato una seconda ERRATA CORRIGE sul sito. E' abbastanza importante perchè implica una piccola modifica a sottopercorso() (va in pratica "refreshato" il valore della mappa all'interno) |
| ornati |
Originally posted by YoMo
Boh!! L'unico consiglio che posso darti è disinstalla il compilatore (cioè cancella la cartella), riavvia la macchina, scaricati di nuovo il compilatore e reinstallalo.
Vero. Il proverbio di Windows è: "riavvia e sarai più fortunato".
Un po' come il gratta e "vinci".
:) |
| Simeon |
Originally posted by ornati
Vero. Il proverbio di Windows è: "riavvia e sarai più fortunato".
Un po' come il gratta e "vinci".
:)
Off-Topic:
E finiamola dai.
Non ho mai avuto (e dico MAI) un crash di sistema da quando ho messo windows XP.
Magari dalla 98 in giù puoi avere ragione ma la tiritera "Linux è meglio  " alla fine stufa...
|
| maynard80 |
Originally posted by Simeon
No, ma credo proprio perchè la mia non è ricorsiva...
Ah ragazzi attenzione che il prof ha pubblicato una seconda ERRATA CORRIGE sul sito. E' abbastanza importante perchè implica una piccola modifica a sottopercorso() (va in pratica "refreshato" il valore della mappa all'interno)
non capisco in che senso va modificato percorso? tu parli di
code:
2) Le righe di input
v -3 3 100
s alfa
vanno sostituite con
v -3 3 100
r alfa
s alfa
nell'input? questo vuol dire che prima di eseguire sottopercorso devi ridurre la mappa, ma che c'entra con modificare il progetto??
PS: una domanda a chi mantiene in una struttura solo i punti che vengono modificati:
- ma quindi controllate se un punto è stato modificato e in caso negativo utilizzate il valore di default?? ma quindi il valore non modificato di un punto non lo immagazzinate e lo calcolate al voo ogni volta??? io avevo pensato una cosa simile (l'informazione sul cammino tanto è contenuta in specifica)
che mi dite? |
| Simeon |
Originally posted by maynard80
non capisco in che senso va modificato percorso? tu parli di
code:
2) Le righe di input
v -3 3 100
s alfa
vanno sostituite con
v -3 3 100
r alfa
s alfa
nell'input? questo vuol dire che prima di eseguire sottopercorso devi ridurre la mappa, ma che c'entra con modificare il progetto??
Parlavo di questo:
code:
Nell'esempio a pag. 6:
1) La riga di output
beta 4 3 16 EESESE
(penultima riga) va sostituita con
beta 4 3 15 EESESE
[/quote]
PS: una domanda a chi mantiene in una struttura solo i punti che vengono modificati:
- ma quindi controllate se un punto è stato modificato e in caso negativo utilizzate il valore di default?? ma quindi il valore non modificato di un punto non lo immagazzinate e lo calcolate al voo ogni volta??? io avevo pensato una cosa simile (l'informazione sul cammino tanto è contenuta in specifica)
che mi dite?
Io ho fatto come hai detto tu. |
| maynard80 |
Originally posted by Simeon
Parlavo di questo:
code:
Nell'esempio a pag. 6:
1) La riga di output
beta 4 3 16 EESESE
(penultima riga) va sostituita con
beta 4 3 15 EESESE
Io ho fatto come hai detto tu. [/QUOTE]
quindi mantieni informazioni del percorso nella specifica (che va aggiornata in caso si esegue riduci)
ma per riduci hai sicuramente bisogno di un grafo di nodi, lo crei al voo anche quello? |
| YoMo |
Originally posted by maynard80
Io ho fatto come hai detto tu.
quindi mantieni informazioni del percorso nella specifica (che va aggiornata in caso si esegue riduci)
ma per riduci hai sicuramente bisogno di un grafo di nodi, lo crei al voo anche quello? [/B][/QUOTE]
Io non penso ci sia bisogno di scomodare i grafi, la cosa si può risolvere con una manciata di cicli. Almeno questa è l'idea che ho, doma devo riscrivere la funzione riduci().... |
| Simeon |
Originally posted by maynard80
quindi mantieni informazioni del percorso nella specifica (che va aggiornata in caso si esegue riduci)
ma per riduci hai sicuramente bisogno di un grafo di nodi, lo crei al voo anche quello? [/B]
Ho detto che ho fatto come hai detto tu nel senso che ho i valori non di default in una struttura. Ogni volta che calcolo un valore e non lo trovo lo vado a pescare tra i valori di default... Il percorso è costituito dalla specifica, non capisco la prima frase boh sarò fuso :asd:.
Non uso grafi di nodi cmq. |
| maynard80 |
Originally posted by Simeon
Ho detto che ho fatto come hai detto tu nel senso che ho i valori non di default in una struttura. Ogni volta che calcolo un valore e non lo trovo lo vado a pescare tra i valori di default... Il percorso è costituito dalla specifica, non capisco la prima frase boh sarò fuso :asd:.
Non uso grafi di nodi cmq.
nel senso che mi sembra inutile memorizzare i nodi in questo progetto, visto che calcolare il loro valore "al volo" è sicuramente + veloce che ricercarli, e visto che abbiamo una stringa che ne indica il percorso ed una funzione che calcola i valori.. le uniche cose che vanno memorizzate sono i valori dei punti modificati a mano.
unica cosa per riduci() non avendo una struttura tipo un grafo non so come applicare un algo greedy o altro...pensavo ad un semplice BFS, ma non so forse sbaglio.
PS: la consegna è entro domenica, ma la parte cartacea posso consegnarla lunedì vero? |
| ornati |
Originally posted by Simeon
Off-Topic:
E finiamola dai.
Non ho mai avuto (e dico MAI) un crash di sistema da quando ho messo windows XP.
Magari dalla 98 in giù puoi avere ragione ma la tiritera "Linux è meglio " alla fine stufa...
Non ho parlato di crash, e neanche di Linux... ho solo fatto una battuta (che poi rispecchia la realtà: in Win spesso è richiesto il riavvio... non si sa bene perchè).
In un sistema Linux l'unica cosa che richiede un riavvio è l'aggiornamento del kernel...
Inoltre il motivo principale per cui uso sistemi basati su Linux non è la stabilità (ok, c'è anche quella) ma è la natura aperta del sistema, che ti permette di capire come funzionano le cose. E anche perchè è divertente.
Ti consiglio una lettura:
Torvalds Linus - Diamond David
Rivoluzionario per caso
Come ho creato Linux (solo per divertirmi)
http://www.garzantilibri.it/default...libro&CPID=1612
Il titolo in inglese è ancora meglio: "Just for fun".
Se vuoi te lo presto io (quando mi ritorna dall'ultimo prestito). |
| tandrea85 |
sono anche io all'epilogo del progetto.. mi mancano la funzione riduci() e sottopercorso()
per la riduci se non c'era il vingolo della lunghezza minima e bastava vedere quale percorso da x,y a xi,yi aveva valore maggiore era una cagata.. cmq per la funzione riduci serve solo il punto di origine della mappa e il punto di arrivo (calcolato tramite la specifica??)? |
| Simeon |
Originally posted by ornati
Non ho parlato di crash, e neanche di Linux... ho solo ..
Non farmi continuare, almeno in sto thread. E dai.
Vabbe mi spiego meglio: il fatto è che sembrava la solita critica mossa dagli utenti linux a windows quando poi windows stesso non è pessimo come molti lo dipingono.
Niente, ok, finiamola comunque che non gliene frega niente a nessuno. |
| Simeon |
Originally posted by tandrea85
cmq per la funzione riduci serve solo il punto di origine della mappa e il punto di arrivo (calcolato tramite la specifica??)?
Esatto. |
| poledrisk85 |
io sto x abbandonare...mi mancano riduci e sottopercorso...non so proprio come procedere (volevo farli con gli array ma in una nota in corsivo si sconsiglia vivamente..:( )
se non riesco farò il prox...sperando che sia + semplice!!! |
| puntozip |
Originally posted by poledrisk85
io sto x abbandonare...mi mancano riduci e sottopercorso...non so proprio come procedere (volevo farli con gli array ma in una nota in corsivo si sconsiglia vivamente..:( )
se non riesco farò il prox...sperando che sia + semplice!!!
Di quale nota in corsivo parli?
Grazie |
| Simeon |
Originally posted by poledrisk85
io sto x abbandonare...mi mancano riduci e sottopercorso...non so proprio come procedere (volevo farli con gli array ma in una nota in corsivo si sconsiglia vivamente..:( )
se non riesco farò il prox...sperando che sia + semplice!!!
Quella nota parla di matrici, e comunque le sconsiglia per rappresentare il piano... |
| Diuzza |
Chi mi darebbe un suggerimento su sottopercorso?
Ho implementato tutto, mi manca solo quello, sono fulminata |
| maynard80 |
ragazzi, ma a voi riduci quanto ci mette???? se do una specifica del tipo
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEENNNNNNNNN
NNNNNNNNNNNNNNNNNNNNNNNNNNNNN
il mio programma va davvero in crisi!! mi sa che ho sbagliato qualcosa.. |
| MaurizioL |
| C'è evidentemente qualcosa che non và, nei test che ti daranno per testare il programma potrebbero esserci specifiche anche di 30000 caratteri. |
| maynard80 |
Originally posted by MaurizioL
C'è evidentemente qualcosa che non và, nei test che ti daranno per testare il programma potrebbero esserci specifiche anche di 30000 caratteri.
a quanto pare mi finisce la memoria.....
ad esempio su un cammino come
10,10 11,10 12,10 13,10 14,10 15,10 16,10 16,11 16,12 16,13 16,14 16,15 16,16
- il percorso ha 13 nodi
trovati 924 cammini di lunghezza minima tra cui 2 di peso massimo.
chiaro che 924 cammini sono un devasto per la memoria.... sopratutto per il fatto che alloco un nodo e non ne ho semplicemente un puntatore... |
| Simeon |
Originally posted by MaurizioL
C'è evidentemente qualcosa che non và, nei test che ti daranno per testare il programma potrebbero esserci specifiche anche di 30000 caratteri.
:schoked: |
| Simeon |
Originally posted by maynard80
a quanto pare mi finisce la memoria.....
ad esempio su un cammino come
10,10 11,10 12,10 13,10 14,10 15,10 16,10 16,11 16,12 16,13 16,14 16,15 16,16
- il percorso ha 13 nodi
trovati 924 cammini di lunghezza minima tra cui 2 di peso massimo.
chiaro che 924 cammini sono un devasto per la memoria.... sopratutto per il fatto che alloco un nodo e non ne ho semplicemente un puntatore...
924 cammini ? Hmm...
Boh a me sul tuo esempio va bello liscio |
|
|
|
|
