Worum geht es in dieser Aktivität?

Die Netzwerke, an denen wir gearbeitet haben, sind minimale Steinerbäume. Sie werden „Bäume“ genannt, weil sie keine Zyklen haben, genau so wie die Zweige auf einem echten Baum auseinander wachsen, sich aber (normalerweise) nicht wieder vereinigen und wieder zusammenwachsen. Sie werden „Steiner“-Bäume genannt, weil neue Punkte, Steiner-Punkte, zu den ursprünglichen Standorten hinzugefügt werden können, die die Bäume verbinden. Und sie werden „minimal“ genannt, weil sie die kürzeste Länge eines Baumes haben, der all diese Punkte verbindet. In der Schlammstadt (Aktivität 9) haben wir gelernt, dass ein Netzwerk, das eine Anzahl von Punkten verbindet, die die Gesamtlänge minimiert, ein minimal aufspannender Baum genannt wird: Steinerbäume sind genauso, außer dass neue Punkte eingeführt werden können.

Es ist interessant, dass es zwar einen sehr effizienten Algorithmus zum Aufspüren minimaler Spannbäume gibt (Aktivität 14) - ein gieriger, der die beiden nächsten, bisher nicht verbundenen Punkte wiederholt verbindet - es aber keine allgemein effiziente Lösung für das minimale Steiner-Problem gibt. Steinerbäume sind viel komplexer, weil du entscheiden musst, wo du die Extrapunkte einsetzen möchtest. Tatsächlich ist es eher überraschend, dass der schwierige Teil des Steinerbaum-Problems nicht darin besteht, die genaue Position der Steiner-Punkte zu bestimmen, sondern grob zu entscheiden, wo sie platziert werden sollen: zum Beispiel den Unterschied zwischen den zwei Lösungen zu Beispiel 2. Sobald du weißt, in welche Regionen die neuen Punkte eingefügt werden sollen, ist die Feinabstimmung auf die optimale Position relativ einfach. Seifenfilme machen das sehr effektiv, genauso wie Computer.

Minimale Steinerbäume zu finden ist Teil einer Geschichte, die das Einsparen von viel Geld im Telefongeschäft bewirkt hat. Vor 1967, als Firmenkunden in den USA große private Telefonnetze betrieben, mieteten sie die Leitungen von einer Telefongesellschaft. Der Betrag, den sie in Rechnung stellten, wurde nicht auf der Grundlage berechnet, wie die Drähte tatsächlich verwendet worden sind, sondern auf der Grundlage der kürzesten Netzverbindung, die möglich war. Der Grund war, dass der Kunde nicht extra bezahlen musste, nur weil die Telefongesellschaft eine Rundum- Route verwendete. Ursprünglich arbeitete der Algorithmus, der die Kosten berechnete, durch das Bestimmen des minimalen aufspannenden Baums. Um 1967 wurde jedoch von einem Kunden - einer Fluggesellschaft mit drei großen Netzknoten - bemerkt, dass die Gesamtlänge des Netzwerks reduziert würde, wenn sie einen vierten Netzknoten als Zwischenpunkt anfordern würden. Die Telefongesellschaft musste die Gebühren auf das reduzieren, was sie gewesen wären, wenn es am Steiner-Punkt eine Telefonzentrale gegeben hätte! Obwohl der minimale Steinerbaum bei typischen Einstellungen nur 5% oder 10% kürzer ist als der minimale Spannbaum, kann dies eine lohnende Einsparung sein, wenn große Geldbeträge betroffen sind. Das Steinerbaum-Problem wird manchmal als „kürzestes Netzwerkproblem“ bezeichnet, da das kürzeste Netzwerk, das eine Gruppe von Punkten verbindet, gefunden wird.

Wenn du die beiden vorhergehenden Aktivitäten, das Puzzle und die Touristenstadt des Kartographen, bereits bearbeitet hast, wirst du nicht überrascht sein zu hören, dass das minimale Steinerbaum-Problem NP-vollständig ist. Mit steigender Anzahl der Standorte erhöht sich auch die Anzahl der möglichen Standorte für Steiner-Punkte und der Versuch, alle Möglichkeiten zu nutzen erfordert eine exponentiell wachsende Suche. Dies ist ein weiteres der Tausenden von Problemen, für die es einfach nicht bekannt ist, ob die exponentielle Suche das Beste ist, was gemacht werden kann, oder ob es einen noch nicht entdeckten polynomiellen Algorithmus gibt. Es ist jedoch bekannt dass, wenn ein Polynomialzeitalgorithmus für dieses Problem gefunden wird, dieser in einen Polynomzeitalgorithmus für die Graphfärbung umgewandelt werden kann, um minimale Absorptionsmengen zu finden - und das gilt auch für alle anderen NP-vollständigen Probleme.

Wir haben am Ende der vorherigen Aktivität erklärt, dass „NP“ im Begriff NP-vollständig für „nicht-deterministisches Polynom“ steht und „complete“ bedeutet, dass wenn ein polynomieller Algorithmus für eines der NP-vollständigen Probleme existiert, dann können auch alle anderen NP-vollständigen Probleme zu polynomiellen Algorithmen umgewandelt werden. Die Menge der Probleme, die in polynomieller Zeit lösbar sind, wird „P“ bezeichnet. Die entscheidende Frage ist also, ob es für NP-vollständige Probleme polynomielle Algorithmen gibt - mit anderen Worten, ist P = NP? Die Antwort auf diese Frage ist nicht bekannt, und es ist eines der großen Geheimnisse der modernen Informatik.

Probleme, für die polynomielle Algorithmen existieren - auch wenn diese Algorithmen sehr langsam sind - werden als „machbar“ bezeichnet. Probleme, für die polynomielle Algorithmen nicht existieren, werden als „hartnäckig“ bezeichnet, denn unabhängig davon wie schnell dein Computer ist oder wie viele Computer du gleichzeitig verwendest, bedeutet ein kleiner Anstieg der Problemgröße, dass sie in der Praxis nicht gelöst werden können. Es ist nicht bekannt, ob die NP-vollständigen Probleme – zu denen auch das Puzzle des Kartographen, die Touristenstadt und die Eisstraßen gehören – „machbar“ sind oder nicht. Aber die meisten ComputerwissenschaftlerInnen sind pessimistisch und vermuten, dass ein polynomialer Algorithmus für NP-vollständige Probleme niemals gefunden werden kann. Daher wird der Beweis, dass ein Problem NP-vollständig ist als starker Beweis dafür angesehen, dass das Problem von Natur aus unlösbar ist.

Was kannst du tun, wenn dein Chef dich auffordert einen effizienten Algorithmus zu entwickeln, der die optimale Lösung für ein Problem ermöglicht und du findest keinen?

– Beispiel dazu ist der Fall, wo eine Fluggesellschaft auf die Tatsache stieß, dass die Netzwerkkosten durch Einführung von Steiner-Punkten reduziert werden konnten. Es wäre schon vorab großartig, wenn du beweisen könntest, dass es keinen effizienten Algorithmus gibt um die optimale Lösung zu finden. Aber es ist sehr schwierig, negative Ergebnisse wie diese in der Informatik zu beweisen, denn wer weiß schon, welche/r schlaue ProgrammiererIn in der Zukunft einen obskuren Trick findet, der das Problem löst. Es ist also unwahrscheinlich, dass du in der Lage bist, kategorisch zu sagen, dass kein effizienter Algorithmus existiert - dass das Problem demnach unlösbar ist.

Wenn du aber zeigen kannst, dass dein Problem NP-vollständig ist, dann ist es stark anzunehmen, dass Tausende von Menschen in Forschungslaboratorien an ähnlichen Problemen gearbeitet haben, die deinem eigenen Problem entsprechen, und es auch nicht geschafft haben, eine effiziente Lösung zu finden. Das bringt vielleicht keinen Bonus, aber es bringt dich aus dem Schneider!

Natürlich müssen solche Probleme im wirklichen Leben noch gelöst werden und dann wenden sich die Leute der Heuristik zu - Algorithmen, die nicht garantieren die bestmögliche Lösung zu geben, aber eine Lösung geben, die sehr nahe an der optimalen Lösung liegt. Heuristische Algorithmen können sehr schnell sein, und der Verlust nicht die bestmögliche Lösung zu finden, kann ziemlich klein sein, sodass sie gut genug sind, um die Aufgabe zu erledigen. Es ist einfach frustrierend zu wissen, dass es einen etwas besseren Zeitplan oder einen etwas besseren Entwurf für ein Netzwerk oder für Straßen geben könnte.

Weiterführende Literatur

Der Cartoon basiert auf einem aus Gareys und Johnsons Buch “Computers and Intractivability”. Berühmt ist eine Karikatur, die einen Forscher darstellt, der seinem Chef Bericht erstattet und begründet, warum er eine bestimmte Aufgabe nicht erfüllen konnte. Mit diesem Szenario veranschaulicht die Karikatur, wie die Methode der NP-Vollständigkeit verwendet werden kann, um ein berühmtes Dilemma der Informatik zu lösen, in dem man für buchstäblich Tausende von grundlegenden Rechenproblemen weder einen effizienten Algorithmus angeben noch beweisen kann, dass es einen solchen Algorithmus nicht gibt. Der in dieser Sammlung verwendete Cartoon wurde von Stefan Szeider angepasst und unter der Creative-Commons-Lizenz 4.0 veröffentlicht. Die Spalte “Computer recreations” im Scientific American, Juni 1984, enthält eine kurze Beschreibung, wie man Steinerbäume mit Seifenblasen herstellt, zusammen mit interessanten Beschreibungen anderer analoger Geräte zur Problemlösung, einschließlich eines ‚Spaghetti-Computers’ zum Sortieren, eines Fadenspiels mit Leinen, um den kürzesten Pfad in einem Graphen zu finden und einer Licht- und Spiegelvorrichtung zum Ermitteln, ob eine Zahl eine Primzahl ist oder nicht. Diese erscheinen auch in einem Abschnitt über analoge Computer in Dewdneys „Turing Omnibus“.