Kürzeste Wege

TL; DR. Probleme können einfach, aber auch NP-schwer sein.

Bei jeder Routenplanung wird ein Weg unter bestimmten Nebenbedingungen optimiert. Vielleicht sind zwei Städte lediglich über den Wasserweg verbunden und falls die Fähre nur Personen transportiert, wird das nichts mit einer Route, die über diesen Weg funktionieren. Gleichzeitig kann ein Weg kurz, aber ungemütlich scheinen und der fünfminütige Umweg ist sicherer, gemütlicher und gibt dir eine bessere Erfahrung. Das Problem dahinter ist bekannte unter den Traveling Salesman Problem. Du hast bestimmte Standorte, die du besuche möchtest und willst dabei den optimalen weg finden. Mit dem Chinese Postman Problem gibt es noch die Alternative, dass du alle Wege betreten haben möchtest ohne möglichst einen Weg mehrmals gehen zu müssen. Bei beiden Problemen handelt es sich um NP-schwere Probleme, also jene Probleme die nicht NP- vollständig sind, aber jedes Problem aus der Komplexitätsklasse NP sich polynomiell darauf reduzieren lässt.

Das alles klingt zwar sehr kompliziert, es ist aber überaus anschaulich. Das spannende hier ist die tatsächliche Anwendung, denn jeder von uns benutzt Navigationssysteme, bestellt ein routenoptimiertes Taxi oder plant seine nächste Tour mit den schönsten Aussichten. Sprich, die annähernd optimale Lösung dieses Problems ist nicht nur für eine Menge Gemütlichkeit zuständig, sondern bestimmt die optimalen Lieferketten, die unsere Lebensmittel garantieren. Das ist ein einziges Beispiel der zahlreichen Problemformulierungen, die dein Leben umgeben, ohne dass du es bewusst als Problem wahrnimmst.

Welche Probleme, die einem normalerweise nicht auffallen, kennst du aus deiner Welt? Schreib es mir in die Kommentare!