.dsy:it. - [progetto] Microcolture

Pages (2): [1] 2 »
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] Microcolture (http://www.dsy.it/forum/showthread.php?threadid=25063)

Posted by mapenzi81 on 04-04-2006 11:24:

[progetto] Microcolture

Dai..facciamo le cose per bene e facciamo un thread dedicato....

in bocca al lupo a tutti

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by lfn on 04-04-2006 11:31:

crepi! cmq credo bisognerà avvisare il prof che lunedì 24 l'ateneo rimarrà chiuso.. ( per la consegna dello stampato )

lfn :cool:

__________________
an arrow from the sun

Posted by maynard80 on 04-04-2006 11:34:

ma voi ci avete capito qualcosa? mi sembra abbastanza incasinato (come al solito)

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by mapenzi81 on 04-04-2006 11:40:

beh dai...ne ho letti di piu incasinati

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by maynard80 on 04-04-2006 13:01:

a pagina 2 ci sono 2 esempi di legami possibili nella colonia, ma quello di destra in teoria non dovrebbe essere regolare secondo i punti 1,2,3:

code:
Supponiamo che la colonia contenga piu di due microorganismi. Allora:
1. L'estremale sinistro deve avere un legame con due 
microorganismi distinti (uno dei due puo
essere l'estremale destro).
2. L'estremale destro deve avere un legame con due 
microorganismi distinti (uno dei due puo
essere l'estremale sinistro).
3. Sia M un microorganismo qualunque non estremale e sia
 P(M) = (x; y). Allora, M ha un
legame con due altri microorganismi Ms e Md tali che, posto
 P(Ms) = (xs; ys) e P(Md) =
(xd; yd), deve valere:
xs < x e x < xd

invece nell'esempio di destra ci sono 2 coppie di organismi che hanno solo un legame tra di loro e tra questi il punto b che ha legame solo con il punto a, nonostante b sia estremo destro...

non capisco.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by KiVan on 04-04-2006 13:26:

controlla bene, il punto b ha i seguenti legami: b-->c ; b--->a

a quanto ho capito quello di sinistra segue le regole ma non e' vitale mentre quello di destra segue le regole ed e' vitale perche' l'energia dei legami e' la minore possibile...

Posted by maynard80 on 04-04-2006 13:32:

Originally posted by KiVan
controlla bene, il punto b ha i seguenti legami: b-->c ; b--->a

a quanto ho capito quello di sinistra segue le regole ma non e' vitale mentre quello di destra segue le regole ed e' vitale perche' l'energia dei legami e' la minore possibile...

nel senso che contano i legami verticali e orizzontali? mi sono fatto ingannare dal fatto che non sono marcati e contavo solo quelli obliqui.

ma allora come facciamo a sapere se esistono o meno i legami
g->a , e->d nella figura di sinistra? nel conto non dovrebbero esistere, ma perchè?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by KiVan on 04-04-2006 14:15:

io ho stampato il testo del progetto e i legami orizzontali si vedono benissimo... invece nella versione pdf si fanno fatica a vedere...

cmq e' come un circuito.. per cui i legami in quella di sinistra sono :

f - g - c - a - b - d - e - f (siamo tornati all'inizio)

per quello di destra sono:

f - g - a - b - c - d - e - f (inizio)

Posted by maynard80 on 04-04-2006 14:26:

Originally posted by KiVan
io ho stampato il testo del progetto e i legami orizzontali si vedono benissimo... invece nella versione pdf si fanno fatica a vedere...

cmq e' come un circuito.. per cui i legami in quella di sinistra sono :

f - g - c - a - b - d - e - f (siamo tornati all'inizio)

per quello di destra sono:

f - g - a - b - c - d - e - f (inizio)

interessante, quindi i legami formano un cammino che ha come sorgente e arrivo lo stesso punto. e sono tutti di grandezza uguale.

tutto sta nel trovare il cammino minimo, al solito...

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by mapenzi81 on 04-04-2006 14:48:

beh no....non hanno tutti lunghezza uguale....

ma che burdeeello!!!

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by maynard80 on 04-04-2006 15:18:

beh se ogni punto è commesso ad altri 2 allora dovrebbe essere una lista di adiacenze dove ogni punto ha 2 adiacenze, no?

a meno che i legami non siano unilaterali.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by maynard80 on 05-04-2006 15:59:

vedo che vi siete messi giu di lena! nessuno posta idee?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by miles on 05-04-2006 18:26:

ho dei dubbi sulle liste di adiacenza perchè ogni punto può avere più vicini e bisogna scegliere le combinazioni che portano ad avere un peso minimo, quindi programmazione dinamica???

Posted by mapenzi81 on 05-04-2006 18:38:

quindi te vuoi creare una lista per memorizzare i collegamenti tra i vari punti?

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by miles on 05-04-2006 19:16:

no un albero binario di ricerca che velocizza la ricerca, gli inserimenti, ecc.

Posted by xeon on 05-04-2006 23:30:

Ciao,
io è tutto il giorno che ci pesto contro la testa.
Alla fine, mi son messo a cercare con google, e penso di aver scoperto perchè è così infame questo progetto.
Trovare il cammino di costo minimo è un problema del "Commesso Viaggiatore", che appartiene alla classe dei problemi NP.
Per questo problema, esistono solo alcune soluzioni, di cui quelle esatte vanno bene solo per problemi fino a circa 50 punti. dopodichè il tempo computazionale diventa proibitivo.

Ho cercato se ci sono implementazioni risolutive già pronte, da poter utilizzare, e qualcosa c'è.
Il problema è che riutilizzarle è un macello.
Sul scriversi da soli un'implementazione risolutiva del problema ci ho pensato, ma non mi sembra una cosa fattibile.

Per informazioni sul Commesso Viaggiatore:
http://it.wikipedia.org/wiki/Proble...sso_viaggiatore

Una pagina con link a software che implementano la soluzione:
http://www.or.deis.unibo.it/research_pages/tspsoft.html

Segnalo tra tutti "Concorde", che è in ANSI C e implementa varie soluzioni possibili del problema, tra cui anche quella esatta, che speravo fosse la più semplice (e quindi di poterla usare...) ma è una mazzata di roba il sorgente...
Molto carina comunque l'interfaccia per windows, dateci un occhio.

Se qualcuno trova qualche strada percorribile per fare questo progetto...

Posted by mapenzi81 on 05-04-2006 23:43:

No xeno non dirmi cosi che sto gia impazzendo di mio.....

Ho provato anche io a pensare come minimizzare la colonia....domani mattina provo a guardare meglio...magari qualche algoritmi sui grafi ci puo venire incontro...

una domanda...gli script sulle strutture dati presenti su algoteam si possono usare tranquillamente?

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by xeon on 06-04-2006 09:35:

Beh magari con qualche aggiustamento penso di sì...il problema è capire cosa usare e come usarlo...

Posted by Gehur on 06-04-2006 09:40:

ma il piano esiste o non esiste?? i microorganismi li mettete dentro una struttura?? una lista? insomma serve una struttura dove la cancellazione e l'inserimento siamo facili da eseguire

Posted by Polsy on 06-04-2006 10:48:

Originally posted by xeon
Ciao,
io è tutto il giorno che ci pesto contro la testa.
Alla fine, mi son messo a cercare con google, e penso di aver scoperto perchè è così infame questo progetto.
Trovare il cammino di costo minimo è un problema del "Commesso Viaggiatore", che appartiene alla classe dei problemi NP.
Per questo problema, esistono solo alcune soluzioni, di cui quelle esatte vanno bene solo per problemi fino a circa 50 punti. dopodichè il tempo computazionale diventa proibitivo.

Ho cercato se ci sono implementazioni risolutive già pronte, da poter utilizzare, e qualcosa c'è.
Il problema è che riutilizzarle è un macello.
Sul scriversi da soli un'implementazione risolutiva del problema ci ho pensato, ma non mi sembra una cosa fattibile.

Per informazioni sul Commesso Viaggiatore:
http://it.wikipedia.org/wiki/Proble...sso_viaggiatore

Una pagina con link a software che implementano la soluzione:
http://www.or.deis.unibo.it/research_pages/tspsoft.html

Segnalo tra tutti "Concorde", che è in ANSI C e implementa varie soluzioni possibili del problema, tra cui anche quella esatta, che speravo fosse la più semplice (e quindi di poterla usare...) ma è una mazzata di roba il sorgente...
Molto carina comunque l'interfaccia per windows, dateci un occhio.

Se qualcuno trova qualche strada percorribile per fare questo progetto...

in realtà non è proprio un circuito hamiltoniano perchè hai delle restrizioni in più (il fatto che ogni nodo deve avere un link a destra e uno a sinistra) che immagino facilitino le cose (non danno mai da risolvere degli NP-completi

)

tra l'altro è dato per scontato che non ci siano 3 punti con la stessa ascissa e che non ci siano 2 punti con l'ascissa minima/massima? perchè se una delle 2 accade è impossibile formare una colonia vitale così com'è definita nelle specifiche

Posted by maynard80 on 06-04-2006 11:28:

Originally posted by Polsy

tra l'altro è dato per scontato che non ci siano 3 punti con la stessa ascissa e che non ci siano 2 punti con l'ascissa minima/massima? perchè se una delle 2 accade è impossibile formare una colonia vitale così com'è definita nelle specifiche

l'ultimo commento non l'ho mica capito....

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by Gehur on 06-04-2006 12:02:

chi mi da delle dritte/idee sulla funzione crea....non so come farla

Posted by mapenzi81 on 06-04-2006 12:08:

dai un occhi ai vecchi progetti che ci sono nell area filez...

io ho creato la struttura dati e lo semplicemente inizializzata....

nn penso serva d piu

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by tandrea85 on 06-04-2006 12:48:

io non riesco a capire quanti possibili legami si possono formare tra piu punti.. nell'esempio 1 fa vedere 2 possibili configurazioni, ma ce ne sono altre?

Posted by mapenzi81 on 06-04-2006 12:56:

beh si...ogni punto puo connettersi
a uno quasiasi dei punti cn x minore ed a uno con x maggiore (sempre che questi siano ancora "liberi" )

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by Gehur on 06-04-2006 13:06:

guarderò..hai detto che hai inizializzato la struttra dati,se non pretendo troppo mi puoi dire che tipo di struttura hai utilizzato

Posted by tandrea85 on 06-04-2006 13:18:

Originally posted by tandrea85
io non riesco a capire quanti possibili legami si possono formare tra piu punti.. nell'esempio 1 fa vedere 2 possibili configurazioni, ma ce ne sono altre?

si ma l'esempio fa vedere un circuito chiuso.. se le connetto a caso controllando solo la x posso formare una roba a zig zig ke va su e giu e non riuscendo piu a tornare al punto di partenza

Posted by Polsy on 06-04-2006 13:34:

Originally posted by maynard80
l'ultimo commento non l'ho mica capito....

come non detto, rileggendo mi sono accorta che 2 punti non possono avere la stessa ascissa (anche se è detto un po' tra le righe...)

Posted by xeon on 06-04-2006 13:37:

Originally posted by mapenzi81
dai un occhi ai vecchi progetti che ci sono nell area filez...

io ho creato la struttura dati e lo semplicemente inizializzata....

nn penso serva d piu

Non so ancora di preciso, ma per me si deve studiare quanti cammini hamiltoniani si possono avere con n punti. Se trovo qualcosa vi dico, ma non è importante per me sapere quanti cammini ci sono.

Qualcuno invece ha risolto il rompicapo della funzione colonia() ? ...

Posted by Gehur on 06-04-2006 13:56:

oggi pomeriggio penso alle funzioni crea e inserisci..., per me il problema è come iniziare (almeno per ora)

Posted by xeon on 06-04-2006 14:19:

Eh ok, ma se poi arrivi a implementare colonia() (ma anche genera() eh) e scopri che le strutture dati che hai usato non van bene?

Posted by mapenzi81 on 06-04-2006 14:39:

Originally posted by Polsy
come non detto, rileggendo mi sono accorta che 2 punti non possono avere la stessa ascissa (anche se è detto un po' tra le righe...)

molto tra le righe...

quindi struttura dati indicizzata sulla x ?
in questo modo le chiavi sono univoche...

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by Polsy on 06-04-2006 16:05:

Originally posted by mapenzi81
molto tra le righe...

quindi struttura dati indicizzata sulla x ?
in questo modo le chiavi sono univoche...

visto che poi ti serve ricercare i punti anche per nome puoi indicizzarli sia secondo le coordinate che in base al nome
cioè ti crei una struct per le info riguardanti il singolo punto, poi fai due "meta-strutture" (liste, alberi...) una ordinata secondo le x e una lessicograficamente, ognuna delle quali ha nel singolo nodo il puntatore alla struttura con le info del punto
in questo modo hai 2 criteri di ordinamento senza duplicare informazioni

Posted by mapenzi81 on 06-04-2006 17:33:

Originally posted by Polsy
visto che poi ti serve ricercare i punti anche per nome puoi indicizzarli sia secondo le coordinate che in base al nome
cioè ti crei una struct per le info riguardanti il singolo punto, poi fai due "meta-strutture" (liste, alberi...) una ordinata secondo le x e una lessicograficamente, ognuna delle quali ha nel singolo nodo il puntatore alla struttura con le info del punto
in questo modo hai 2 criteri di ordinamento senza duplicare informazioni

mmmmm
si pero nel singolo nodo avro sicuramente i puntatori della struttura

per ex negli alberi ho up, right e left....

devo duplicare i puntatori che riguardano le strutture all interno del singolo nodo...3 puntatori per l'albero (lista) che ordina per x e 3 puntatori per lo'albero (lista) per l'ordinamento lessicografo...

è corretto?

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by Polsy on 06-04-2006 20:03:

Originally posted by mapenzi81
mmmmm
si pero nel singolo nodo avro sicuramente i puntatori della struttura

per ex negli alberi ho up, right e left....

devo duplicare i puntatori che riguardano le strutture all interno del singolo nodo...3 puntatori per l'albero (lista) che ordina per x e 3 puntatori per lo'albero (lista) per l'ordinamento lessicografo...

è corretto?

si nel senso, avrai 3 strutture diverse
esempio:
la struttura punto contiene x, y, nome, link sx e dx
la struttura (lista?) che ordina per coordinate avrà 3 puntatori *prec *succ e *punto
la struttura (albero?) che ordina per nome avrà *left *right e *punto

oppure te ne sbatti dell'efficienza e tieni la struttura ordinata per le x e quando devi cercare un punto per nome scorri tutto l'albero (lista)

Posted by maynard80 on 06-04-2006 20:16:

Originally posted by Polsy

la struttura punto contiene x, y, nome, link sx e dx
la struttura (lista?) che ordina per coordinate avrà 3 puntatori *prec *succ e *punto
la struttura (albero?) che ordina per nome avrà *left *right e *punto

mi sa che è il contrario, l'albero per le coordinate e la lista ordinata lessicograficamente.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by mapenzi81 on 06-04-2006 20:23:

Originally posted by Polsy
si nel senso, avrai 3 strutture diverse
esempio:
la struttura punto contiene x, y, nome, link sx e dx
la struttura (lista?) che ordina per coordinate avrà 3 puntatori *prec *succ e *punto
la struttura (albero?) che ordina per nome avrà *left *right e *punto

oppure te ne sbatti dell'efficienza e tieni la struttura ordinata per le x e quando devi cercare un punto per nome scorri tutto l'albero (lista)

riflettendoci credo che sia la soluzione ottimale....

mi sa che stasera mi tocchera implementarla

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by mapenzi81 on 06-04-2006 20:29:

Originally posted by maynard80
mi sa che è il contrario, l'albero per le coordinate e la lista ordinata lessicograficamente.

si..mi sa che è la soluzione migliore...
...mi sta sfuggendo come fare l ordinamento lessicografo.... :shock:

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by Gehur on 06-04-2006 20:42:

io pensavo di inserire dentro una lista le strutture punto solo che devo pensare come fare la funz colonia....
piuttosto qualcuno mi può spiegare come si calcola l'energia..si insomma io l'ho calcolata e mi son venuti 25 e 20 ma vorrei sapere altri pareri xche mi sembra di aver letto che l'energia non è collegata ai legami tra i punti ma io ho usato proprio i legami tra i punti per calcolarla....(almeno credo!)

Posted by xeon on 06-04-2006 21:04:

Io penso che l'albero ordinato lessicograficamente (basta una strcmp() ) sia ottimale per ricercare nodi, mentre invece per i punti occupati sul piano sia meglio una lista, dato che permette di eseguire inserimenti e cancellazioni in tempo lineare, oltre a poter accedere agli elementi adiacenti di un nodo in tempo unitario (si ricerca prima un microorganismo per nome nell'albero, poi tramite il puntatore al suo punto sul piano occupato si recupera il punto della lista).

Qualcuno ha capito come fare colonia() ?????

Posted by Gehur on 06-04-2006 21:14:

sulla lista (inserimento e cancellazione) hai detto quello che avevo pensato..per quanto riguarda la colonia ho notato che sicuramente il l'energia minore è dovuta a un numero di collegamenti/cammini uguale al munero di punti(vabbe cosa ovvia)

piuttosto nessuno mi chiarisce come calcolare l'energia...

Posted by mapenzi81 on 06-04-2006 21:17:

Originally posted by Gehur
sulla lista (inserimento e cancellazione) hai detto quello che avevo pensato..per quanto riguarda la colonia ho notato che sicuramente il l'energia minore è dovuta a un numero di collegamenti/cammini uguale al munero di punti(vabbe cosa ovvia)

piuttosto nessuno mi chiarisce come calcolare l'energia...

beh....l energia tra due punti è la differenza tra le sue coordinate

P1(5,6)->p2(3,4) E= |5-3|+|6-4|=2+2=4

secondo me cè qualche relazione tra i punti per ottimizzare il percorso....il problema è trovarla e dimostrarla

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by Gehur on 06-04-2006 21:23:

si ok...ma fammi un esempio con 3 o 4 punti perfavore

hai provato a calcolare l'energia nell esempio ti è venuta 24 e poi 20??
a me è venuta, ho fatto Edi fg + Ecg + Eac ecc... solo che in questo modo si è vincolati dai legami mentre nel testo mi sembra di capire che l'energia vitale dipende solo dalle coordinate e non dai legami...

Posted by mapenzi81 on 06-04-2006 21:28:

Originally posted by Gehur
si ok...ma fammi un esempio con 3 o 4 punti perfavore

hai provato a calcolare l'energia nell esempio ti è venuta 24 e poi 20??
a me è venuta, ho fatto Edi fg + Ecg + Eac ecc... solo che in questo modo si è vincolati dai legami mentre nel testo mi sembra di capire che l'energia vitale dipende solo dalle coordinate e non dai legami...

si mi viene 20 e 24
beh....deve essere legata dai legami..se no qualsiasi coppia che prendi puo andare bene....invece dei prendere le coppie che minimizzano il percorso

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by Gehur on 06-04-2006 21:32:

infatti ma all'inizio della pagina numero 2 (subito dopo il punto 4) ce scritto che i legami non centrano (almeno io ho capito cosi)... vabbe per oggi basta

Posted by Polsy on 06-04-2006 21:34:

Originally posted by maynard80
mi sa che è il contrario, l'albero per le coordinate e la lista ordinata lessicograficamente.

si beh in realtà dipende dall'algoritmo che scegli (per quello mettevo i punti di domanda)
per come avevo pensato di implementare la funzione che trova la colonia vitale paradossalmente a me risulta + efficiente una lista, perchè mi serve scandire i punti da sinistra a destra e non mi capiterà di cercare un punto in base al valore della sua ascissa
per l'ordine lessicografico invece credo che l'albero sia la soluzione migliore (soprattutto se lo si rende bilanciato)

Posted by mapenzi81 on 06-04-2006 21:35:

Originally posted by Gehur
infatti ma all'inizio della pagina numero 2 (subito dopo il punto 4) ce scritto che i legami non centrano (almeno io ho capito cosi)... vabbe per oggi basta

io l'ho interpretata come
....ogni volta che modifichi qualche punto...lo inserisci, lo mofichi, lo elimini etc...si parte da zero e si cancellano tutti i collegamenti esistenti (preesistenti)

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by Gehur on 06-04-2006 21:41:

si be può essere una giusta interpretazione, visto che per calcolare l'energia bisogna considerare i punti 2 a 2 Egf + Ecg + Eac + Eba + Ebd + Ede + Eef....

domani ci penso meglio

Posted by maynard80 on 07-04-2006 14:38:

ma invece una hash table con chiave i nomi?? e poi una lista di adiacenze per il grafo? (che si crea ogni volta che il grafo è modificato)

una volta che abbiamo la lista di adiacenze ci applichiamo un algo del libro... no?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by mapenzi81 on 07-04-2006 14:41:

Originally posted by maynard80
ma invece una hash table con chiave i nomi?? e poi una lista di adiacenze per il grafo? (che si crea ogni volta che il grafo è modificato)

una volta che abbiamo la lista di adiacenze ci applichiamo un algo del libro... no?

anke....
pero cosi non t viene comodo l'ordinamento per le x

una conferma...
me lo sono sognato o le coordinate sono interi positivi sia x che y?

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by maynard80 on 07-04-2006 15:23:

essendo su Z col cavolo che sono positivi.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by mapenzi81 on 08-04-2006 18:04:

hai ragione
cmq non cambia molto..per il calcolo dell energia...

qualcuno è a buon punto cn la creazione della colonia?

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by maynard80 on 08-04-2006 19:28:

per il piano chi parlava di liste intendeva lista di adiacenze vero?

qualcuno ha una implementazione base della lista di adiacenze?

code:
struct nodo{
      int X,Y;
      char *nome;
}

struct listaNodi{
      nodo *nodo;
      struct listaNodi *next;
      struct listaAdiacenze *adj;
}

struct listaAdiacenze{
      struct listaNodi *nodo_rappresentato;
      struct listaAdiacenze *next;
}

E' una cagata?(tolto eventuali errori di sintassi) non trovo da nessuna parte tale implementazione, ho trovato solo liste semplici e bidirezionali, per le liste di adiacenze si intende una lista con tutti i punti dove in ogni punto c'è un puntatore ad una lista dei nodi adiacenti a quel punto.. quello che non mi torna è se ogni adiacenza deve a sua volta puntare alla lista base oppure no e come gestire le cancellazioni.

per il resto una volta creata tale lista e avendo una struttura che memorizza i punti (albero) si appica un algo di shortest path sul grafo (la lista).

non credete? l'energia è la distanza tra 2 punti e ogni nodo ha al + 2 adiacenze.
in + il fatto che non esistono 2 punti con la stessa ascissa può rivelarsi una semplificazione, ma non so ancora come.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by jonnypee on 13-04-2006 09:36:

ciao a tutti...
volevo fare un piccolo appello. è quasi un anno che mi sto portando dietro quest'esame, sono proprio negato a programmare in C...non è che qualcuno sotto ricompensa può aiutarmi a farlo???

Posted by lino on 13-04-2006 10:51:

Chi ha utilizzato un albero lessicografico per i nomi dei microorganismi e una lista per le coordinate che algoritmo ha utilizzato per calcolare l'energia di una colonia?

Posted by maynard80 on 13-04-2006 13:47:

io sto usando un albero ordinato lessicograficamente e una lista che tenga dei puntatori all'albero ordinata secondo la sola x (non possono esserci 2 nodi con la stessa x)

per la colonia vitale penso che bisogna usare un'euristica per il prob. del commesso viaggiatore, mentre per il genera il problema che ho è:

se sul segmento (0,0)-(1,2) devo generare un organismo che coordinate ha?? la y è 1 ma la x è 0,5!!! e così nella maggior parte dei casi..

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by KiVan on 13-04-2006 15:25:

a quanto ho capito generi l'organismo se e solo se i valori di x e y dell'organismo probabile sono interi e se non ci sono altri organismi con la stessa x

in pratica per vedere se un organismo ha le coordinate intere ti ricavi l'equazione della retta (o meglio del segmento) passante per i due organismi, ci sostituisci nell'equazione al posto di X tutti i naturali compresi tra gli estremi del segmento e se ottieni delle Y intere hai trovato un organismo probabile...

se non vengono soddisfatte queste due condizioni semplicemente non crei nulla...

Posted by maynard80 on 13-04-2006 23:14:

Originally posted by KiVan
a quanto ho capito generi l'organismo se e solo se i valori di x e y dell'organismo probabile sono interi e se non ci sono altri organismi con la stessa x

in pratica per vedere se un organismo ha le coordinate intere ti ricavi l'equazione della retta (o meglio del segmento) passante per i due organismi, ci sostituisci nell'equazione al posto di X tutti i naturali compresi tra gli estremi del segmento e se ottieni delle Y intere hai trovato un organismo probabile...

se non vengono soddisfatte queste due condizioni semplicemente non crei nulla...

beh il testo di questo prog. mi sembra scritto coi piedi

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by logan.x on 14-04-2006 13:58:

Ciao, io invece ho la seguente domanda:
sono ammessi percorsi che si incrociano?
Mi spiego:
ho preso come riferimento i punti del primo esempio del file di input
A(1,5)
C(2,15)
E(3,8)
F(4,2)
B(5,10)
D(6,9)

Provando su carta, io trovo 2 configurazioni di punti che mi danno lo stesso valore minimo (cioe' 40)
Una e'
A -> C -> E -> B -> D -> F -> A
mentre l'altra e'
A -> C -> E -> D -> B -> F -> A
Disegnandole si nota che il segmento ED incrocia BF
E' ammesso tale percorso?

Posted by xeon on 14-04-2006 19:32:

Il percorso, se non viola le 3 condizioni iniziali, è permesso.

Soluzione (penso l'unica) al problema di colonia: provare tutte le configurazioni.
Partendo da un punto, si creano tutti i cammini che non violano le 3 regole.
Quando si crea un ciclo (un nodo con due collegamenti) si calcola l'energia richiesta dal cammino, e se è la minore trovata finora si memorizza il cammino come quello di costo minore.

Posted by maynard80 on 15-04-2006 10:36:

Originally posted by xeon
Il percorso, se non viola le 3 condizioni iniziali, è permesso.

Soluzione (penso l'unica) al problema di colonia: provare tutte le configurazioni.
Partendo da un punto, si creano tutti i cammini che non violano le 3 regole.
Quando si crea un ciclo (un nodo con due collegamenti) si calcola l'energia richiesta dal cammino, e se è la minore trovata finora si memorizza il cammino come quello di costo minore.

se ti calcoli tutti i cammini il tuo sistema avrà complessità esponeniale...

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by marcomaria on 15-04-2006 21:36:

Originally posted by Polsy

per l'ordine lessicografico invece credo che l'albero sia la soluzione migliore (soprattutto se lo si rende bilanciato)

stavo pensando ad una tabella hash, dovrebbe essere estremamente performante per ricerca/ins/cancellazione in base al nome che sembra il caso primario;
mentre per coordinate, che e' il caso secondario, usare una semplice lista...ma queste servono per gli algoritmi e forse e' meglio avere un albero bilaciato
ps: per la funzione genera() con il coefficiente angolare del segmento creato si potrebbe definire se si intersecano pti oppure no...boh...riflessioni da tarda sera

Posted by Polsy on 15-04-2006 23:14:

Originally posted by marcomaria
stavo pensando ad una tabella hash, dovrebbe essere estremamente performante per ricerca/ins/cancellazione in base al nome che sembra il caso primario;

ero al primo turno e con goldwurm non si fanno le tabelle hash, quindi non ti saprei dire...

mentre per coordinate, che e' il caso secondario, usare una semplice lista...ma queste servono per gli algoritmi e forse e' meglio avere un albero bilaciato

dipende tutto da che tipo di algoritmo usi, se scandisci i punti sempre da sx a dx (o viceversa) senza cercare una x in particolare ti conviene una lista, mentre se fai una cosa del tipo "voglio i punti compresi tra a e b" ti conviene un albero (magari a intervalli)

ps: per la funzione genera() con il coefficiente angolare del segmento creato si potrebbe definire se si intersecano pti oppure no...boh...riflessioni da tarda sera

+ semplice

fai conto di avere A in (x1,y1) e B in (x2,y2)
se trovi x=|x2-x1| e y=|y2-y1| ti accorgi che A e B non possono generare solo se sono coprimi

se invece trovi i divisori comuni trovi anche i punti in cui possono generare (con un po' di matematica

in realtà basta l'mcd)

Posted by tandrea85 on 16-04-2006 10:26:

Originally posted by maynard80
se ti calcoli tutti i cammini il tuo sistema avrà complessità esponeniale...

io ho fatto proprio cosi.. anzi il mio è (n-1)! ma con l'input del prof l'algoritmo se la viaggia.. con 6 nodi le permutazioni sono solo 120 da calcolare nel mio caso

mo devo capire come fare genera..

Posted by miles on 16-04-2006 18:02:

io per genera ho usato l'equazione della retta y=mx+q calcolo m e q in base ai due micro (x1,y1), (x2,y2) poi uso l'equazione e se y è un intero allora posso generare un nuovo micro. avete invece suggerimenti per la colonia vitale perche come l'ho implementata io in alcuni casi non trova la soluzione migliore ad esempio come nell'ultimo C dell'esempio.

Posted by miles on 16-04-2006 18:04:

dimenticavo...........ma perchè l'output dell'ultimo stampa non è ordinato lessicograficamente???????????

Posted by maynard80 on 16-04-2006 19:16:

dunque se invece di un algo (che per questo prob è sicuramente esponenziale) usiamo un'Euristica è normale che non sempre trovi il cammino migliore ma ci vada vicino.

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

io la penso così, o siamo veloci ma non sempre esatti o siamo a complessità esagerate, io tendo per la prima. di più non so

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by miles on 17-04-2006 11:00:

sì ok ma se non funziona sugli input del prof il progetto non è accettato...........provare per credere.................quindi come c.zzo si implementa sto colonia esisterà una soluzione anche perchè implementare un algoritmo basato sul commesso viaggiatore è un lavoro spaventoso! che palle sto progetto!

Posted by maynard80 on 17-04-2006 12:20:

Originally posted by miles
sì ok ma se non funziona sugli input del prof il progetto non è accettato...........provare per credere.................quindi come c.zzo si implementa sto colonia esisterà una soluzione anche perchè implementare un algoritmo basato sul commesso viaggiatore è un lavoro spaventoso! che palle sto progetto!

esatto, è roba di algoritmiII e cmq uno dei problemi + difficili!

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by mapenzi81 on 17-04-2006 13:17:

concordo.....

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by miles on 17-04-2006 19:13:

invece per quanto riguarda l'output dell'ultimo censimento che non è ordinato lessico.... ho mandato una mail al prof per sentire che mi dice........domani provo a modificare il mio colonia e poi vi faccio sapere.....spero di non riprendere a imprecare visto che sono già tre anni che ho smesso!!!!!!!!!!!

Posted by mapenzi81 on 17-04-2006 20:51:

ma no dai...nn cè bisogno di imprecare...qui cè proprio bisgno di bestemmiare!!!!

cmq al di la di cio.....

nell input del problema cè
m epsilon 0 -10

che nn corrisponde allo standard del problema....

qualcuno ha già chiesto ai prof come il programma deve "ragire" in questo caso?

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by miles on 18-04-2006 08:44:

penso che lì sia un errore del prof

Posted by mapenzi81 on 18-04-2006 11:47:

correzioni in :

http://homes.dsi.unimi.it/~fiorenti/labalg05.html

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by Nosferatu on 18-04-2006 12:39:

miles puoi spiegarmi come si fa a trovare m e q nell'equazione della retta passante per i 2 micro (x1,y1), (x2,y2) ... la matematica non è il mio forte

Posted by marcomaria on 18-04-2006 14:50:

qlc1 ha usato il codice di Algoteam x implementare RB tree?
avrei un dubbio...

Posted by tandrea85 on 18-04-2006 17:41:

Originally posted by Nosferatu
miles puoi spiegarmi come si fa a trovare m e q nell'equazione della retta passante per i 2 micro (x1,y1), (x2,y2) ... la matematica non è il mio forte

http://www.itg-rondani.it/dida/Mate...tta/retta8.html

Posted by KiVan on 19-04-2006 10:09:

ragazzi sul libro "introduzione agli algoritmi" se guardate il problema alla fine del capitolo 16 noterete che e' praticamente uguale all'algoritmo del progetto...

lo chiama "problema del commesso viaggiatore bitonico e euclideo"
come suggerimento dice: "si effettui una scansione da sinistra verso destra mantenendo le possibilita' ottime per le due parti del cammino"...

qualcuno sa interpretare a modo questo suggerimento?

Posted by marcomaria on 19-04-2006 11:18:

grazie, molto molto interessante...
una possibile soluzione: http://www.hassineletaief.com/COMP510-HW-2.htm

Posted by Nosferatu on 19-04-2006 12:10:

Qualcuno sa per caso come si fà a concatenare ad una stringa un intero

Posted by tandrea85 on 19-04-2006 13:18:

Originally posted by Nosferatu
Qualcuno sa per caso come si fà a concatenare ad una stringa un intero

code:
int x = ...;
char strtemp[]="";
sprintf(strtemp, "%d",x);

poi usi la strcat per concatenera le 2 stringhe

Posted by maynard80 on 19-04-2006 13:33:

dunque io ho l'albero con i nodi ordinati lessicograficamente e una lista che invece li dovrebbe ordinare in base alla x... ma come faccio ad applicare un algo di ordinamento (rand-quicksort) ad una lista?devo scorrere tutta la lista ricavare l'array poi cancelare la lista ordinare l'array e poi riempirlo??? un delirio, ma se invece inserisco ordinatamente (invece di inserire in testa) ogni volta nel caso peggiore mi scorro la lista... cosa consigliate?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by mapenzi81 on 19-04-2006 13:50:

anke io ho un problema simile....
ogni volta che inserisco un elemento lo posiziono nella sua posizione scorrento la lista....
molto inserion sort...

se usi la lista ci impieghi n+nlg2+n ma utilizzi piu memoria....

io sto cercando una 3 soluzione....tipo un quicksort o mergesort sulla lista direttamente giocando un po con i puntatori...

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by maynard80 on 19-04-2006 14:00:

mapenzi se trovi la soluzione dammi una dritta!

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by mapenzi81 on 19-04-2006 14:03:

se la trovo...volentieri....

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by Nosferatu on 19-04-2006 15:36:

Dopo aver calcolato m e q come faccio a verificare che la y risultante sia un intero (nel metodo genera)?

Posted by tandrea85 on 19-04-2006 19:28:

boh io ho finito.. con l'input del prof ci impiega 0.063sec.. direi abbastanza buono anke se nn ottimo..

ho usato solo 1 lista ordinata lessicograficalmente e un array di appoggio per calcolare il cammino con energia minima..

Posted by maynard80 on 20-04-2006 07:38:

Originally posted by tandrea85
boh io ho finito.. con l'input del prof ci impiega 0.063sec.. direi abbastanza buono anke se nn ottimo..

ho usato solo 1 lista ordinata lessicograficalmente e un array di appoggio per calcolare il cammino con energia minima..

puoi delucidarci su come hai fatto?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by tandrea85 on 20-04-2006 09:30:

Originally posted by maynard80
puoi delucidarci su come hai fatto?

certo.. ho semplicemente fatto tutte le prove possibili con delle permutazioni.. N nodi -> (N-1)! permutazioni possibili

ho costruito un array con dentro i microorganismi e su quello ho fatto il calcolo di tutte le permutazioni possibili partendo sempre dall'estremale sinistro, scartando i percorsi ke nn verificavano una certa condizione sulla x e ho scoeprto ke mi veniva fuori sempre il percorso corretto..

Posted by mapenzi81 on 20-04-2006 09:31:

....qualche delucidazione su come si calcola il tempo di esecuzione??

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by tandrea85 on 20-04-2006 10:11:

Originally posted by mapenzi81
....qualche delucidazione su come si calcola il tempo di esecuzione??

#include <time.h>

all'ìnizio del main metti questo

code:
clock_t start,end;
double tempo;
start=clock();

prima di uscire dal programma quindi con la pressione della f metti questo

code:
end=clock();
tempo=((double)(end-start))/CLOCKS_PER_SEC;
printf("execution_time == %f seconds\n", tempo);

ovviamente l'input devi ridirigerlo all'esecutibile se no sta roba nn funge

Posted by mapenzi81 on 20-04-2006 11:12:

grazie

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by sasaciric on 21-04-2006 08:42:

Tempo di esecuzione

Ragazzi ho provato con 20 punti e ci mette circa 5 minuti e mezzo. Con l'esempio del prof anche a me è immediato. Voi con 20 punti quanto ci mettete??

Grazie.

Ciao.

Sasaciric

Posted by mapenzi81 on 21-04-2006 09:25:

un pokino di meno...

ragazzi ci postiamo alcuni test su grossi numeri e li compariamo cosi evitiamo di controllarli a mano?

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by sasaciric on 21-04-2006 09:29:

Cosa intendi per un pochino meno? La metà o più o meno lo stesso tempo??

Posted by maynard80 on 21-04-2006 10:03:

complessità schifosa evidentemente...calcolare tutte le possibili combinazioni non è certo la buono, anzi è la soluzione peggiore

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by tandrea85 on 21-04-2006 10:09:

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

Posted by sasaciric on 21-04-2006 10:20:

Caro maynard80 evidentemente l'unico modo per risolvere il problema del commesso viaggiatore è provare tutte le configurazioni possibili (che rispettino i vincoli del progetto e quindi sono meno rispetto a n! del commesso viaggiatore). I metodi euristici non portano mai alla soluzioni ottimale a meno di grandi quantità di punti. Realisticamente i test da fare non sono su centinaia di punti ma su 6/10 come negli esempi del prof.

Posted by tandrea85 on 21-04-2006 10:37:

Originally posted by sasaciric
Caro maynard80 evidentemente l'unico modo per risolvere il problema del commesso viaggiatore è provare tutte le configurazioni possibili (che rispettino i vincoli del progetto e quindi sono meno rispetto a n! del commesso viaggiatore). I metodi euristici non portano mai alla soluzioni ottimale a meno di grandi quantità di punti. Realisticamente i test da fare non sono su centinaia di punti ma su 6/10 come negli esempi del prof.

per la storia dell'n! cmq il programma ne valuta sempre n! ma poi sceglie se è valido o meno.. infatti a me ne risultano per es. 15/720 validi nel primo caso, ma i 720 li valuta cmq tutti

altra cosa: ma l'output del prof è tutto corretto? a me inverte un po di valori per esempio al posto di

b,(5,10) <- d,(7,2) -> fd6,(6,2) scrive fd6,(6,2) <- d,(7,2) -> b,(5,10)

è un problema?

Posted by sasaciric on 21-04-2006 10:43:

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

Posted by tandrea85 on 21-04-2006 10:50:

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

allora io faccio cosi:
1- memorizzo le (n-1)! permutazioni
2- valuto ogni permutazione se è valida o meno
3- se è valida calcola la lunghezza del percorso, se no nn fa nulla e passa alla prox

Posted by sasaciric on 21-04-2006 11:02:

sul punto 2 potresti ottimizzare ( invece di valutare se è giusto alla fine) : quando aggiungi un nuovo elemento dovresti controllare se viola le regole, così non stai a calcolartelo tutto (anche non valido) per scartarlo alla fine

pensa se hai 10 punti e il terzo che hai aggiunto al cammino viola le regole, eviti di calcolarti tutte le permutazioni dei sette punti restanti

Posted by marcomaria on 21-04-2006 11:15:

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

si, attenzione che questo non e' TSP ma ci sono i vincoli che lo portano ad essere "problema del commesso viaggiatore bitonico e euclideo" (vedi qualche post precedente) risolvibile in O(n^2)

Posted by mapenzi81 on 21-04-2006 12:02:

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

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)

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by mapenzi81 on 21-04-2006 12:15:

anche la relazione è da consegnare domenica?

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by tandrea85 on 21-04-2006 15:26:

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)

a me quest'output me lo da senza i punti da l a t.. e me lo esegue in 3 sec.. con l'output da 20 punti invece il processo sotto linux mi viene killato, occupa troppe risorse.

Posted by karlost on 22-04-2006 11:43:

Suggerimenti GENERA()

Ciao a tutti!
Sono riuscito a completare la funz. colonia() senza usare tecniche di grafi o TSP particolari, ho usato la geometria e una funz. del libro del Sedgewick Algoritmi in C che parla dei cammini chiusi semplici.
Il mio problema e' che i tempi di calcolo sono decenti, adesso non so se lo scopo del progetto fosse stato di usare qualche tecnica di grafi per la colonia...? o paura che la soluz. non sia quella che si aspetta il prof.
Di strutture ho usato 2 RB tree per memorizzare la Colonia(con chiave arctg ..trovate tutto sul libro del sedgewik) e i microorganismi (con chiave ascissa) e un BST per i microorganismo ordinati per nome
Per la funz. genera() devo cercare ancora un metodo, qlcuno l'ha gia' fatto e gentilmente puo darmi suggerimenti..?
In bocca al lupo a tutti..

Posted by mapenzi81 on 22-04-2006 16:12:

karlost se guardi qualche post insietro trovi tutto....
cmq
calcoli la funzione della retta e per ogni x compresa tra i due punti guardi se la y corrispondente è un intero...

è normale che printf sotto linux aggiunga un carattere ^M ??

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by karlost on 22-04-2006 16:37:

Grazie 1000^n ....

^M a volte dipende dal terminale che usi, alcune shell tipo ksh o bash quando non sono in grado d'interpretare un tasto o una seq. di tasti ti restituiscono dei caratteri stranni.
O anche quando usi editor di testo non standard e poi tenti di aprire il file con un editor standard tipo VI alcuni caratteri che non è in grado d'interpretare te li rappresenta con ^M.

Posted by Corrado M. on 22-04-2006 16:39:

nessuno di voi ha usato l'algoritmo Approx-TSP-Tour che viene spiegato in uno dei paragrafi del capitolo ALGORITMI APPROSSIMATI sul nostro libro?

io stavo implementando quello, poi leggendo qui mi sono venuti forti dubbi.

__________________
"basta un paio de scarpe nove, e poi gira' tutto er munno"
>> www.javalab.it - www.jobcrawler.it - www.aboutdebian.com/install3.htm<<
Linux user #354593

Posted by mapenzi81 on 22-04-2006 18:50:

no...anche io ho optato per una soluzione geometrica...

risolto il ^M
modificando la funzione read_word ora funziona...
la cosa simpatica è che sotto Win.....
sto incominciando a capire il perchè sotto Win le applicazioni sono alquanto instabili...

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by maynard80 on 23-04-2006 10:56:

panico, scusate!
fino ad ora ho provato sempre le funzioni senza l'input da tastiera, ho finito ,ma proprio adessoc he devo prendere input da tastiera ho un problema!
la mia funzione

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

inserisce nell'albero puntato da p gli elementi x, y ed il nome.
ho sempre inserito nome tramite un puntatore ad una variabile dichiarata:

code:
char *nome="pincopallino"

e funziona

ma ora che prendo la variabile da

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

ad ogni inserimento tutti i nodi hanno l'ultimo nome inserito (puntano alla stessa variabile) ma non posso dichiarare in antcipo le variabili per ogni nodo in quanto non ne conosco il numero....

come avete fatto????! scusate so che è una cazzata, ma sono in panico!

PS: se qualcuno ha msn mi contatti

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by mapenzi81 on 23-04-2006 11:56:

qualcuno ha voglia di fare un confronto su un test su 500 - 600 punti?

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by maynard80 on 23-04-2006 12:06:

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

mapenzi sei un grande! grazie.

PS sto pomeriggio faccio volentieri il test dei 600 punti.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by mapenzi81 on 23-04-2006 12:09:

ooook

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by tandrea85 on 23-04-2006 18:03:

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

pazzo

io se supero gli 11 punti non va piu una bega :shock:

Posted by mapenzi81 on 23-04-2006 18:12:

azzzzzzzzzzzzzzzz

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by darkAntAreS on 23-04-2006 18:31:

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

guarda, se mi dici come fare a dare un input di 500-600 punti senza scriverli tutti magari

cmq, se ti basta, il mio l'ho testato su 150 punti (circa), per la sola funzione colonia() (tempo O(n^2)), e il tempo è 0,024 secondi

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Posted by maynard80 on 23-04-2006 19:17:

ragazzi ma nella mail dobbiamo consegnare solo il codice giusto? la relazione entro domani in busta, vero?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by darkAntAreS on 23-04-2006 19:27:

codice sorgente E relazione...in più gli devi stampare la relazione e portargliela entro domani

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Posted by mapenzi81 on 23-04-2006 19:38:

domani il dipartimento è chiuso...la parte cartacea la si porta il 26

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by tandrea85 on 23-04-2006 20:12:

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

Posted by maynard80 on 24-04-2006 08:53:

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 specicato 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 denizioni, 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.

mi pare che per mail bisognava mandare solo il codice, io ho fatto così.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by darkAntAreS on 24-04-2006 10:57:

le consegne di fiorentini e aguzzoli sono diverse, aguzzoli dice espressamente che vuole per mail anche la relazione, il tutto in un unico file .zip che deve avere la denominazione cognome.zip

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Posted by xeon on 24-04-2006 14:41:

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

Posted by mapenzi81 on 24-04-2006 14:48:

io ho fatto una cappellata...me ne sono accorto ora....
funziona quasi sempre in n^2 o anche meno....

ma nn è attendibile...aimè

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by karlost on 24-04-2006 15:10:

valutazione progetto

Ank'io ho lo stesso problema, mi sono accorto adesso che con alcuni input il mio prog. va in segmentation fault... azzz...
Cmq qualcuno sà il peso che il prog. ha nel voto finale.. ?

Posted by mapenzi81 on 24-04-2006 15:44:

2 - 4 punti....ho letto su qualche post vecchio...

mi domando se ci ammette all'orale anche con il prog che nn funziona a dovere

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by tandrea85 on 24-04-2006 21:08:

ma la relazione scritta dove bisogna dargliela? in via comelico nelle cassette della posta all'ingresso?

Posted by darkAntAreS on 24-04-2006 22:21:

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

si per entrambe le domande

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Posted by maynard80 on 25-04-2006 13:35:

ma mi dite dove si trova questa soluzione sul libro??

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by darkAntAreS on 25-04-2006 14:03:

non c'è la soluzione, il libro dà come come compito questo algoritmo e indica anche un piccolo suggerimento...cmq è verso la fine del capitolo sulla programmazione dinamica

edit: ho postato nell'area filez il mio progetto, lì se vuoi c'è una possibile implementazione secondo i suggerimenti del libro e altre pillole trovate qua e là in rete

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Posted by maynard80 on 25-04-2006 15:53:

darkAntAreS sei un grande, il tuo progetto è fatto davvero bene, l'ho provato con un input di circa 500, il tuo ci mette 5 secondi, il mio 120!

ma tu sei con fiorentini o goldrake?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by darkAntAreS on 25-04-2006 16:43:

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

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Posted by maynard80 on 26-04-2006 09:51:

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

ma solitamente per Fiorentini la cosa che conta di più (visto che è il corso di algoritmi e strutture dati) è il tempo di esecuzione, visto che per ogni problema il numero delle soluzioni migliori è sempre limitato

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by paolinux on 26-04-2006 11:52:

Ragazzi (Dott.House), qualcuno può postare nell'area filez l'input da 500 o giù di lì .. tanto per vedere come viaggia il mio? l'ho testato solo con pochi organismi e anche se ormai l'ho gia consegnato volevo avere un'idea del tempo di esecuzione ...

Posted by maynard80 on 26-04-2006 16:35:

ragazzi, in teoria dopodomani iniziano gli orali, ma non si sa ancora nulla, oggi abbiamo consegnato le relazioni, ma non le ha ancora prese, e il track di lettura della mail contenente il codice non mi è arrivata (quindi in teoria non l'ha letta)

boh!

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by maynard80 on 26-04-2006 16:36:

doppio post

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by tandrea85 on 27-04-2006 16:37:

novità? ho mandato un email anke al torelli per sapere se posso sostenere l'appello perke mi sono dimenticato di registrarmi sul sifa, ma nessuna risposta manco da lui..

Posted by maynard80 on 27-04-2006 16:40:

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...

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by karlost on 27-04-2006 16:56:

Tesst del progetto

Ho ricevuto una mail di Fiorentini comunicandomi che non riesce a testare il mio prog. perchè gli dà segmetation fault? ma il prog. prima di mandarlo l'ho testato con diversi input e non succedeva qto.
QUalcuno ha idea se per caso può dipendere dalla versione del gcc o del sistemaoperativo sul quale sta facendo i test.
Il mio prog. l'ho compilato con gcc4 e ho usato Ubuntu su un p4 32bit..

Che parto sto esame... :shock:

Posted by maynard80 on 28-04-2006 15:12:

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...

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??

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by darkAntAreS on 28-04-2006 18:06:

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...

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Posted by maynard80 on 28-04-2006 18:36:

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...

beh ora che è finita, mi spiegate questa soluzione ottima in n^2 ?

PS: la mia euristica trovava la soluzione giusta ed in n^2.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by darkAntAreS on 28-04-2006 21:56:

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

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

)...al max se vuoi chiarimenti sul mio codice posso darteli, per il resto posso solo ipotizzare

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Posted by maynard80 on 29-04-2006 12:06:

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 )...al max se vuoi chiarimenti sul mio codice posso darteli, per il resto posso solo ipotizzare

nel senso che ti ha mostrato una soluzione a colloquio prima della consegna?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by darkAntAreS on 29-04-2006 18:02:

nel senso che giovedì 27 sono andato lì per alcuni chiarimenti e tanto che c'ero abbiamo parlato del progetto e mi ha mostrato una soluzione partendo dalla mia e ripulendo il codice

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Posted by mapenzi81 on 03-05-2006 10:27:

Orale torelli...

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

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

Posted by Simeon on 03-05-2006 12:24:

Originally posted by mapenzi81
Orale torelli...

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

Gli algoritmi dei grafi non dovrebbe, l'unione di insiemi disgiunti invece ho sentito chiedergliela.

Posted by senai on 15-05-2006 13:37:

hahahah

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??

hahahahah

All times are GMT. The time now is 00:47.

Pages (2): [1] 2 »
Show all 152 posts from this thread on one page