Minimizzare un percorso

Messaggioda Edo73 » 21/04/2005, 08:02

Ciao, ho scoperto questo forum per caso navigando nel web alla ricerca di una soluzione al mio problema. Dati n punti su un piano X-Y ordinarli in modo tale da minimizzare il percorso. Ad esempio date n fermate dell'autobus trovare un algoritmo che stabilisca l'ordine in modo da minimizzare il percorso, oppure per la raccolta dei rifiuti.
Credo che lo studio di questi algoritmi sia materia di "Ricerca Operativa", ed ovviamente non era nel mio corso di studi.
Grazie a tutti, ciao.
Edo73
Starting Member
Starting Member
 
Messaggio: 1 di 1
Iscritto il: 21/04/2005, 08:01

Messaggioda Elijah82 » 21/04/2005, 13:08

Più in generale, quando non tutti i punti (nodi) sono collegati fra loro e il costo per andare da un nodo a un altro è un qualunque numero positivo e non necessariamente la distanza geometrica sul piano, questo è il problema del commesso viaggiatore. Non ho studiato l'algoritmo all'università, ma prova a cercare su Google "commesso viaggiatore"
Elijah82
Junior Member
Junior Member
 
Messaggio: 181 di 214
Iscritto il: 04/03/2005, 14:31
Località: Italy

Messaggioda Elijah82 » 21/04/2005, 13:15

http://www.dima.unige.it/~sideri/did/ro/TLC02/TSP24.pdf
qui dice che è un problema per cui non esiste un algoritmo esatto... in effetti ora che ci penso l'avevo letto da qualche parte! comunque cerca le parole problema commesso viaggiatore, o travelling salesman in inglese
Elijah82
Junior Member
Junior Member
 
Messaggio: 182 di 214
Iscritto il: 04/03/2005, 14:31
Località: Italy


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite