Discussione:Problema del commesso viaggiatore
Da Wikipedia, l'enciclopedia libera.
|
||
"una ed una sola volta": è intrinseco. Ovviamente se si vuole trovare il percorso minimo questo non passerà due volte per lo stesso punto. Se il percorso fosse ABCBA ovviamente sarebbe più corto ABCA...
- Vero. Però non l'ho modificato perché così è più chiaro. È presente anche nella versione inglese (what is the cheapest round-trip route that visits each city once) --Jack (sa vût?) 01:24, 31 dic 2005 (CET)
- Però se cerchi anche online su altre fonti (ad esempio universitarie) in genere non viene detto. Perchè il fatto che passi due volte o meno per un certo punto (che per altri tipi di problemi dell'informatica è fondamentale) in questo caso non è di rilievo. Voglio dire: visto che in genere si usano algoritmi greedy, questi possono dare anche risultati in cui il percorso passa due volte per lo stesso punto, ma questo non invalida la soluzione. Solitamente se si capita in una soluzione del è facile ottimizzarla togliendo uno dei due passi. Tuttavia se è definito come "ciclo hamiltoniano di peso minimo" questo contraddice la mia ipotesi visto che i cicli hamiltoniani sottointendono già che si passi una e una sola volta per ogni vertice del grafo... boh :)
- mi hai messo la pulce nell'orecchio e sono andato a vedere sul Cormen - Introduction to Algorithms (2a ed). Cito testualmente: [...] visiting each city exactly once and finishing at the city he starts from. È nella sezione 34.5.4 The traveling-salesman problem. --Jack (sa vût?) 02:15, 31 dic 2005 (CET)
- Però se cerchi anche online su altre fonti (ad esempio universitarie) in genere non viene detto. Perchè il fatto che passi due volte o meno per un certo punto (che per altri tipi di problemi dell'informatica è fondamentale) in questo caso non è di rilievo. Voglio dire: visto che in genere si usano algoritmi greedy, questi possono dare anche risultati in cui il percorso passa due volte per lo stesso punto, ma questo non invalida la soluzione. Solitamente se si capita in una soluzione del è facile ottimizzarla togliendo uno dei due passi. Tuttavia se è definito come "ciclo hamiltoniano di peso minimo" questo contraddice la mia ipotesi visto che i cicli hamiltoniani sottointendono già che si passi una e una sola volta per ogni vertice del grafo... boh :)
[modifica] Traduzione da en
Ho avuto qualche problema in questo passo:
- "Un esempio classico è la costruzione di circuiti stampati, nella pianificazione del percorso del trapano per creare i buchi nella piastra. Nelle applicazioni di foratura o di rifinitura automatica eseguite da robot, le "città" sono pezzi da rifinire o buchi (di varie dimensioni) da praticare, e il "costo di viaggio" include i necessari tempi morti."
perchè nell'articolo inglese vengono usati termini propri della robotica e dell'elettronica che non sono sicuro di aver reso bene:
- "A classic example is in printed circuit manufacturing: scheduling of a route of the drill machine to drill holes in a PCB. In robotic machining or drilling applications, the "cities" are parts to machine or holes (of different sizes) to drill, and the "cost of travel" includes time for retooling the robot (single machine job sequencing problem)."
Se qualcuno che se ne intende vuol metterci mano, toglierebbe un po' di approssimazione. --Jack (sa vût?) 01:32, 31 dic 2005 (CET)
