Greedy-Algorithmen SS09

Aus ProgrammingWiki

< AuK

Archivierte Version vom 2009-05-17T11:58:55+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

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)

(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 '())))))

<eval> > (geldwechsel 1293) </eval>

Verschiedene Greedy-Algorithmen

Greedy

Dijkstra

Edsger W. Dijkstra auf Wikipedia

Kruskal

Joseph Kruskal auf Wikipedia

Greedy-Algorithmen SS09

Inhaltsverzeichnis

Einführung

Bruchteilrucksack-Problem

Aufbau

Anwendbarkeit

Beispiel (Geldwechsel)

Verschiedene Greedy-Algorithmen

Dijkstra

Kruskal

Übung

Suche