Problema del commesso viaggiatore metrico (TSP metrico)

Catalogo dei problemi di ottimizzazione combinatoria · Problemi di routing · Catalogo (PDF)

Definizione 1: Problema del commesso viaggiatore metrico

Un'istanza del TSP è metrica se le sue distanze soddisfano la disuguaglianza triangolare

\[ d_{ij} \le d_{ik} + d_{kj} \qquad \text{per ogni terna di città distinte } i,j,k \in \mathscr{V}. \]

Il problema del commesso viaggiatore metrico (TSP metrico) è il TSP ristretto alle istanze metriche.

Che cosa fa il corso su questo problema

Tecnica	Dove
Definizione	Cap. 6 «Problemi di routing»
Formulazioni	Cap. 13 «Formulazioni dei problemi di routing»
Euristiche	Cap. 30 «Euristiche costruttive»
Approssimazione	Cap. 39 «TSP: il caso generale e il caso metrico»
Esercizi	Esercizio 6.4; Cap. 39 (2 esercizi)