Grafi e retiSalesman

Finora abbiamo ignorato la distanza fra le città. Nella vita reale, tuttavia, questa è una considerazione molto importante: non vogliamo trovare qualsiasi percorso, ma il percorso più breve. Questo è chiamato Problema del commesso viaggiatore. Non si applica solo nei trasporti e nella logistica, ma anche quando si posizionano i transistor sui microchip, per rendere i computer più veloci, o quando si analizza la struttura del DNA.

Un metodo semplice sarebbe quello di provare tutti i percorsi possibili, trovare la lunghezza di ciascuno e quindi scegliere quello più breve. Tuttavia abbiamo appena dimostrato che, anche con solo ${tsn2} città ci sono ${tsn2}! = ${factorial(tsn2)} possibili percorsi. Una volta che hai centinaia o migliaia di vertici, provare tutti i possibili percorsi diventa impossibile, anche usando computer potenti.