Commesso viaggiatore

[-Ivan-]

Devo risolvere il problema del commesso viaggiatore per l'università.
Ho letto su internet il problema ma non mi è chiara una cosa:
le città sono ognuna collegata con tutte le altre città? Cioè da ogni città esiste un percorso per arrivare ad un'altra qualsiasi? Oppure ci possono essere dei vincoli legati al grafo iniziale che magari non prevede che la città A sia collegata direttamente con la città Z?
Inoltre esiste il vincolo di dover passare da ogni città una sola volta?

probabilmente avrò altre domande ma mi verrano in mente mentre programmo.
Intanto grazie a chi mi risponderà.

[rdefalco]

Qui
http://www.dia.unisa.it/professori/uv/ASD/l22.pdf
c'è la lezione di un mio prof di Università sugli algoritmi fra cui il problema del commesso viaggiatore. Parla di tutti i vertici collegati due a due fra loro e della diseguaglianza triangolare.

[-Ivan-]

Vorrei chiedervi una spiegazione su questo problema perchè non riesco a capirlo fino in fondo.
Mi risulta un po' complicato spiegarvi cosa non mi è chiaro con i grafi quindi faccio un esempio con delle città italiane.

Io sono di Milano, devo fare un viaggio (al termine del viaggio dovrò quindi tornare a Milano), devo andare a Monza, Rimini, Napoli, Palermo.
Se io faccio:
Milano->Monza Monza->Rimini Rimini->Napoli Napoli->Palermo Palermo->Milano
non è questa una soluzione ottima???

Cioè io in questo caso vado sempre nella città che mi è più vicina in quel momento, non riesco a capire perchè andare sempre nella città più vicina non sia una soluzione del problema, tanto alla fine la distanza tra le città è sempre quella e tu la devi percorrerre tutta in tutti i casi, la allunghi solamente se sei in un punto e da li vai in una città che non è la più vicina per poi andare in una città lontana da quella di arrivo ma vicina a quella in cui eri in precedenza (è un po' complicato spiegarlo) cioè facendo ad esempio:

Milano->Napoli Napoli->Rimini Rimini->Monza ecc.

Non è così? Cos'è che non ho capito del problema? Ho letto qualche soluzione su intenret capendoci molto poco ed è molto complicata la faccenda, mi sono perso qualche pezzo mi sa.

[franksisca]

ogni strada ha il suo costo, e di solito si cerca di minimizzare il costo totale. quindi la tua soluzione è una souzione, ma magari non è la soluizione ottima, perchè magari puoi trovare un èpercorso che ti fà fare qualche KM in meno.
e poi tutte e città sono collegate con tutte le città, se le colleghi a 2 a 2, è un caso particolare, e mi sembra che non sia la stesssa cosa, ora non ne sono sicuro, ma se trovo qualcosa d+ preciso, vi faccio sapere.

[-Ivan-]

ogni strada ha il suo costo, e di solito si cerca di minimizzare il costo totale. quindi la tua soluzione è una souzione, ma magari non è la soluizione ottima, perchè magari puoi trovare un èpercorso che ti fà fare qualche KM in meno.
e poi tutte e città sono collegate con tutte le città, se le colleghi a 2 a 2, è un caso particolare, e mi sembra che non sia la stesssa cosa, ora non ne sono sicuro, ma se trovo qualcosa d+ preciso, vi faccio sapere.

Secondo il mio ragionamente se tu devi andare in tot città andando da quella di partenza a quella più vicina fino alla più lontana e poi tornando non puoi metterci di più che facendo qualsiasi altra strada ( o almeno non molto di più ed anche le soluzioni che si trovano dicono che non calcolano esattamente il percorso ottimo ma uno che gli si avvicina). Questo ragionamento è sbagliato e lo so perchè ho visto le soluzioni al problema su internet e sono molto complicate quindi vorrei consocere i casi in cui questo ragionamento porta a conclusioni sbagliate così da mettermi il cuore in pace e studiare le soluzioni di cui ho letto.

[fuocofatuo]

Il problema del commesso viaggiatore, nella sua accezione più generale, non fa alcuna supposizione in merito al grafo su cui dovrà lavorare. In altre parole, non si assume che tutte le città siano collegate, e non si assume che il costo di un viaggio dipenda dalla distanza "in linea d'aria", per intenderci.
Se si lavora in un grafo completo in cui vale la disuguaglianza triangolare, il problema viene spesso chiamato "TSP metrico". Questo ha il vantaggio, rispetto al primo, di essere approssimabile con fattore 1,5, mentre il primo non è approssimabile per nessun fattore. Questo significa che, per il primo, possiamo sviluppare algoritmi e euristiche di qualsiasi tipo, ma non saremo mai certi di quanto queste saranno efficienti. Al contrario, per il TSP metrico, è facile trovare una soluzione "abbastanza buona", ovvero una soluzione per la quale possiamo garantire che il suo costo sarà inferiore a 1,5 volte il costo della soluzione ottima.

L'euristica proposta da te è una delle più intuitive, nonchè la prima ad essere presentata ad ogni corso, ma fallisce in molti casi. Pensa a questo caso:

4----1
-------------------------------------------------------5
3----2

L'algoritmo che proponi tu, partendo da uno, andrebbe subito a 2 (immagina che sia più vicino di 4, 3, e ovviamente 5), poi a 3, 4, e quindi 5 e di nuovo a 1.
La soluzione ottima, invece, ha come percorso 5, 2, 3, 4 e 1.

[-Ivan-]

Il problema del commesso viaggiatore, nella sua accezione più generale, non fa alcuna supposizione in merito al grafo su cui dovrà lavorare. In altre parole, non si assume che tutte le città siano collegate, e non si assume che il costo di un viaggio dipenda dalla distanza "in linea d'aria", per intenderci.
Se si lavora in un grafo completo in cui vale la disuguaglianza triangolare, il problema viene spesso chiamato "TSP metrico". Questo ha il vantaggio, rispetto al primo, di essere approssimabile con fattore 1,5, mentre il primo non è approssimabile per nessun fattore. Questo significa che, per il primo, possiamo sviluppare algoritmi e euristiche di qualsiasi tipo, ma non saremo mai certi di quanto queste saranno efficienti. Al contrario, per il TSP metrico, è facile trovare una soluzione "abbastanza buona", ovvero una soluzione per la quale possiamo garantire che il suo costo sarà inferiore a 1,5 volte il costo della soluzione ottima.

L'euristica proposta da te è una delle più intuitive, nonchè la prima ad essere presentata ad ogni corso, ma fallisce in molti casi. Pensa a questo caso:

4----1
-------------------------------------------------------5
3----2

L'algoritmo che proponi tu, partendo da uno, andrebbe subito a 2 (immagina che sia più vicino di 4, 3, e ovviamente 5), poi a 3, 4, e quindi 5 e di nuovo a 1.
La soluzione ottima, invece, ha come percorso 5, 2, 3, 4 e 1.


Si facendo un po' di prove effettivamente è abbastanza banale che la soluzione che avevo in mente fosse una discreta minchiata :D .
Il problema del commesso viaggiatore, nella sua accezione più generale, non fa alcuna supposizione in merito al grafo su cui dovrà lavorare. In altre parole, non si assume che tutte le città siano collegate

Questa cosa mi ha sconvolto perchè fino ad ora pensavo di si e sto pensando a un algoritmo dando per scontato che tutte siano collegate.

Per ora mi sono messo a smanettare con le matrici sperando di capire qualcosa di più.
Tra l'altro io non so nemmeno bene quale sia la consegna che ci ha dato il prof, so solo che dobbiamo implementare un algoritmo per il tsp e che lo dobbiamo fare senza cercare codice su internet, penso che gli basti una soluzione anche molto approssimativa.