Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Problema TSP
Forum - C/C++ - Problema TSP

Avatar
nabla (Normal User)
Newbie


Messaggi: 2
Iscritto: 03/05/2009

Segnala al moderatore
Postato alle 13:28
Domenica, 03/05/2009
Ciao a tutti.............
sono nuovo di questo forum.....
programmo in c a livello scolastico e uso linux da circa tre anni.........

Vorrei chiedere un parere circa un progettino che devo svolgere....

Questo progetto richiede di creare un algoritmo per risolvere un problema TSP o problema del commesso viaggiatore. Tale algoritmo prendendo un insieme di archi (vie cittadine) deve effettuare la scelta migliore, tra tali vie, per portare a termine entro un periodo di tempo prefissato, la consegna di ipotetici pacchetti. Ogni arco non ha la stessa priorità ma è contrassegnato da un flag, 0=priorità bassa, 1=priorità alta. L'obbiettivo è quello di trovare il percorso migliore per fare tutte le consegne coperte dagli archi con priorità 1 e farne il più possibile quelle con priorità 0.

******************************
Dati:
******************************

Il programma deve prendere in ingresso tre file da linea di comando:
  -un file di testo dove ci sono gli indirizzi delle vie della città con relativi flag;
  -due file dove devono essere stampati i percorsi effettuati dal commesso viaggiatore
   e gli archi non toccati.


Sono state fornite le funzioni per il calcolo del tempo e della distanza tra due nodi, dove tali funzioni tengono conto anche degli orari di punta del traffico cittadino.  


Ora arrivo al punto...... :-)
Vorrei chiedere un parere circa la struttura dati da utilizzare...per svolgere tale algoritmo...
Secondo me, dato che si tratta di un insieme di archi, e su ogni nodo si può passare al più due volte, avevo in mente di utilizzare un grafo orientato pesato con matrice di adiacenza, in modo che all'inizio si effettui una scansione di tutti gli archi assegnandoli il relativo peso, e poi successivamente inserirli nella matrice.

Secondo voi tale struttura dati può andare bene, oppure è inutile per un esercizio di questo tipo?

Grazie in anticipo per la risposta.....

CIAOOOO

PS:
Spero che oltre a chiedere ogni tanto qualche consiglio possa essere anche d'aiuto ;-)

PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 21:05
Domenica, 03/05/2009
Secondo me sarebbe più opportuna una matrice di incidenza.
Con quella di adiacenza è più semplice sapere se da un nodo ne puoi raggiungere un altro ma non sai poi per quale arco sei passato.
Invece con una matrice di incidenza ti becchi tutti gli archi uscenti da un nodo e scopri poi in che nodo entrano.

Come algoritmo per l'esercizio ti consiglierei Dijkstra per trovare i cammini minimi :k:
Per dijkstra guarda qui http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra

PM Quote
Avatar
nabla (Normal User)
Newbie


Messaggi: 2
Iscritto: 03/05/2009

Segnala al moderatore
Postato alle 15:54
Mercoledì, 06/05/2009
Testo quotato

Postato originariamente da andrea.b89:

Secondo me sarebbe più opportuna una matrice di incidenza.
Con quella di adiacenza è più semplice sapere se da un nodo ne puoi raggiungere un altro ma non sai poi per quale arco sei passato.
Invece con una matrice di incidenza ti becchi tutti gli archi uscenti da un nodo e scopri poi in che nodo entrano.

Come algoritmo per l'esercizio ti consiglierei Dijkstra per trovare i cammini minimi :k:
Per dijkstra guarda qui http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra



CIAO Grazie per la risposta....effettivamente sembra migliore rispetto la soluzione da me indicata.....Ancora grazie....


CIAO :-)

PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 17:00
Mercoledì, 06/05/2009
Prego :k:

PM Quote