.dsy:it. - [progetto] Microcolture

Calendar

Members

Faq

Logout

.dsy:it. : Powered by vBulletin version 2.3.1

.dsy:it. > Didattica > Corsi A - F > Algoritmi e strutture dati > [progetto] Microcolture

Pages (11): « 1 2 3 [4] 5 6 7 8 » ... Last »

Last Thread Next Thread

Author

Thread Expand all | Contract all

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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)

06-04-2006 21:34

Click here to Send Polsy a Private Message

mapenzi81

dsy developer

User info:

Registered: Feb 2005
Posts: 233 (0.03 al dì)
Location: Milano
Corso: Informatica
Anno: 3.....456789....
Time Online: 6 Days, 1:18:40 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

06-04-2006 21:35

Click here to Send mapenzi81 a Private Message

Gehur

.grande:maestro.

User info:

Registered: Apr 2006
Posts: 519 (0.08 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 3 Days, 0:41:42 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

06-04-2006 21:41

Click here to Send Gehur a Private Message

maynard80

.novellino.

User info:

Registered: Jul 2007
Posts: 3 (0.00 al dì)
Location: Milano (e non interland, tendo a precisare)
Corso: informatica
Anno: SESTO
Time Online: 12 Days, 14:28:38 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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 !

07-04-2006 14:38

Click here to Send maynard80 a Private Message

mapenzi81

dsy developer

User info:

Registered: Feb 2005
Posts: 233 (0.03 al dì)
Location: Milano
Corso: Informatica
Anno: 3.....456789....
Time Online: 6 Days, 1:18:40 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

07-04-2006 14:41

maynard80

.novellino.

Post actions:

Edit | Report | IP: Logged

essendo su Z col cavolo che sono positivi.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

07-04-2006 15:23

mapenzi81

dsy developer

User info:

Registered: Feb 2005
Posts: 233 (0.03 al dì)
Location: Milano
Corso: Informatica
Anno: 3.....456789....
Time Online: 6 Days, 1:18:40 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

08-04-2006 18:04

maynard80

.novellino.

Post actions:

Edit | Report | IP: Logged

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 !

Last edited by maynard80 on 08-04-2006 at 19:33

08-04-2006 19:28

jonnypee

.fedelissimo.

User info:

Registered: Feb 2006
Posts: 42 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 13:24:20 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

13-04-2006 09:36

Click here to Send jonnypee a Private Message

lino

.precettore.

User info:

Registered: Jun 2003
Posts: 96 (0.01 al dì)
Location: lodi
Corso: informatica
Anno: terzo
Time Online: 2 Days, 1:25:20 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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?

13-04-2006 10:51

Click here to Send lino a Private Message

maynard80

.novellino.

Post actions:

Edit | Report | IP: Logged

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 !

13-04-2006 13:47

KiVan

.always:banned.

User info:

Registered: Nov 2001
Posts: 128 (0.02 al dì)
Location: Magenta
Corso: Omg! Laureato in Informatica
Anno: è un problema NP completo
Time Online: 1 Day, 6:25:47 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

13-04-2006 15:25

Click here to Send KiVan a Private Message

maynard80

.novellino.

Post actions:

Edit | Report | IP: Logged

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 !

13-04-2006 23:14

logan.x

.amico.

User info:

Registered: Jul 2003
Posts: 36 (0.00 al dì)
Location: milano
Corso: informatica triennale
Anno: 2° fuori corso
Time Online: 19:13:22 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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?

14-04-2006 13:58

Click here to Send logan.x a Private Message

xeon

.novellino.

User info:

Registered: Apr 2006
Posts: 7 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 1:01:48 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.

14-04-2006 19:32