Das Traveling-Salesman-Problem

Das Traveling-Salesman-Problem

Es gibt einige „berühmte“ Programmierprobleme, von denen jeder Entwickler bereits einmal gehört haben sollte. Das Travelling-Salesman-Problem ist sicherlich eines der bekanntesten. Ein Handlungsreisender muss eine bestimmte Anzahl an Orten besuchen und der kürzeste Weg zwischen all diesen Punkten wird gesucht.

Was sich nach einer lächerlich einfachen Aufgabe anhört, die man mit einer simplen for-Schleife lösen könnte, stellt sich bei genauerer Betrachtung als unlösbares Problem heraus. Denn die schiere Anzahl an Kombinationsmöglichkeiten bei einer größeren Anzahl an Orten ist für Computer in endlicher Zeit nicht berechenbar. Schon bei 20 zu besuchenden Orten gibt es 20! = 2.432902E+18 verschiedene Möglichkeiten für eine Reihenfolge.

Daher benötigt man andere Ansätze, um solche Probleme zu lösen. Bei Baeldung gibt es ein schönes Beispiel für die Programmierung des TSPs mit sogenannten evolutionären Algorithmen: The Traveling Salesman Problem in Java. Diese Algorithmen bedienen sich bei bekannten Abläufen aus der Natur, zum Beispiel der Evolution, um scheinbar unlösbare Probleme näherungsweise zu lösen. Der Artikel gibt einen kurzen Einstieg in diese Thematik und zeigt eine Beispiellösung in Java.

Ich selbst lasse meine Studierenden in einem Tutorium zum Thema Produktionsplanung auch immer ein Referat über evolutionäre Algorithmen halten. Diese Ansätze bei der Programmierung sind äußerst spannend und haben mit der üblichen imperativen Herangehensweise an Probleme nicht mehr viel zu tun. Daher denke ich, dass jeder Entwickler etwas dabei lernen kann, wenn er mal eine völlig andere Lösung ausprobiert.


Musstest du schon einmal solche „harten“ Probleme lösen? Oder programmierst du hauptsächlich gut umsetzbare Algorithmen?

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax