Un commesso viaggiatore deve visitare un insieme di città, tornando nel punto di partenza e senza passare due volte per la stessa città (ovvero facendo un tour).
Le distanze tra le coppie di città, in chilometri, sono date dai seguenti termini:
- arco(C1,C2,10)
- arco(C1,C3,4)
- arco(C1,C4,9)
- arco(C2,C3,6)
- arco(C2,C4,5)
- arco(C3,C4,4)
che hanno la struttura arco(<nome di città>,<nome di città>,<distanza>).
Il commesso parte dalla città C1; disegnare il grafo delle città e trovare la lunghezza, in chilometri del tour più corto.
DISCUSSIONE
Il grafo corrispondente
Tutti i possibili tour per C1
- [C1,C2,C3,C4,C1], L=29
- [C1,C2,C4,C3,C1], L=23
- [C1,C3,C2,C4,C1], L=24
- [C1,C3,C4,C2,C1], L=23
- [C1,C4,C2,C3,C1], L=24
- [C1,C4,C3,C2,C1], L=29
anche graficamente
Il tour più corto
Risposta
L=23