Können „gierige Verhaltensweisen“ zum Ziel führen?

Prof: Heike Ripphausen-Lipa aus dem Studiengang Medieninformatik
Schulfach:Informatik
Vortragszeit: 45-90 Min. (je nach Wunsch)
Vorkenntnisse der Teilnehmer: Der Vortrag kann auf unterschiedliche Vorkenntnisse abgestimmt werden.
Benötigte Ausrüstung: Beamer, Tafel

Terminvereinbarung

030 4504-2751
ripphausen[at]beuth-hochschule.de


Inhalt

In unserem Alltag lösen wir ständig Optimierungsprobleme wie z.B. eine möglichst kurze Rundreise durch mehrere Städte zu finden, den Kofferraum eines Autos optimal auszunutzen, usw.

Eine typische Vorgehensweise diese Probleme zu lösen ist das sogenannte „Greedy-Verfahren“ oder auch „gierige Verfahren“. Bei einem Greedy-Verfahren erweitert man eine Teillösung des Problems durch die momentan am günstigsten erscheinende Möglichkeit.

Als Beispiel soll der Aufbau eines Systems von Brücken zwischen mehreren Inseln dienen, sodass man nur über Brücken zwischen den verschiedenen Inseln reisen kann und die Kosten möglichst gering sind. Ein Greedy-Verfahren zum Aufbau eines solchen Systems besteht darin, sukzessiv die kostengünstigste Brücke, d.h. die Brücke kürzester Länge auszuwählen, die nicht überflüssig ist. Dies wird solange wiederholt, bis alle Inseln miteinander verbunden sind.

21. Algorithmus der Woche (2006): Minimale aufspannende Bäume