Forschungsinstitut für Diskrete Mathematik
Programmierpraktikum Diskrete Optimierung (Modul P2C1)
Sommersemester 2010
Thema: Kürzeste Wege zwischen Hindernissen
Kürzeste-Wege-Probleme gehören zu den grundlegenden
Problemen der Optimierung. Meistens werden dabei Wege in einem
vorgegebenen Graphen gesucht.
In diesem Programmierpraktikum wird dagegen das Problem betrachtet, zwischen
zwei Punkten in der Ebene einen möglichst kurzen Weg zu berechnen, wobei
man bestimmten (rechteckigen) Hindernissen ausweichen muß.
Dieses Problem muß z.B. beim Entwurf von modernen Computerchips
millionenfach gelöst werden, daher werden sehr schnelle
Algorithmen und effiziente Implementierungen benötigt.
In diesem Praktikum sollen einige Verfahren zur Lösung dieses
Problems implementiert und auf großen Instanzen aus der Praxis getestet
werden.
Einen Überblick über einige Algorithmen zur
Berechnung von solchen kürzesten Wegen bietet der Artikel
"Rectilinear paths among rectilinear obstacles"
von D.T. Lee und C.D. Yang, Discrete Applied Mathematics, 70,
1996, 185-215.
Ein genaue Beschreibung der Aufgabenstellung findet sich hier.
Test-Instanzen:
Größere Instanzen:
Ein hohes mathematisches Interesse und
grundlegende Programmierkenntnisse werden vorausgesetzt.
Prof. Dr.
B. Korte,
Prof. Dr.
J. Vygen,
Prof.
Dr. S. Hougardy,
Jun.Prof.
Dr. T. Nieberg,
Dr. U.
Brenner
