Home > Informatik > Optimierungsprobleme

Optimierungsprobleme in der Informatik

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äden 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:

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 auch problemlos im Informatikunterricht nicht nur behandelt, sondern sogar auch programmiert 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 in eine Platte bohren muss, nach einem bestimmten Muster. 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.

Bei sämtlichen Aufgaben besteht die Herausforderung darin, sie möglichst effizient zu erledigen. Eine andere Art der Optimierung, die aber ebenfalls die Effizienz steigern soll, ist die Anpassung von Software, wie es die Produkte von Unternehmen wie Acatec leisten. Die Software wird individuell auf den Kunden abgestimmt. Zum Beispiel kann ein Produktkonfigurator für bestimmte Firmen eine sinnvolle Lösung darstellen, da so auf Basis eines definierten Regelwerkes maßgeschneiderte Varianten für Kunden erstellt werden können. Wichtig dabei ist, dass alle Lösungen, die angeboten werden, auch wirklich umsetzbar und plausibel sind. Alle Beteiligten der Wertschöpfungskette können jederzeit auf Informationen und Lösungen zugreifen, online und offline. Dadurch werden Geschäftsprozesse beschleunigt und natürlich optimiert.

Algorithmen zum TSP und anderen Problemen

Das Traveling Salesman Problem ist eines der bekanntesten Optimierungsprobleme der Informatik. Algorithmen, die das TSP auf vernünftige Weise lösen, lassen sich auch für die Lösung vieler anderer ähnlicher Probleme einsetzen, zum Beispiel bei der Herstellung von Leiterplatten.