.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Progetto] Incastri - Gennaio 2011 (http://www.dsy.it/forum/showthread.php?threadid=41351)

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 ´´-±·ø·± ..

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

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 ´´-±·ø·± ..

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

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

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

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

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

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

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

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

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

Output errato

... up

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

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!

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 ´´-±·ø·± ..

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 ´´-±·ø·± ..

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)