Miniforschungsprojekt 'Kürzeste Wege'

Mit den OberstufenteilnehmerInnen am Hector-Seminar wurden Möglichkeiten für eine betreute und begleitete Miniforschung (einzeln oder in Zweiergruppen) besprochen. Als mögliches Miniforschungsthema bietet sich die Berechnung kürzester Wege in Graphen an. Um einen ersten Einblick in das Thema zu bekommen, sind folgende Quellen u.U. hilfreich:

• Wikipedia: Kürzester Pfad
  Dabei sind auch die Verweise auf grundlegend Algorithmen (A*, Dijkstra, Bellman-Ford) interessant. Die zugehörige englische Webseite ist etwas ausführlicher.

• In 'Game Programming Gems 3' zeigt der Artikel von William van der Sterren (S 294.ff; Handbibliothek) auf, wie man Verfahren wie A-Stern auch für die taktische Pfadplanung in Computerspielen verwenden kann ("Tactical path-finding with A*").

• In der Publikation von Goldberg et.al. werden Landmarking und Reaching als zwei praktikable Varianten bei der behandlung grosser Karten angesprochen. Zudem werden hier extrem grosse Datensätze behandelt.

• Eine Veröffentlichung von Schultes et.al. finden sich Algorithmische Details für kurze Strecken und heterogene Netze. Die Beispiele dazu stammen aus Deutschland

• Bast et al. betrachten einen Algorithmus, der durch intensives Preprocessing Arbeiten, die nur vom Netz abhängen, in einem Preprocessing-Schritt durchführt.

• Auch die Arbeit von Lauther verwendet Preprocessing und zeichnet sich dabei durch ihre Praxisnähe aus (Siemens AG).

Die Auswahl der Quellen zeigt einige Themengebiete auf, mit denen man sich beschäftigen kann: Beweis der Optimalität der errechneten Lösung, Effizienz der Algorithmen, Preprocessing zur Beschleunigung der Suche, Experimente an grossen Datensätzen, ...