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