Visita tutte le città. Torna alla partenza. Fai la strada più corta.
🏭Parti dal magazzino (Partenza)
🖱️Click sulle case 🏠 in ordine → costruisci il giro delle consegne
↩️Click sull'ultima città → la togli
🎯Vince la rotta più corta
🏆Poi sfida gli algoritmi!
ℹ️ Perché è così difficile?
Devi visitare tutte le città una sola volta e tornare al punto di
partenza, facendo la strada più corta possibile. Sembra facile, ma
i percorsi possibili esplodono: con 10 città sono già 181.440, con 20
città più di 60 milioni di miliardi.
È lo stesso tipo di problema che pianifica i giri dei corrieri,
i percorsi dei trapani che forano i circuiti elettronici, o
l'ordine in cui un telescopio osserva le stelle.
Curiosità matematica: si chiama problema del commesso viaggiatore
(Travelling Salesman Problem, TSP) — ogni città è un nodo, ogni strada un
arco con la sua lunghezza.
Trovare la rotta più corta è NP-difficile. Con poche città un
algoritmo esatto trova sempre l'ottimo; con tante città diventa
impossibile, e si usano euristiche e metaeuristiche —
provale qui a destra!