Originally posted by sasaciric
il trucco sta nel valutare il percorso se è valido non alla fine, ma durante la sua creazione. Se sto aggiungendo un punto che viola le condizioni, non costruisco tutto il cammino per vedere alla fine se è valido o meno ma mi blocco prima. così ne valuto molti meno e ottimizzo il tutto!
inoltre, anche valutando alla fine se è valido o meno, non sarebbe n! ma (n-1)! perchè quando tu scegli di partire da un elemento, non devi simulare di partire da tutti gli altri elementi perchè creeresti percorsi uguali. Es a 1,1 b 2,2 c 3,3

il percorso 1,1 2,2 3,3 1,1 è uguale a 2,2 3,3 1,1 2,2 quindi non serve testarlo 2 volte

Originally posted by sasaciric
l'unico modo per risolvere il problema del commesso viaggiatore è provare tutte le configurazioni possibili

Originally posted by tandrea85
il mio con 20 punti l'ho fatto partire 10min fa e sta ancora andando :|
mi ha allocato 2gb di memoria e il processo per ora ne occupa 20mb e sta salendo!!

speriamo che testi il programma con al max 10 - 12 punti se no addio

quelli che ci hanno messo 5min o meno che algoritmo avete usato?
provate con questo input

code:

c
i -9 2 a
i -8 2 b
i -7 2 c
i -6 2 d
i -5 2 e
i -4 2 f
i -3 2 g
i -2 2 h
i -1 2 i
i -9 -2 l
i -8 -2 m
i -7 -2 n
i -6 -2 o
i -5 -2 p
i -4 -2 q
i -3 -2 r
i -2 -2 s
i -1 -2 t
i -10 1 u
i 0 0 v
s
C

Originally posted by mapenzi81
il mio ci mette 0.015 ma a volta sbaglia....
com'è il vostro output?

24:
a,(-9,2) <- u,(-10,1) -> v,(0,0)
u,(-10,1) <- a,(-9,2) -> b,(-8,2)
a,(-9,2) <- b,(-8,2) -> c,(-7,2)
b,(-8,2) <- c,(-7,2) -> d,(-6,2)
c,(-7,2) <- d,(-6,2) -> e,(-5,2)
d,(-6,2) <- e,(-5,2) -> f,(-4,2)
e,(-5,2) <- f,(-4,2) -> g,(-3,2)
f,(-4,2) <- g,(-3,2) -> h,(-2,2)
g,(-3,2) <- h,(-2,2) -> i,(-1,2)
h,(-2,2) <- i,(-1,2) -> v,(0,0)
u,(-10,1) <- v,(0,0) -> i,(-1,2)

code:

searchtree *insert(searchtree *p, char *nome, int x, int y)

code:
char *nome="pincopallino"

code:
scanf("%d,%d,%s",&x,&y,&nome)

Originally posted by mapenzi81
qualcuno ha voglia di fare un confronto su un test su 500 - 600 punti?

Originally posted by mapenzi81
qualcuno ha voglia di fare un confronto su un test su 500 - 600 punti?

Originally posted by mapenzi81
qualcuno ha voglia di fare un confronto su un test su 500 - 600 punti?

Consegna entro domenica 23 aprile (compresa)
Poiché il giorno 24 aprile il dipartimento è chiuso, è possibile consegnare la documentazione cartacea il giorno 26 aprile.

code:
1. Inviare il codice del progetto per posta elettronica all'indirizzo fiorenti@dsi.unimi.it. La e-mail
deve avere come subject \Progetto di Cognome Nome", il le sorgente deve essere allegato alla
e-mail e deve chiamarsi cognome.c. Ad esempio, lo studente Mario Bianchi deve inviare una e-mail
avente cme subject Progetto di Bianchi Mario e allegare il le bianchi.c contenente il codice.
Nella e-mail e possibile segnalare le proprie preferenze per l'orale, come specicato sotto.
Nel caso il progetto sia suddiviso in piu le, va allegato un le cognome.zip (oppure cognome.tar),
contenente i le sorgente. In questo caso, i le devono rispettate le usuali convenzioni (ad esempio,
i le con susso .h devono contenere solo denizioni, i le con susso .c non vanno inclusi in altri
le).
2. Consegnare una copia stampata del codice e una sintetica relazione del progetto svolto. La relazione
deve illustrare e motivare le strutture dati e i principali algoritmi utilizzati, analizzandone anche
la complessita (il commento alle singole funzioni del programma va fatto all'interno del codice del
programma). Tale materiale va consegnata al dr. Fiorentini entro luned 24 aprile (compreso),
lasciandolo eventualmente nella sua casella postale presso il dipartimento in via Comelico (di anco
alla portineria). La relazione e il codice devono riportare il proprio nome, cognome e matricola.

Originally posted by xeon
Quindi si poteva risolvere in O(n^2)? Siete sicuri che dia sempre la soluzione migliore l'algoritmo bitonico euclideo?

Originally posted by darkAntAreS
sono con goldwurm...cmq 120 secondi al posto che 5 non cambia molto, almeno per quanto riguarda Aguzzoli conta più che altro "l'originalità" del progetto e se capisce che non hai messo lì il primo algoritmo che ti è venuto in mente ma ci hai pensato...
per Fiorentini/Torelli non so, ma nn penso cambi molto

code:

Non capisco perche' abbia scelto di usare un algoritmo approssimato!
Prima di fare una  tale scelta, non in linea con quanto richiesto,
avrebbe dovuto discuterne con me.

Il progetto non e' accettato e la invito a passare dutante  l'orario di
ricevimento per discuterne

saluti

Originally posted by maynard80
bene a me Fiorentini ha risposto:

code:

Non capisco perche' abbia scelto di usare un algoritmo approssimato!
Prima di fare una  tale scelta, non in linea con quanto richiesto,
avrebbe dovuto discuterne con me.

Il progetto non e' accettato e la invito a passare dutante  l'orario di
ricevimento per discuterne

saluti

ma funzionava correttamente! bene, domani è il mio compleanno e sono nella crisi più nera...

Originally posted by darkAntAreS
il problema non è quello del commesso viaggiatore, è "simile" a quello del commesso viaggiatore...quello del progetto si può calcolare in tempo O(n^2), mentre quello del commesso viaggiatore è NP-difficile..
ora non so che algoritmo hai utilizzato, ma utilizzando una euristica produci un risultato che non sempre è ottimale, quindi in generale non trovi la soluzione richiesta...

Originally posted by maynard80
PS: la mia euristica trovava la soluzione giusta ed in n^2. [/B]

Originally posted by darkAntAreS
non lo metto in dubbio, ma solo per il fatto che è un'euristica, in generale non produce una soluzione ottima...magari l'ha prodotta per ogni prova che hai fatto e la produrrà per tante altre prove, ma ce ne saranno sempre tante altre per cui non potrà farlo

per la soluzione, non ce n'è una sola...se vuoi io ne ho implementata una, il codice è nell'area filez e insieme trovi la relazione con una breve spiegazione...quella è però UNA possibile implementazione, a me il prof. ne ha fatta vedere un'altra con un codice un po' più pulito, sempre con tempo O(n^2) (che però non ho ben capito, mi sono limitato ad annuire con una faccia convinta :D )...al max se vuoi chiarimenti sul mio codice posso darteli, per il resto posso solo ipotizzare ;)

Originally posted by mapenzi81
Orale torelli...

Curiosita chiede anche gli algoritmi sui grafi e anche l unione di insieme disgiunti?

Originally posted by maynard80
ancora non capisco perchè mi ha annullato il progetto, ho usato un approccio simile all'euristica costruttiva per il commesso viaggiatore denominata "nearest neighbor"

http://it.wikipedia.org/wiki/Proble...sso_viaggiatore

e funziona tranquillamente.

il prof dice che non in linea con quanto richiesto, ma che vuol dire??

Originally posted by senai
hahahahah