.dsy:it. - [progetto] Microcolture

Pages (11): « 1 2 3 [4] 5 6 7 8 » ... Last »
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 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.

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

Pages (11): « 1 2 3 [4] 5 6 7 8 » ... Last »
Show all 152 posts from this thread on one page