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

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

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)

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

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

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?

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

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

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

Originally posted by mapenzi81
molto tra le righe... :)

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

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

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?

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

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) :P

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

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

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

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

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

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?

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;
}

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

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.

Originally posted by Polsy

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

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;

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

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

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!

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

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);

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

Originally posted by maynard80
puoi delucidarci su come hai fatto?

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

code:

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

code:

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

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