Path-Finder Algorithmen in C#

Man kennt diese mathematische Aufgabe schon seit den 1930 Jahren, lange bevor es GPS-Anwendungen gab und es bekam den Namen "Traveling Salesman Problem" oder "Das Problem des Handlungsreisenden" (Wikipedia). Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass keine Station außer der ersten mehr als einmal besucht wird, die gesamte Reisestrecke des Handlungsreisenden möglichst kurz und die erste Station gleich der letzten Station ist.

Das Problem tritt schon in seiner Reinform in vielen praktischen Anwendungen auf, beispielsweise in der Tourenplanung, in der Logistik oder im Design von Mikrochips. Auch so etwas triviales wie eine Stickmaschine profitiert sehr von einer Lösung des Problems. Nennt ihr die Software die Kürzesten Wege zu den Punkten an denen sie tätig werden muss, ist das Produkt schneller fertig, die Maschine braucht weniger Energie und hält länger.

Mit einem Teilproblem davon beschäftigt sich der schwedische Entwickler Kristian Ekman in einem Beitrag auf CodeProjekt - bei ihm ist es keine Rundreise. Lediglich der kürzeste Weg von A nach Z (mit beliebig vielen Zwischenstationen) wird gesucht, wie bei einer Navigations-App. Sein Artikel erklärt das Problem und bietet Beispielcode, den seine Leser nach Belieben verwenden dürfen. Der Artikel vergleicht dabei auch zwei gängige Basisalgorithmen namens Dijkstra und A*. Auf dieser Seite finden Sie seine Ausführungen.