xeon

User info:

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

Post actions:

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

mapenzi81

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:

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

xeon

User info:

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

Post actions:

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

Gehur

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:

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

Last edited by Gehur on 06-04-2006 at 09:44

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:

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

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:

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 !

Gehur

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:

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

mapenzi81

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:

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

tandrea85

User info:

Registered: Sep 2004
Posts: 95 (0.01 al dì)
Location:
Corso: informatica
Anno: 1
Time Online: 18:21:48 [...]
Status: Offline

Post actions:

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?

mapenzi81

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:

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

Gehur

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:

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

Last edited by Gehur on 06-04-2006 at 13:11

tandrea85

User info:

Registered: Sep 2004
Posts: 95 (0.01 al dì)
Location:
Corso: informatica
Anno: 1
Time Online: 18:21:48 [...]
Status: Offline

Post actions:

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?

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:

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

xeon

User info:

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

Post actions:

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

Gehur

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:

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