Greedy-Algorithmen SS09

Aus ProgrammingWiki

Archivierte Version vom 2009-05-17T15:07:07+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Einführung
2 Bruchteilrucksack-Problem
3 Aufbau
4 Anwendbarkeit
5 Beispiel (Geldwechsel)
6 Verschiedene Greedy-Algorithmen
- 6.1 Dijkstra
- 6.2 Kruskal
7 Übung
8 Kommentare

Dev Status

Einführung

Greedy [eng. gefräßig] - eine gefräßige Strategie für Algorithmen. Sie funktioniert nach der Methode:

"Nimm immer den besten Happen, den du kriegen kannst."

Das geschieht durch eine rechnerische Entscheidung. Die Berechnung erfolgt auf der Basis lokaler Information, also ohne Rückgriff auf vorher ermittelte Werte.

Bruchteilrucksack-Problem

Greedy

Aufbau

(define greedy
 (lambda (vorgabewert) ; z.B.: Kapazitaet der Rucksacks
  (let
      ((kandidatenliste '(......))
       (loesung? (lambda (ls) ... ))
       (okay? (lambda (ls) ... ))
       (naechster (lambda (ls) ... ))
       (modify+ (lambda (x ls) ... ))
       (modify- (lambda (x ls) ... ))
       (ziel (lambda (ls) ... ))
   (letrec
        ((helfer
           (lambda (kandidaten resultat)
            (cond
             ((loesung? resultat)(ziel resultat))
             ((and (null? kandidaten)(not (loesung? resultat)))
              (error 'greedy "Es gibt keine Loesung."))
             (else
              (let* ((neuer-kandidat (naechster kandidaten))
                     (neues-resultat (cons neuer-kandidat resultat)))
                 (if (okay? neues-resultat)
                     (helfer (modify+ neuer-kandidat kandidaten) neues-resultat)
                     (helfer (modify- neuer-kandidat kandidaten) resultat))))))))
        (helfer kandidatenliste '())))))

Anwendbarkeit

Greedy

Beispiel (Geldwechsel)

Einem Kunden wird Wechselgeld herausgegeben, wobei möglichst wenige Münzen verwendet werden sollen.

Zur Verfügung haben wir alle Euro-Münzen: 1, 2, 5, 10, 20, 50, 100 (1 Euro), 200 (2 Euro).
Die Münzen werden mit absteigendem Cent-Wert vorsortiert.
Die Prozedur geldwechsel ergibt Resultatliste und Anzahl der Münzen.

(define geldwechsel
 (lambda (restbetrag)
  (let ((kandidatenliste '(200 100 50 20 10 5 2 1))
    (loesung? (lambda (ls)(= restbetrag (apply + ls))))
    (okay? (lambda (ls) (<= (apply + ls) restbetrag)))
    (naechster car)
    (modify+ (lambda (x ls) ls))
    (modify- (lambda (x ls) (delete x ls)))
    (ziel (lambda (ls) (cons (reverse ls) (list (length ls))))))
   (letrec
      ((helfer
       (lambda (kandidaten resultat)
         (cond
          ((loesung? resultat)(ziel resultat))
          ((and (null? kandidaten)(not (loesung? resultat)))
           (error 'greedy "Es gibt keine Loesung"))
          (else
           (let* ((neuer-kandidat (naechster kandidaten))
                  (neues-resultat (cons neuer-kandidat resultat)))
              (if (okay? neues-resultat)
                  (helfer
                   (modify+ neuer-kandidat kandidaten)
                    neues-resultat)
                  (helfer
                   (modify- neuer-kandidat kandidaten)
                    resultat))))))))
          (helfer kandidatenliste '())))))

Die Prozedur wird benutzt um 12,93 Euro (1293 Euro-Cent) herauszugeben. <eval> (geldwechsel 1293) </eval>