Greedy-Algorithmen SS09

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

Inhaltsverzeichnis

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)

<eval> (geldwechsel 1293) </eval>

Verschiedene Greedy-Algorithmen

Greedy

Dijkstra

Edsger W. Dijkstra auf Wikipedia

Kruskal

Joseph Kruskal auf Wikipedia

Übung