Graphen und NetzwerkeSalesman

Bisher haben wir die Tatsache ignoriert, dass einige Städte weiter voneinander entfernt sein könnten als andere. Im wirklichen Leben ist dies jedoch eine sehr wichtige Überlegung: Wir wollen nicht nur einen Weg finden, sondern den kürzesten. Man nennt dies das Problem des Handlungsreisenden. Es muss nicht nur im Transport- und Logistikbereich gelöst werden, sondern auch bei der Positionierung von Transistoren auf Mikrochips, um immer schnellere Computer herzustellen, oder bei der Analyse der Struktur der DNA.

Eine einfache Methode wäre es, alle möglichen Wege auszuprobieren, die Länge jedes Weges zu ermitteln und dann den kürzesten zu wählen. Wie auch immer, wir haben gerade gezeigt, dass es selbst mit nur ${tsn2} Städten ${tsn2}! = ${factorial(tsn2)} mögliche Wege gibt. Sobald du hunderte oder tausende Knoten hast, wird es selbst mit leistungsstarken Computern unmöglich, alle verschiedenen Wege auszuprobieren.