Grafer och nätverkSalesman

Hittills har vi ignorerat det faktum att vissa städer kan vara längre från varandra än andra. I verkliga livet är detta emellertid ett mycket viktigt övervägande: vi vill inte bara hitta någon väg utan vi vill hitta den kortaste vägen. Detta kallas Travelling Salesman Problem . Det måste lösas inte bara inom transport och logistik, utan också när man placerar transistorer på mikrochips, för att göra snabbare datorer eller när man analyserar DNA- strukturen.

En enkel metod skulle vara att prova alla möjliga vägar, hitta längden på varje och sedan välja den kortaste. Men vi har bara visat det, även med bara ${tsn2} städer finns ${tsn2} ! = ${factorial(tsn2)} möjliga vägar. När du väl har hundratals eller tusentals vertikaler blir det omöjligt att prova alla möjliga vägar, även med kraftfulla datorer.