CowBoy

User info:

Registered: May 2006
Posts: 294 (0.04 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Ti do ragione asgar... purtroppo le strutture dati dei grafi scritte dall'ALGOTeam non sono molto chiare. Mancano i commenti e chiarimenti del caso. Personalmente ci ho messo un po a decifrare il tutto. Praticamente ogni vertice viene rappresentato da un intero che parte da 0, con numerazione crescente. La lista/file di input deve contenere i dati in formato [id vertice partenza] [id arco(id vertice al quale collego il vertice di partenza)] [costo/distanza].
Il codice inoltre richiede che l'input venga letto da un file, ma si può modificare per far sì che legga una lista o altro...

Penso che sarebbe di grande aiuto se un giorno chi ha scritto il codice, aggiungesse anche dei commenti o delle descrizioni.

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

asgar

User info:

Registered: Jun 2009
Posts: 78 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 10:31:23 [...]
Status: Offline

Post actions:

hum dijkstra non credo serva in ogni caso, basta visitare in ampiezza per trovare le catene

CowBoy

User info:

Registered: May 2006
Posts: 294 (0.04 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Vero, la visita in ampiezza... ho fatto male a non frequentare quest'anno. Ho provato ad implementarla e funziona bene con i primi test.
Dijkstra basico con complessità O(n^2) mi funzionava bene ma quando ho cambiato implementazione usando gli 2-3heap per scendere a O(m+nlogn), il risultato finale era errato. Grazie asgar per questo suggerimento!

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

asgar

User info:

Registered: Jun 2009
Posts: 78 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 10:31:23 [...]
Status: Offline

Post actions:

mah per ora più che vedere il tempo di calcolo o lo spazio occupato cerco di farlo funzionare hehe.. in effetti il mio fra cicli e non cicli ci mette un sacco a calcolare le catene. però si può sempre risolvere aggiungendo qualche puntatore ai nodi del grafo quindi per ora non me ne preoccupo

Guccio

.fedelissimo.

User info:

Registered: May 2009
Posts: 59 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno: Terzo
Time Online: 9:28:59 [...]
Status: Offline

Post actions:

Scusate ma voi usando i grafi come fate a ricavarvi il cammino più breve?

CowBoy

User info:

Registered: May 2006
Posts: 294 (0.04 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Come diceva asgar, facendo una ricerca bfs... oppure, se vuoi farti del male, usando dijkstra.

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

asgar

User info:

Registered: Jun 2009
Posts: 78 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 10:31:23 [...]
Status: Offline

Post actions:

qualcuno ha già fatto le sottostringhe massime o la cacofonia?

Guccio

.fedelissimo.

User info:

Registered: May 2009
Posts: 59 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno: Terzo
Time Online: 9:28:59 [...]
Status: Offline

Post actions:

Originally posted by CowBoy
Come diceva asgar, facendo una ricerca bfs... oppure, se vuoi farti del male, usando dijkstra.

Bomb

User info:

Registered: Feb 2009
Posts: 14 (0.00 al dì)
Location: Venegono Superiore
Corso: Informatica
Anno: 3
Time Online: 4:35:59 [...]
Status: Offline

Post actions:

li memo rizzi tutti e poi tieni quello che fa meno passi?
mah...mi sembra un po' dispendioso...però dijkstra lo è ancora di più...:mad

CowBoy

User info:

Registered: May 2006
Posts: 294 (0.04 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Originally posted by asgar
qualcuno ha già fatto le sottostringhe massime o la cacofonia?

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

CowBoy

User info:

Registered: May 2006
Posts: 294 (0.04 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

... up

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

asgar

User info:

Registered: Jun 2009
Posts: 78 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 10:31:23 [...]
Status: Offline

Post actions:

Originally posted by CowBoy
Usa un algoritmo chiamato "La sotto sequenza comune massima"(LCS - Longest common subsequence/substring)... ci sono vari modi di implementarlo. Il peggiore è quello ricorsivo(tempo esponenziale). Quello dinamico scende a O(n*m)... se proprio vuoi strafare ci sono alcune tecniche per renderlo ancora più veloce.

Ciao!

mm non avevo visto il post.. ne ho fatto uno io che dipende dalla lunghezza delle due stringhe quindi credo dell'ordine di n*m, credo terrò quello, grazie cmq

CowBoy

User info:

Registered: May 2006
Posts: 294 (0.04 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Direi che ormai dovrei esserci... se qualcuno ha preparato file per testare il codice, posti pure qualche esempio per vedere se ci sono comportamenti anomali e sistemarli...

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

CowBoy

User info:

Registered: May 2006
Posts: 294 (0.04 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

ATTENZIONE!!! Leggete il seguente avviso:

7 gennaio 2011
La traccia del progetto "incastri", valida per l'appello di gennaio, presenta un errore all'interno dell'esempio conclusivo. L'istruzione "m gatto topo" deve essere ignorata in quando non esistono tessere con nome "gatto" quindi la riga di output "to" non va stampata.

http://lonati.dsi.unimi.it/algo/1011/?page=avvisi

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Last edited by CowBoy on 12-01-2011 at 14:26

xSharKMaNx

un gioco della follia

User info:

Registered: Sep 2007
Posts: 1477 (0.22 al dì)
Location:
Corso: F49
Anno: Laureato
Time Online: 10 Days, 17:15:29 [...]
Status: Offline

Post actions:

Ciao a tutti,
volevo chiedere a chi ha frequentato il lab di algo con la Prof. Lonati come si è trovato.

Vedendo le sue slide sul JLI devo dire che sono fatte davvero bene.

Per la teoria cosa state utilizzando come materiale?

Grazie a tutti

__________________
Perché, mentre il manganello può sostituire il dialogo, le parole non perderanno mai il loro potere; perché esse sono il mezzo per giungere al significato, e per coloro che vorranno ascoltare, all'affermazione della verità. E la verità è che c'è qualcosa di terribilmente marcio in questo paese. (V)

I popoli non dovrebbero aver paura dei propri governi, sono i governi che dovrebbero aver paura dei popoli. (T.J)