Greedy-Algorithmen SS09

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2009-05-17T12:18:09+00:00. Aktuelle Version

Inhaltsverzeichnis

Dev Status

Einführung

lalala

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.

<eval> (geldwechsel 1293) </eval>

Verschiedene Greedy-Algorithmen

Greedy

Dijkstra

Edsger W. Dijkstra auf Wikipedia

Kruskal

Joseph Kruskal auf Wikipedia

Übung