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

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