Ottimizzazione Combinatoria 2005/2006 Homework 2
Cognome __________________
Nome __________________
Matricola __________________
Esercizio 1
La seguente matrice è una matrice delle distanze di un’istanza del problema del Commesso Viaggiatore.
1 2 3 4 5 6 7
1 - 12 42 7 10 11 21
2 12 - 31 4 8 27 7
3 42 31 - 27 6 5 15
4 7 4 27 - 14 33 23
5 10 8 6 14 - 12 32
6 11 27 5 33 12 - 14
7 21 7 15 23 32 14 -
Calcolare
1. Il valore del rilassamento che si ottiene determinando l’1-albero di costo minimo 2. Una soluzione euristica S ottenuta tramite l’algoritmo di Christofides.
3. Una soluzione euristica S ottenuta tramite l’algoritmo Double Tree.
4. Una soluzione euristica S ottenuta tramite l’algoritmo Farthest Insertion 5. Una soluzione euristica S ottenuta tramite l’algoritmo Nearest Neighbor.
Esercizio 2
Un’azienda di autotrasporti effettua un giro di consegne nelle seguenti città europee:
Roma Atene Madrid Bruxelles Belgrado Parigi Berlino
- 1460 2040 1580 1410 1500 1400 Roma - 3470 3010 1280 2729 2580 Atene - 1550 1730 1260 2340 Madrid - 1730 590 810 Bruxelles
- 1040 1310 Belgrado
- 1080 Parigi
- Berlino
Sapendo che:
1. Ogni elemento (i, j) della matrice rappresenta la distanza in km tra le città i e j;
2. L’azienda effettua il giro con un automezzo condotto da un unico autista che può guidare consecutivamente per un massimo di 1200 km;
3. Il giro di consegna parte da Roma e termina a Roma.
Provate a minimizzare il numero di soste spiegando le scelte algoritmiche effettuate.
