Thomas Kahle
Als wenn er es nicht schon schwer genug hätte, muss der Weihnachtsmann auch noch ein schwieriges Mathe-Problem lösen. In welcher Reihenfolge soll er denn all die Kinder besuchen, damit er nicht zu viele Umwege macht und die Kosten für das Rentierfutter nicht komplett eskalieren. Glücklicherweise gab es in den letzten 100 Jahren zahlreiche Fortschritte, sodass die Mathematik dem Weihnachtsmann nun sowohl theoretisch-allgemein als auch praktisch für seine Route eine zufriedenstellende Antwort geben kann. Wir schauen in nur 24 Minuten auf das Problem des Handlungsreisenden, einem wegweisenden Problem für die mathematische Optimierung.
- Wisspod-Podcastadventskalender 2025
- Eigenraum-Podcast
- Quelle: „Der Handlungsreisende, wie er sein soll …“ (1832)
- Richard M. Karp in Math Genealogy
- EIG011 Graphentheorie
- Math encounters: Vortragsvideo mit vielen Details und Anekdoten
- Christofides Algorithm
- 1. Paper zur 1E-36 Verbesserung
- Quanta Magazine Artikel zu den Verbesserungen von Christofides Algorithmus
Feedback gerne auf Mastodon @Eigenraum@podcasts.social, an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite.
Automatisch generiertes Transkript (nicht geprüft)
So, hallo zusammen, liebe Leute. Hier ist der Eigenraum-Podcast.
Mein Name ist Thomas Kahle. Ich lebe und arbeite im schönen Magdeburg an der
Elbe und denke, dass es nicht genug Mathe-Podcasts gibt. Und deswegen mache ich hier auch einen.
Einige von euch wissen das natürlich alles, weil sie hier öfter reinhören.
Andere hören jetzt vielleicht gerade den Wissenschafts-Podcast-Adventskalender.
Wissport Weihnacht Der Adventskalender von Wissens- und Wissenschaftspodcasts
Musik Und ich begrüße euch alle gemeinsam in eurer Vereinigungsmenge.
Da kann ich euch dann mal vorstellen, die zwei Gruppen, also welche Eigenraumzuhörerin
ist. Es gibt diesen Adventskalender, nun schon eine ganze Weile,
und da gibt es jeden Tag ein wissenschaftliches Hörtürchen zu öffnen.
Und andersherum, wenn ihr den Kalender hört, aber sonst noch nie Eigenraum gehört
habt, dann abonniert den vielleicht oder schaut mal auf unserem Mast oder den
Kanal at eigenraum.podcasts.social vorbei.
Das wäre super goldig. Und dann gibt es natürlich auch die ganze Menge an Leuten,
die in beiden Gruppen sind, also die Eigenraum und den Adventskalender hören.
Da freue ich mich natürlich ganz besonders drüber. Vielen Dank an euch und eure
treue Hörerschaft und das schöne Feedback, was es immer gibt.
So, also jetzt hier zum Jahresende, zum Fest, muss man ja auch mal Danke sagen. Also, vielen Dank.
So, ich möchte euch heute eine Geschichte erzählen und ich muss mich ein bisschen
ranhalten, weil es ist ja bald Weihnachten und ich muss noch Geschenke besorgen
und dazu muss ich in sieben verschiedene Läden.
Ich kaufe nämlich meine Geschenke immer offline, das stimmt zwar nicht,
aber für die Geschichte ist es jetzt ganz gut und die Läden,
die sind überall in der Stadt verteilt.
Und Brot brauche ich auch noch. Und dann wäre es vielleicht auch noch ganz nice,
wenn ich beim Fahrradladen vorbeikommen würde. Und da brauche ich nämlich auch
noch ein Teil, was ich mir da holen muss.
So, jetzt habe ich also vielleicht hier so eine Karte der Stadt vor mir.
Und da sind meine, wie war das jetzt nochmal, sieben Läden, zwei Brot,
Fahrrad, neun Punkte markiert, wo ich hin will.
Und danach will ich natürlich wieder nach Hause. Und wie mache ich das denn jetzt am besten?
Also ich will natürlich nicht irgendwie so riesige Umwege fahren
oder ewig brauchen und ich will auch einen schönen Weg finden und das will ich
mir jetzt mal als mathematisches Problem anschauen und dann hätte ich für jede
mögliche Strecke in der Stadt in meinem mathematischen Modell vielleicht noch
irgendwie so eine Art Bewertung,
wie nervig es jetzt wäre, diese Strecke zu benutzen.
Und die Nervigkeit, die setzt sich dann zusammen aus erstmal der Entfernung
und vielleicht, ob da gerade Baustellen sind, ob man am Fahrrad gut durchkommt,
viele Ampeln oder was weiß ich.
Und in Magdeburg sind zum Beispiel gerade viele Brücken kaputt und das Schlimme
ist, wenn eine Brücke kaputt ist, dann kann man nicht drüber und man kann aber auch nicht drunter.
Also wir haben viele so eine Wegekreuzung, wo sich zwei Verkehrswege kreuzen
und man kann in keine von den Richtungen durch.
Das macht das Ganze gerade ein bisschen schwierig und das könnte man alles dann
beachten bei der Bewertung.
Also wenn ich jetzt zum Beispiel von dem ersten Laden zum zweiten Laden will.
Dann gibt es eine Bewertung dafür, die ich vielleicht mit einer Zahl abspeichern kann.
Und vom zweiten Laden zum dritten Laden gibt es eine Bewertung und vom ersten
Laden zum dritten Laden gibt es auch eine Bewertung.
Und das für alle meine Orte, wo ich hin will, für jedes Paar gibt es eine Bewertung,
wie teuer es für mich wäre oder wie nervig, sagen wir mal, diese Strecke zu fahren.
Und dann hat man schon so ein mathematisches Optimierungsproblem.
Also mein mathematisches Optimierungsproblem ist jetzt, in welcher Reihenfolge
soll ich jetzt meine Besorgung machen? Also ich starte immer bei mir zu Hause.
Und dann muss ich mir einen Ort aussuchen, zu dem ich zuerst will.
Und dann füge ich meiner summierten Nervigkeit der Besorgungen hinzu,
die Kosten, die ich habe, um zu diesem ersten Ort zu kommen.
Von diesem ersten Ort aus muss ich dann den zweiten Ort aufsuchen und da habe
ich dann die Auswahlmöglichkeiten. Also ich will noch nicht direkt wieder nach
Hause, weil ich muss ja meine ganzen Besorgungen machen.
Also habe ich dann noch die anderen zur Auswahl und dann gibt es wieder die
Nervigkeiten, weil ich habe ja diese Nervigkeiten für je zwei Orte gegeben.
So, und das nimmt an das Problem des Handlungsreisenden und das wird schon eine
ganze Weile untersucht, so richtig mathematische Untersuchungen gibt es dazu
schon seit mindestens 1930, es wird intensivst beforscht, wurde aber schon vorher formuliert.
Ich habe das mal auf Wikipedia nachgeschlagen und da wird ein Handbuch von 1832
zitiert, ein Handbuch für Handlungsreisende mit dem schönen Titel Der Handlungsreisende,
wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen
Erfolgs in seinen Geschäften gewiss zu sein von einem alten Commiss Voyageur.
So und das ist jetzt also erstmal ein schönes Beispiel für Buchtitel,
die waren damals immer noch so ein bisschen länger.
Ich habe dem Buch auch mal so ein bisschen rumgeschmökert, das ist da verlinkt
und da stehen dann so Sachen drin wie, die Geschäfte führen den Handlungsreisenden
bald hier, bald dorthin und es lassen sich nicht alle füglichen Reiserouten
angeben, die für alle vorkommenden Fälle passend sind.
Aber es kann durch zweckmäßige Wahl und Einteilung der Tour manchmal so viel
Zeit gewonnen werden, dass wir es nicht glauben, umgehen zu dürfen,
auch hierüber einige Vorschriften zu geben.
Wow, das war ein Satz. Und dann kommen in dem Buch dann noch so explizite Listen für Deutschland.
Also die Reihenfolge, in der man so Städte da um Frankfurt rum,
war das, was ich gesehen habe, besuchen sollte.
Und dann steht auch immer noch, welches Hotel man ansteuern soll oder welche Unterkunft.
Und da ist mir aufgefallen, dass es irgendwie den Namen Ritter für Unterkünfte damals oft gab.
Also da sollte man im Wetzlar im Ritter übernachten, im Siegen im Löwen,
im Marburg wieder im Ritter und so weiter.
Ich weiß nicht, ob das eine Kette war, aber wahrscheinlich war es einfach ein
sehr populärer Name für seine Unterkunft oder sein Gasthaus,
den Namen Ritter oder Löwe zu wählen.
So, aber zurück zum mathematischen Problem. Wie löst man das nun?
Also es sieht irgendwie ziemlich fies aus, weil es eben diese ganzen vielen
Kombinationen von Wegen gibt, die man alle ausrechnen und dann vergleichen müsste.
Also das ist wirklich ein schwieriges Problem und hat deswegen die mathematische
Forschung für die Optimierung,
also die heutzutage nennen wir es die mathematische Optimierung,
man nennt das auch früher Operations Research im Englischen.
Sehr geprägt dieses Problem.
Das heißt, das Travelling Salesman Problem auf Deutsch, das Problem des Handlungsreisenden
und es war wirklich absolut wegweisend für die mathematische Optimierung im 20.
Jahrhundert und bis heute, weil es eben ein sehr praktisch relevantes Problem ist.
So, und da hat man immer diese Unterscheidung in zwei...
Teile dieser Forschung. Also es gibt immer so, wie es in der Mathematik so üblich
ist, diese theoretische Forschung für die Optimalität.
Was ist der beste Algorithmus, der die optimale Lösung findet?
Was können Computer berechnen? Können Computer das überhaupt lösen,
vor das Universum endet?
Und solche Fragen. und dann hat man für die Reisen im Alltag oder für die Amazon-Fahrer,
die hier rumfahren und unsere Weihnachtspakete ausliefern, immer so gut genug Lösungen.
Also in der Realität würde ich zum Beispiel wahrscheinlich bei meinem echten
Problem gar nicht auf eine Karte schauen.
Ich kenne mich in der Stadt ja irgendwie so ein bisschen aus und treffe solche
Entscheidungen irgendwie intuitiv.
Und dann ist die letzte Optimalität für mich vielleicht auch gar nicht so wichtig.
Also wenn meine Route irgendwo durch eine Veränderung mal 200 Meter kürzer werden würde.
Dann ist es jetzt den Aufwand des Auffindens dieser optimalen Route vielleicht
gar nicht wert oder auf dem Weg ist vielleicht sowieso noch eine Ampel und die
könnte rot sein und dann bekomme ich da,
wenn die Ampel rot ist, bekomme ich da eh nochmal zwei Minuten drauf und es
gibt so eine gewisse Unschärfe,
sodass mir so minimale Verbesserungen eigentlich komplett egal sein können.
Ja, also da gibt es zumindest in der Forschung jetzt diesen theoretischen Aspekt,
der ganz stark mit der Informatik verknüpft ist.
Das ist eben, wie schnell kann man dieses Problem zur exakten Optimalität lösen.
Und die Eingabe für so ein Programm, das dann gesucht ist, wäre dann zum Beispiel
ein mathematischer Graph, wie wir es nennen, der alle möglichen Strecken zwischen
den Punkten enthält, zusammen mit Kosten für jede Strecke.
Das, was ich am Anfang die Nervigkeit der Strecke genannt habe,
also das modelliert man dann einfach so, dass es.
Irgendwie eine Zahl gibt, die die Kosten bezeichnet, diese Strecke zwischen zwei Punkten zu reißen.
Also vom Fahrradladen zum Spielzeugladen dauert es zehn Minuten und dann für
jede mögliche Kombination aller Orte so eine Bewertung.
Und dann soll der Computer die Reihenfolge der Orte bestimmen,
in welcher Reihenfolge die aufgesucht werden.
Und da ist jetzt keine echte Karte mehr nötig,
alles wird in so einem sogenannten gewichteten Graphen abgespeichert und das
ist eben die Angabe der Zahlen dieser Reisekosten von Punkt zu Punkt.
Und eine Tour in dem Graphen, die wieder zum Startpunkt zurückkehrt,
aber keinen Punkt doppelt aufsucht, ist dann ein sogenannter Hamilton-Kreis
und wenn ich einmal alles abgelaufen habe und aufsummiere.
Wie viele Kosten ich verursacht habe durch meinen ganzen Weg,
dann suche ich jetzt unter allen Wegen, die alle Punkte in dem Graphen aufsuchen,
den Weg, wo die Summe über die ganzen Kosten am niedrigsten ist.
Zur Grafentheorie und Hamilton-Kreisen in Grafen haben wir auch eine spezielle
Folge hier im Eigenraum.
Wenn ihr da mal nachhören wollt, könnt ihr euch mal Eigenraum Folge 11 Grafentheorie
dazu nochmal anhören. So, und wenn man jetzt ganz naiv rangeht,
dann kann man vielleicht so die Möglichkeiten, die Anzahl der Touren sich mal überlegen.
Ich bin zu Hause und das ist einer von meinen N-Orten.
Und jetzt würde ich zum ersten Ort, da habe ich N-1, Orte zur Auswahl,
die ich jetzt als erstes aufsuchen könnte.
Und wenn ich dann bei meinem ersten Ort bin, dann will ich noch nicht wieder
zurück nach Hause schnell und ich will nicht dahin, wo ich gerade bin und habe
dann also noch n-2 Möglichkeiten für den nächsten Ort.
Und wenn ich an dem Ort bin, habe ich noch n-3 Möglichkeiten,
weil ich ja drei schon besucht habe und noch nicht wieder nach Hause will.
Weil ich noch welche zu besuchen habe. So, und wenn man das jetzt aufmultipliziert,
diese verschiedenen Möglichkeiten, die sich mir da bieten,
dann kommt man auf n-1 mal n-2 mal n-3 und so weiter, bis am Ende mal 2 mal
1 und das nimmt man die Fakultätsfunktion, n-1 Fakultät, wie die Fachleute sagen,
und das ist eine ganz schlimme Funktion.
Also die Anzahl der möglichen Touren, die wächst irre, die wächst wie eine Fakultätsfunktion.
Man kann jetzt vielleicht noch durch zwei teilen, weil wenn ich so eine Tour
habe und ich komme ja wieder nach Hause, dann kann ich die auch rückwärts durchlaufen,
gibt die gleichen Kosten. Aber das macht bei der Größe dieser Funktion eigentlich
überhaupt nichts, da noch durch zwei zu teilen.
Die wächst einfach komplett irre, schneller als eine Exponentialfunktion.
Sowas wie n hoch n geteilt durch e hoch n ist das Wachstum der Fakultätsfunktion.
Aber so ganz so schlimm ist es nicht man findet auch recht leicht normal exponentielle
Algorithmen also sowas wie eine Laufzeit von n² mal 2 hoch n aber immer noch exponentiell,
also wächst exponentiell zwar nicht wie n hoch n, aber immer noch wie 2 hoch n.
So, also jetzt muss man natürlich ein bisschen an die Praxis denken also wenn
man jetzt zum Beispiel der Weihnachtsmann wäre Und man müsste n gleich Anzahl
Kinder besuchen, dann wäre das schon ziemlich irre.
Also egal, ob mit den naiven Vergleich aller Touren oder mit so einem normal
exponentiellen Algorithmus.
Ein exponentieller Algorithmus ist eigentlich immer ziemlich schlecht.
Schöner wäre ein polynomieller Algorithmus.
Das bedeutet, dass die Anzahl der Rechenschritte zum Finden der optimalen Lösung,
die ja irgendwas mit der Anzahl der möglichen Wege zu tun haben,
beschränkt wird durch ein Polynom.
Ein Polynom, sowas wie n² plus n hoch 3 plus n hoch 4 oder so.
Und eben nicht solche Terme 2 hoch 3.
Also das N soll nicht im Exponenten vorkommen. N, die Anzahl unserer Orte,
die wir besuchen wollen.
So, und dann geht es eben in zwei Richtungen. Also man kann Theorie und Praxis sich anschauen.
Optimalität und Praktikabilität. Und die ganzen theoretischen Untersuchungen,
die klingen erstmal so ein bisschen negativ.
Also bezüglich der optimalen Lösung führte dann in den 1970er Jahren diese ganze
Untersuchung zu einem wichtigen Ergebnis, so parallel mit der Entstehung der
Komplexitätstheorie in der Informatik dazu, dass dieses Travelling Salesman
Problem, TSP auch kurz genannt,
dass es ein sogenanntes NP-vollständiges Problem ist.
Das wurde von Richard Karp bewiesen, einem amerikanischen Informatiker und Mathematiker.
Der hat auch 1985 den Turing Award erhalten, hat 556 Nachfahren in der mathematischen Genealogie.
Und sein Ergebnis bedeutet, dass ein Programm, wenn man eins hat,
welches das TSP, das Travelling Salesman Problem zur Optimalität lösen kann.
Dann kann es auch alle anderen von diesen NP-Problemen, also den schwierigen
algorithmischen Problemen, die in nicht deterministisch-polynomierler Zeit lösbar sind, auch lösen.
Das ist so ein The One to Rule Them All-Regel, also es ist genauso schwer oder
schwerer, das TSP zu lösen, wie alle diese NP-Probleme, die selbst die schweren Probleme sind.
Die Schlussfolgerung, die man daraus zieht, ist, dass TSP selbst ein schwieriges Problem ist.
Also man ist jetzt dadurch nicht außergewöhnlich motiviert, eine optimale Lösung
für TSP zu finden, die schnell läuft, sondern man sieht das eher so,
aha, das ist ein Indiz dafür, dass auch TSP ein sehr schwieriges,
algorithmisch schwieriges Problem ist.
Dahinter steht natürlich diese Frage P versus NP, eins der Millennium-Probleme, ob sich die
Solche nicht deterministisch-polynomiellen Probleme auch in Polynomialzeit lösen lassen.
Also wenn das so wäre, dann wäre P gleich NP, wie man in dieser Sprache sagt
und das wäre ein sehr überraschendes Ergebnis.
Die meisten Expertinnen und Experten gehen davon aus, dass es nicht so ist,
dass also diese NP-vollständigen Probleme wirklich schwieriger sind.
Das hört sich jetzt erstmal an wie ein negatives Ergebnis für unser Travelling
Salesman und wenn man jetzt also der Weihnachtsmann oder Thomas ist,
der Einkäufe macht oder der Amazon Paketbote, dann muss man ja irgendwas machen
und dann kommen wir zur Praxis.
Und in der Praxis benutzt man einen Löser und einer davon ist zum Beispiel das Programm Concord.
Das wird an der Uni Waterloo in Kanada entwickelt.
Und dieses Programm Concord, das ist ein Optimallöser.
Und da kann man mal schauen, wie weit man mit dieser wirklichen Optimalität
jetzt heutzutage schon gekommen ist. Denn dieses Problem...
Kann hier zur Optimalität mit echten Problemen mit mehreren zehntausend Städten
oder Orten gelöst werden.
Und da ist eben sehr viel Optimierung reingeflossen, die verschiedene Annahmen
benutzt. Also man hat auf der einen Seite einfach mathematische Optimierungen,
es sind einfach ganz viele geniale algorithmische Ideen in diese Lösung eingegangen.
Auf der anderen Seite hat man auch entdeckt, dass es sinnvolle Annahmen gibt,
die man für unsere praktischen Probleme treffen kann, die das Problem aber vereinfachen.
Und eine ganz wichtige Annahme, das war auch schon relativ früh bekannt.
Ist, dass man sich, wenn man sich wirklich in einem euklidischen Raum befindet,
dann gilt da die sogenannte Dreiecksungleichung, die sagt, wenn ich von A nach
B will, ist der direkte Weg am kürzesten und wenn ich zwischendurch noch einen
anderen Punkt besuche, C,
dann kann es höchstens so schnell gehen wie auf dem direkten Weg,
wenn nämlich C direkt auf dem direkten Weg liegt, ansonsten hat man immer eine längere Route.
So, und wenn das jetzt für diese Nervigkeit der Strecken gilt,
diese Dreiecksungleichung,
dass kein Weg kürzer werden kann als der direkte Weg,
dann kann man viele Vereinfachungen machen, die zum Beispiel damit zu tun haben,
dass wenn sich auf so einer Karte, die ich hinmale, Wege kreuzen,
dann kann ich so lokal meine Wege optimieren.
Und ja, unter Verwendung solcher Annahmen und ganz, ganz viel Theorie aus der
mathematischen Optimierung, die über die letzten 100 Jahre entwickelt wurde,
konnte man eben zu diesem C-Programm kommen, Concorde,
was das Travelling Salesman Problem zur Optimalität für mehrere 10.000 Städte
oder Orte, die man besuchen will, lösen kann.
Und dann kann man natürlich auch noch Heuristiken machen. Also wenn das noch
nicht genug ist, wenn man jetzt wirklich der Weihnachtsmann ist und sehr viele
Orte auf der Welt besuchen will,
man kann dann sagen, sich vielleicht so eine Schranke vorgeben,
ich akzeptiere Lösungen bis zu 2% Fehlertoleranz.
Also ich will einfach nur Lösungen finden, die...
Die höchstens zwei Prozent länger sind als die optimale Route.
Und ja, zwei Prozent ist schon sehr groß gewählt.
Also die Leute, die das wirklich betreiben, die wollen dann eher sowas wie 0,002 Prozent.
Und da gibt es zum Beispiel ein Benchmark-Problem von Google,
die mal auf der Erdoberfläche eine Million Städte und Orte auf der ganzen Welt
benutzt haben und dann einen zufälligen Weg gewählt haben, aus diesen ganzen
irre vielen eine Million minus eins Fakultät,
eine unvorstellbar große Zahl möglichen Wegen einfach einen zufälligen gewählt
haben und den dann einfach immer lokal optimiert.
Das bedeutet, man schaut sich einfach so einen kleinen Teil des Weges an,
stellt fest, das ist doch totaler Quatsch, was hier gemacht wird,
einfach hier in dieser Umgebung kann man das einfach so ein bisschen optimaler
machen, statt hier so dreimal kreuz und quer zu fahren, machen wir doch für
diese drei Städte, die hier in der Nähe sind.
Eine etwas verbesserte Route und das macht man dann an ganz vielen Teilen dieses Weges.
Und mit solchen Heuristiken bekommt man sehr schnelle Algorithmen,
die eben auch solche Instanzen mit bis zu einer Million oder noch mehr Orten
mittlerweile lösen können.
Und das ist eben das, was die Amazon-Fahrer machen.
Also da kommt man an dann Größen, die für die Praxis relevant sind und die schnell gelöst werden können.
Denn eine 99% optimale Route ist für die meisten praxisrelevanten Probleme doch
ausreichend. So, meine Zeit ist
knapp, deswegen muss ich jetzt schon ein bisschen zu meinem Fazit kommen.
Was ich besonders interessant finde an diesem Problem ist, dass wir haben auf
der einen Seite diese große Millenniumsfrage P versus NP.
Was kann berechnet werden mit dem Computer? Wie schnell kann es berechnet werden?
Und es gibt eine Million für die Lösung der Frage, ist jedes nicht deterministisch-polynomielle
Problem, so wie das Travelling-Salesman-Problem auch polynomiell lösbar?
Vor 25 Jahren, als das formuliert wurde, war das noch viel mehr Geld,
also einen Inflationsausgleich habt ihr da irgendwie bei diesem Problem nicht so ganz gedacht, aber….
Ich frage mich, wie relevant dieses Problem wirklich ist. Also wir sehen hier
bei diesem Travelling Salesman Problem zwei Aspekte.
Der erste Aspekt ist, dadurch, dass wir uns wirklich die ganze Zeit abarbeiten
an solchen Fragen wie Pre versus NP und wie schnell kann man die optimale Lösung
wirklich berechnen in der Praxis und welche Annahmen kann man noch machen in
diesem konkreten Problem.
Um die optimale Lösung unter einer realistischen und sinnvollen Annahme zu machen.
Schneller zu bekommen, die bringen uns wirklich vorwärts, sodass wir in den
Bereich der relevanten Anwendungen kommen, also ich meine selbst für 10.000 Orte,
da kann man ja schon, also der Handlungsreisende von 1830 mit seinen Städten
in Deutschland, der wird damit sehr happy werden und gleichzeitig zeigt es aber auch,
dass wir vielleicht diese ganzen NP-Probleme, dass wir vor dieser Negativität
der Unlösbarkeit und der Komplexität gar nicht so viel Angst haben müssen.
Weil wir eigentlich immer, wenn wir uns eine Situation genau anschauen.
Gute Heuristiken finden können.
Es gibt einfach immer noch eine cleverere Idee, wie man irgendwie so einem Nicht-Machbarkeitsresultat
oder einem Negativresultat aus der Komplexitätstheorie in die Suppe spucken
kann oder es umgehen kann.
Und es ist ganz wichtig, da einen kühlen Kopf zu bewahren und sich nicht von
solchen Negativresultaten, die man manchmal in der Informatik oder in der Mathematik
hat, aufhalten zu lassen, sondern positiv zu bleiben, seine Kreativität auszuleben.
Und so passieren auch immer noch heutzutage neue Entdeckungen bei Dingen,
denen man dachte, dass sie 1970 für unmöglich erklärt wurden.
Also es gab zum Beispiel bei der Fragestellung, also es geht natürlich jetzt
unglaublich auf, also dieses, das wird ja seit 100 Jahren beforscht,
also da gibt es ganz viele verschiedene Stoßrichtungen und eine von denen ist
die sogenannte 1,5-Approximation,
in der man sich jetzt fragt nach 50 Prozent entfernt von der Optimallösung.
Höchstens 50 Prozent entfernt von der Optimallösung.
Und da gibt es eben ein Ergebnis von Christoph Fides aus dem Jahr 1976,
das sagt, dass es einen Polynomialzeit-Algorithmus gibt, also so einen P-Algorithmus,
der das Problem bis auf 50 Prozent Fehler löst.
Und der ist eben sehr schnell, aber hat eben diesen 50-Prozent-Fehler.
Und das stand 40 Jahre lang bis dann 2020 bis 2023 in so einer Folge von Arbeiten,
die jetzt natürlich auch noch weitergeführt werden und ausgearbeitet wurden,
eben klar wurde, dass man auch unter 50 Prozent kommen kann.
Und da gab es ein sehr cooles Paper, was eben zeigt, dass man irgendwie 10 hoch
minus 36 besser sein kann als dieser Faktor 1,5 bezüglich der optimalen Kosten.
Und das war erst ein probabilistischer Algorithmus und wurde dann entprobabilisiert.
Also jetzt gibt es einen deterministischen, polynomiellen Algorithmus,
der auch unter 1,5 liegt, so ein kleines bisschen,
aber das würde als so einen Durchbruch angesehen, weil es eben 40 Jahre lang
bei diesem 1,5 stand und man sich schon fragte, ob 50% Fehler das Beste ist,
was man garantieren kann.
Wenn man einen polynomiellen Laufzeitalgorithmus haben will.
So, also das ist der positive Ausblick, auch wenn man erst ein negatives Resultat
hat oder ein negativ scheinendes NP-Vollständigkeitsresultat,
geht es doch in der Mathematik immer weiter, neue kreative Ideen kommen dazu,
man kann die richtigen Annahmen finden, die vielleicht die Realität ein bisschen
besser abbilden und mathematische Vereinfachung erlauben und so geht es doch
immer wieder weiter, auch bei diesen alten klassischen Problemen.
Gut, dann wünsche ich euch weiterhin viel Spaß mit eurer Mathematik,
was auch immer sie sein möchte und ich hoffe, ihr schaltet auch mal wieder beim
Eigenraum ein oder ihr schaltet regelmäßig wieder beim Eigenraum ein und das würde mich sehr freuen.
Also macht's gut, viel Spaß noch mit weiteren Wissenschafts-Podcasts,
Adventsfolgen und bis bald.