Sightseeing.png
Sightseeing
TSP.png
TSP Spiel
kcenter.png
k-Center Spiel
Steiner.png
Steiner Baum Spiel
MCPP.png
Postboten Spiel
Routenplanung.png
Graph-
algorithmen


Verallgemeinerung des Traveling Salesman Problems: Sightseeing Problem
Planung einer Stadtbesichtigung von München
Sightseeing.png Beschreibung: Planen Sie eine Stadtbesichtung von München unter Berücksichtigung Ihres Zeit- und Finanzbudgets und Ihrer persönlichen Vorlieben für die Auswahl der Sehenswürdigkeiten.
Mathematische Beschreibung: Das Sightseeing Problem ist eine Kombination aus Knapsack-Problem und TSP: Es muss eine Auswahl der Knoten eines Graphen getroffen und auf diesen eine Tour berechnet werden, sodass die Summe der Knotenbewertungen maximiert wird unter der Nebenbedingung, dass Tourdauer und -kosten vorgegebene Schranken nicht überschreiten.

Traveling Salesman Problems
Spiel zum Traveling Salesman Problem
TSP.png Beschreibung: Werden Sie zum Handlungsreisenden und planen Sie eine möglichst kurze Rundreise durch alle gegebenen Städte. Sie können Ihre Lösung am Ende mit der Optimallösung vergleichen. Wie gut ist Ihre Intuition?
Mathematische Beschreibung: Problem des Handlungsreisenden (TSP) ist es einen kürzesten Kreis zu finden, der alle Knoten des Graphens einmal besucht.

k-Center Problem
Spiel zur Veranschaulichung des k-Center Problems
kcenter.png Beschreibung: Beat the computer! Platzieren Sie Kreise mit möglichst kleinem Radius um alle auf einer Karte markierten Punkte zu überdecken und vergleichen Sie Ihre Lösung mit der Lösung des Computers.
Mathematische Beschreibung: Euklidisches k-Center Problem

Steiner-Baum-Problem
Spiel zum Steinerbaumproblem
Steiner.png Beschreibung: Lernen Sie das Steiner-Baum-Problem kennen und konstruieren Sie gute Steiner-Bäume. Finden Sie die optimale Lösung?
Mathematische Beschreibung: Steiner-Bäume sind Bäume, die nur eine vorgegebene Teilmenge der Knoten aufspannen müssen, die restlichen Knoten dürfen als Hilfsknoten verwendete werden, müssen aber nicht angebunden sein.

Gemischtes Postboten Problem
Spiel zum gemischten Postboten Problem
MCPP.png Beschreibung: Lernen Sie das gemischte Postboten Problem kennen und konstruieren Sie eine gute Tour für den Postboten, der Briefe verteilen will und deshalb alle Straßen ablaufen muss. Finden Sie die optimale Lösung?
Mathematische Beschreibung: Beim Postboten Problem sucht man eine möglichst kurze Rundtour, die jede Straße mindestens einmal durchläuft (um Briefe einzuwerfen). Gibt es im zugrundeliegenden Graphen gerichtete und ungerichtete Kanten (d.h. Einbahnstraßen und normale Straßen), so ist das Problem NP-schwer. Die beiden anderen Fälle (nur gerichtete oder nur ungerichtete Kanten) hingegen sind einfach zu lösen; ein Applet für das gerichtete Postboten Problem finden Sie bei den Graphalgorithmen.

Grundlegende Algorithmen auf Graphen
Veranschaulichung grundlegender Algorithmen
Routenplanung.png Beschreibung: Visualisierung der algorithmischen Vorgehensweisen zur Lösung einiger grundlegender Problemstellungen der Routenplanung, wie sie etwa in Navigationssystemen oder der täglichen Planung großer Logistikunternehmen auftreten.
Mathematische Beschreibung: Folgende Algorithmen sind verfügbar:
Kürzeste Wege:Dijkstra, A*, Bellman-Ford, Floyd-Warshall
Minimale Spannbäume:Prim,Kruskal
Euler-Touren:Hierholzer
Minimale Perfekte Matchings:Hopcroft-Karp, Ungarische Methode
Chinese Postman:Kombination der obigen Algorithmen