Discussione:Problema del commesso viaggiatore

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

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)

Siete sicuri che "Non esistono algoritmi efficienti per la risoluzione del TSP, l'unico metodo di risoluzione è rappresentato dall'enumerazione totale" ?

Sono un principiante in materia e quindi non voglio modificare direttamente la voce, ma sto seguendo un corso online di algoritmi in cui ci hanno fatto studiare un algoritmo di programmazione lineare che ha un tempo di esecuzione O(n^2 2^n), esponenziale ma molto migliore del tempo fattoriale O(n!) della forza bruta (n = numero dei vertici di un grafo completo). — Questo commento senza la firma utente è stato inserito da 151.41.21.175 (discussioni · contributi).

sì, hai ragione, "basta" (si fa per dire) un ordine esponenziale e non fattoriale. La voce puoi modificarla, ma dovresti aggiungere un riferimento esterno all'algoritmo (scrivendo <ref>[http://sito.con.l.algoritmo Titolo dell'algoritmo]</ref> -- .mau. ✉ 11:52, 21 gen 2013 (CET)

Collegamenti esterni modificati

Gentili utenti,

ho appena modificato 1 collegamento esterno sulla pagina Problema del commesso viaggiatore. Per cortesia controllate la mia modifica. Se avete qualche domanda o se fosse necessario far sì che il bot ignori i link o l'intera pagina, date un'occhiata a queste FAQ. Ho effettuato le seguenti modifiche:

• Aggiunta del link all'archivio https://web.archive.org/web/20170325123309/http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ per http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

Fate riferimento alle FAQ per informazioni su come correggere gli errori del bot.

Saluti.—InternetArchiveBot (Segnala un errore) 00:08, 18 nov 2019 (CET)

Simulated annealing

In questa voce si legge la seguente affermazione:

Per scopi pratici, il metodo della ricottura simulata (Simulated annealing) ha effettivamente risolto il TSP.

Non sono un esperto in materia, sono solo uno studente, ma non mi torna.

Mi risulta che il TSP sia risolvibile, anche se con tempi esponenziali. La frase in questione andrebbe dettagliata, specificando:

• con che tempi risolve TSP
• con che grado di approssimazione risolve TSP
• risolve una determinata istanza di TSP

Grazie, --Luca.favorido (msg) 22:20, 25 apr 2021 (CEST)

per quello che ricordo io (il simulated annealing l'ho visto più di trent'anni fa...) la tecnica può solo dare un'alta probabilità di soluzione, ma non la certezza. Il "raffreddamento" può sempre rimanere bloccato in un minimo locale. -- .mau. ✉ 11:10, 26 apr 2021 (CEST)

Inutile anglofilia

A cosa serve in voce in wikipedia.it la frase: "Viene spesso indicato con il suo nome inglese, traveling salesman problem o traveling salesperson problem, in acronimo TSP"?

A questo punto allora, inoltriamo la pagina direttamente a https://en.wikipedia.org/wiki/Travelling_salesman_problem

Cordiali saluti,

Isidoro Ghezzi. --188.153.189.64 (msg) 00:02, 29 nov 2023 (CET)

Qui non "inoltriamo". Semplicemente e correttamente, ove il termine in lingua inglese (o altra lingua che sia) risulti quello utilizzato per designare qualcosa nell'ambito del linguaggio tecnico di settore o in quello corrente lo si riporta a beneficio della completezza e comprensibilità.--TrinacrianGolem (msg) 01:05, 29 nov 2023 (CET)