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?

2 thoughts on “Das Traveling-Salesman-Problem

  1. Hallo Stefan,

    bei meiner Arbeit habe ich hab und an auch ein Paar harte Nüsse zu knacken aber die meisten dinge lassen sich irgendwann nach gewisser arbeit Lösen. Das schwierigste was ich gefühlt umgesetzt habe war aber für mich selbst und nicht bei der Arbeit.

    Ich programmiere Hobbymäßig an einem Framework zum später Spiele einfach zu entwickeln als „kleines“ Projekt. Das letzte was ich dabei erstellt habe war ein kleines Modul welches dazu dient eine Karte besser eine Art Dungeon prozedural zu erstellen. Dies ist eigentlich ein gigantischer Algorithmus der aus mehreren
    kleinen Unterschritten besteht. Dabei habe ich gemerkt wie komplex manche Dinge dieser Art werden können. Aber wenn man sich an etwas derartigem versucht lernt man viele neue Dinge hinzu welche bei anderen Projekten ob Arbeit oder Hobby weiterhelfen können .

    Grüße Lycea

  2. Hallo Lycea,

    ab und an darf man ja auch mal ein bisschen knabbern an einem Problem. Muss ja auch herausfordernd bleiben unser Job 😉 Wobei die Spieleprogrammierung natürlich schon sehr anspruchsvoll ist!

    Viele Grüße!
    Stefan

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