A chi vuole girare il mondo
ho 18 anni! **** pero non ho ancora la patente...
cmq quando ce l'avro potrà essermi utile sapere come raggiungere n posti nel modo più veloce possibile no?
sinceramente sta cosa funziona più per gli aerei... e allora magari quando vorrò girare il mondo potrà essermi utile
sapere come volare in n città pagando meno...(di solito i prezzi dei biglietti sono a km)
beh qualcuno provi a dirmi il trucco per trovare sempre la strada più breve che unisce n punti nello spazio.
ciao
ah cmq è figo scrivere qui: è la mia prima volta!
cmq quando ce l'avro potrà essermi utile sapere come raggiungere n posti nel modo più veloce possibile no?
sinceramente sta cosa funziona più per gli aerei... e allora magari quando vorrò girare il mondo potrà essermi utile
sapere come volare in n città pagando meno...(di solito i prezzi dei biglietti sono a km)
beh qualcuno provi a dirmi il trucco per trovare sempre la strada più breve che unisce n punti nello spazio.
ciao
ah cmq è figo scrivere qui: è la mia prima volta!
Risposte
No il TSP non è legato in modo particolare alla geometria.
Infatti il problema è questo. Dati $n$ punti e una matrice:
$ A = [ d_{ij} ] $
Dove $d_{ij}$ rappresenta la distanza fra il punto $i$ e il punto $j$ trovare il cammino di lunghezza minima che percorre una volta sola ciascun punto e ritorna al punto di partenza.
Data l'arbitrarietà della matrice $A$ uno può far saltare fuori situazioni di qualunque tipo anche situazioni non geometricamente sensate (ad esempio quando la distanza fra $i$ e $j$ è diversa dalla distanza fra $j$ e $i$...)
Questo problema è molto difficile da risolvere visto che non si conoscono algoritmi per risolverlo in tempo polinomiale rispetto a $n$ (e addirittura si congettura che non ne esistano), ma esistono algoritmi polinomiali in grado di trovare una buona soluzione in tempi brevi (ma non la migliore). Quelli che ho linkato io funzionano solo nel caso euclideo (tutti i punti su un unico piano)....
Infatti il problema è questo. Dati $n$ punti e una matrice:
$ A = [ d_{ij} ] $
Dove $d_{ij}$ rappresenta la distanza fra il punto $i$ e il punto $j$ trovare il cammino di lunghezza minima che percorre una volta sola ciascun punto e ritorna al punto di partenza.
Data l'arbitrarietà della matrice $A$ uno può far saltare fuori situazioni di qualunque tipo anche situazioni non geometricamente sensate (ad esempio quando la distanza fra $i$ e $j$ è diversa dalla distanza fra $j$ e $i$...)
Questo problema è molto difficile da risolvere visto che non si conoscono algoritmi per risolverlo in tempo polinomiale rispetto a $n$ (e addirittura si congettura che non ne esistano), ma esistono algoritmi polinomiali in grado di trovare una buona soluzione in tempi brevi (ma non la migliore). Quelli che ho linkato io funzionano solo nel caso euclideo (tutti i punti su un unico piano)....
Scusate l'ignoranza, questo quesito è molto interessante, ma vorrei capirlo meglio.
Ditemi se va bene...
In poche parole stiamo cercando di trovare la distanza minore posta tra due punti di una superficie gaussiana, cioè a sfera?
Ditemi se va bene...
In poche parole stiamo cercando di trovare la distanza minore posta tra due punti di una superficie gaussiana, cioè a sfera?
beh interessante
La formulazione PLI e' semplicissima (la capirebbe anche un bambino). Solo che l'algoritmo risolutivo ha complessita esponenziale (se non ti accontenti di una soluzione "approssimata").
Se parli di citta' i punti sono su una superficie e quindi il problema e' piano (pur di passare alle coordinate gaussine).
E in ogni caso se il metodo fosse cosi facilmente deducibile e applicabile non ci sarebbe la teoria dell'NP-completezza visto che il TSP e' un problema NP completo. Quindi se si trovasse un algoritmo polinomiale per risolverlo si avrebbe P=NP. (quindi se la trovi diventi un uomo ricco e famoso)
Al limite puoi inventarti qualche algoritmo per giungere a una buona soluzione approssimata. Ne esistono tantissimi, alcuni sono quelli del PDF, ma ce ne sono molti altri. Ad esempio avevo letto di un algoritmo che sfruttava il comportamento di una colonia virtuale di formiche per tracciare un percorso.
Se parli di citta' i punti sono su una superficie e quindi il problema e' piano (pur di passare alle coordinate gaussine).
E in ogni caso se il metodo fosse cosi facilmente deducibile e applicabile non ci sarebbe la teoria dell'NP-completezza visto che il TSP e' un problema NP completo. Quindi se si trovasse un algoritmo polinomiale per risolverlo si avrebbe P=NP. (quindi se la trovi diventi un uomo ricco e famoso)
Al limite puoi inventarti qualche algoritmo per giungere a una buona soluzione approssimata. Ne esistono tantissimi, alcuni sono quelli del PDF, ma ce ne sono molti altri. Ad esempio avevo letto di un algoritmo che sfruttava il comportamento di una colonia virtuale di formiche per tracciare un percorso.
non mi piace questa risposta: anche se la complessità è esponenziale la deduzione del metodo penso sia molto semplice
e facilmente applicabile...
e la soluzione non penso sia unire i punti come dici... anche perchè non siamo sul piano ma nello spazio
e facilmente applicabile...
e la soluzione non penso sia unire i punti come dici... anche perchè non siamo sul piano ma nello spazio
Si ci sono metodi piu' matematici (nel senso che arrivano alla soluzione ottima) per farlo (ad esempio la PLI) ma hanno complessita' esponenziale...
non penso sia cosi... anzi secondo me c'è un metodo molto matematico per farlo
Beh gli algoritmi nel PDF sono euristici quindi non e' che ci sia dentro molta matematica....
Se dovessi farlo "a mano" cercherei di raccordare i punti in una specie di circonferenza distorta....
Se dovessi farlo "a mano" cercherei di raccordare i punti in una specie di circonferenza distorta....
Tu personalmente e anche non matematicamente come faresti
Il TSP (traveling salesman problem) e' un problema NP-Difficile visto che la sua versione di riconoscimento e' NP-completa (vd. altro topic) esistono pero' una serie di algoritmi polinomiali che trovano soluzioni approssimate abb. buone.
Guarda:
http://www1.mate.polimi.it/~errico/mate ... chetsp.pdf
Guarda:
http://www1.mate.polimi.it/~errico/mate ... chetsp.pdf
C'era un di solito per i biglietti aerei... se proprio si vuole risparmiare conviene prenotare con largo (anni) anticipo o partire a sorpresa (last minute)...
però non mi avete detto come fareste in modo pratico a collegare n punti nello spazio nel modo più breve!
però non mi avete detto come fareste in modo pratico a collegare n punti nello spazio nel modo più breve!
Ti rispondo in un modo non matematico.
Abbandona la tua certezza che i biglietti aerei siano proporzionali ai km!
Esempio:
Milano-Amsterdam-Minneapolis e ritorno 900$
Amsterdam-Minneapolis (stesso volo di cui sopra) 3300$
Senza parole....
Abbandona la tua certezza che i biglietti aerei siano proporzionali ai km!
Esempio:
Milano-Amsterdam-Minneapolis e ritorno 900$
Amsterdam-Minneapolis (stesso volo di cui sopra) 3300$
Senza parole....
"miik.bor":
ho 18 anni! **** pero non ho ancora la patente...
cmq quando ce l'avro potrà essermi utile sapere come raggiungere n posti nel modo più veloce possibile no?
sinceramente sta cosa funziona più per gli aerei... e allora magari quando vorrò girare il mondo potrà essermi utile
sapere come volare in n città pagando meno...(di solito i prezzi dei biglietti sono a km)
beh qualcuno provi a dirmi il trucco per trovare sempre la strada più breve che unisce n punti nello spazio.
ciao
ah cmq è figo scrivere qui: è la mia prima volta!
Hai mascherato un tipico algoritmo non polinomiale, detto problema del commmesso viaggiatore.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo