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

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

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

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

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

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

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

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

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

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?

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

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

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

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