Home > Informatik > Optimierungsprobleme

Optimierungsprobleme in der Informatik

Einführung - Datentypen - Sprachen - Probleme

Das Traveling Salesman Problem (TSP)

Ein typisches Anwendungsgebiet der Informatik sind die vielen Optimierungsprobleme, die es in Wirtschaft und Wissenschaft zu lösen gilt. Das wohl berühmteste Beispiel, das auch an vielen Schulen im Informatikunterricht behandelt wird, ist das Problem des Handelsreisenden oder auf Englisch das "Traveling Salesman Problem", abgekürzt mit TSP.

Stellen Sie sich vor, Sie sind ein Handelsreisender und müssen auf Ihrer Tour eine bestimmte Zahl von Städten besuchen. Die Reihenfolge, in der Sie die Städte besuchen, ist nicht festgelegt, es gilt aber die Bedingung, dass Sie jede Stadt genau(!) einmal besuchen. Am Ende müssen Sie wieder in der Ausgangsstadt ankommen.

Hier ein Beispiel für eine solche Tour:

Eine Tour

Sie sehen, dass die gewählte Tour nicht irgendeine zufällige ist. Die Tour wurde so gewählt, dass sie möglichst kurz ist. Ob es sich aber wirklich um die kürzeste Tour handelt, kann durch eine solch einfache Betrachtung nicht festgestellt werden.

Und damit wären wir auch schon bei dem eigentlichen Optimierungsproblem angekommen: Ziel ist es, eine möglichst kurze Rundreise durch alle Städte zu finden. Dazu gibt es verschiedene Algorithmen, auf die auf den folgenden Seiten eingegangen wird. Einige dieser Algorithmen sind so einfach, dass sie im Informatikunterricht nicht nur theoretisch behandelt, sondern auch tatsächlich implementiert werden können.

Optimierungsprobleme allgemein

Das TSP ist stellvertretend für eine ganze Klasse ähnlicher Optimierungsprobleme. Stellen Sie sich eine Maschine vor, die Löcher nach einem bestimmten Muster in eine Platte bohren muss. Der Bohrkopf muss sich von einem Loch zum nächsten bewegen. Auch hier ist es sinnvoll, die Gesamtstrecke, die der Bohrkopf zurücklegen muss, möglichst klein zu halten. Beim Design von Leiterplatten hat man ähnliche Probleme.

Steht die algorithmische Infrastruktur, dann ist die Optimierung noch nicht an Ihrem Ende angekommen. Wie bei der Software, so ist auch beim menschlichen Umgang mit digitalen Gütern die Optimierung als stetiger Prozess des Anpassens an bestimmte Gegebenheiten zu verstehen. In einem Fernstudium Qualitätsmanagement lernt man beispielsweise statistische Kontrollmethoden kennen, um Projekte effizient zu managen. Diese Art der Prozessoptimierung wirkt sich natürlich auch auf die Qualität des späteren Endprodukts aus.

Algorithmen zum TSP und anderen Problemen

Seitenanfang -