Greedy-Algorithmen WS13-14

Einführung

Entgegen anderen Programmiermethoden, wie bspw. dem Dynamischen Programmieren oder dem systematischen Probieren mit Backtracking, arbeiten Greedy-Algorithmen nach dem Motto "Nimm immer den besten Happen, den du kriegen kannst". Hierzu werden immer Entscheidungen auf Basis von lokalen (zu dieser Zeit vorliegenden) Informationen getroffen. Greedy-Algorithmen sind gefräßig und suchen sich immer die besten Stücken aus.

Auf den ersten Blick erscheint das Verfahren gut, denn der Aufwand, den man benötigt, wird wohl nicht exponentiell sein.

Die Basis eines Greedy-Algorithmus ist eine bereits vorsortierte Liste. Wird diese erweitert, werden die entsprechenden Elemente direkt an die richtige Stelle einsortiert.